Structured Game Representations and Efficient Nash Calculations
Stanford / Intel Research / UC-Riverside
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.