Structured Game Representations and Efficient Nash Calculations

Christian Shelton
Stanford / Intel Research / UC-Riverside
USA

In this talk I will provide an overview of recent work from the field of artificial intelligence on compact structured representation of games. In particular I will describe graphical games -- a structured form of normal form games -- and multiagent influence diagrams (MAIDs) -- a structured form of extensive form games. These representations unify data structures from computer science with ideas from game theory and allow the efficient description of games of many players.

One of the main directions of research regarding these representations has been the use of structure in the game to find equilibria efficiently. I will present recent work of Ben Blum, Daphne Koller, and myself on algorithms that apply the homotopy method of Govindan and Wilson to graphical games and MAIDs, exploiting the structure of the games to vastly improve computational time.