Computability in Europe 2006
Logical Approaches to Computational Barriers

Special Session Talk:
Computing equilibria in large games we play

Speaker: Constantinos Daskalakis


Describing a game using the standard (table) representation requires information exponential in the number of players. This description size becomes impractical for modeling large games with thousands or millions of players and is also very wasteful since the information required to populate the game-table might be unknown, hard to determine, or enjoy high redundancy which would allow for a much more succinct representation. Indeed, to model large games, succinct representations, like graphical games, have been suggested which save in description complexity by specifying the graph of player-interactions. However, computing Nash equilibria in such games has been shown to be an intractable problem by Daskalakis, Goldberg and Papadimitriou, and whether approximate Nash equilibria can be computed for graphical games remains a major open problem. We consider instead a different class of succinct games, that of anonymous games, in which the payoff of each player is a symmetric function of the actions of the other players; that is, every player is oblivious of the identities of the other players. We argue that many large games of practical interest, such as congestion games, several auction settings, and social phenomena, are anonymous and we provide a polynomial time approximation scheme for computing Nash equilibria in anonymous games.

websites: Arnold Beckmann 2008-03-25