Network of Recursive-Modeling Influence Diagram: An approach to model and solve multi-stage games

Chen Xi

Abstract

The classical approaches to represent games encounter curse of dimension when the number of players or the number of decisions increases. Application of tools like influence diagram in decision theory alleviates the difficulty. However, the influence diagram expands tremendously when the number of decisions increases, which induces huge number of arcs. This exacerbates the solving difficulty as the graph offers little clue about the solution. This problem is more significant for multi-stage games in which a same format game is played in each stage and repeats several times. This thesis develops a new type of representation (NORMID) for multi-stage games, which not only solves the dimension curse but also incorporates the learning process of agencies. The final solution from NORMID includes the long term optimal strategies together with the trajectory of agents’ decisions. In other words, the learning process is reflected in NORMID solution.