Symmetries and the Complexity of Nash Equilibria
Speaker: Costantinos Daskalakis , Microsoft Research New England
Date: March 3 2009
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Scott Aaronson, CSAIL, MIT
Contact: be, 3-6098, imbe@mit.edu
Relevant URL: How long does it take a market or, more broadly, a game to reach an equilibrium state? I will review recent work with Paul Goldberg and Christos Papadimitriou, showing that convergence to a Nash equilibrium may take prohibitively long. Since a Nash equilibrium is guaranteed to exist in every game---by Nash's seminal result, the theory of NP-completeness does not seem appropriate for characterizing its complexity. Our result is that the Nash equilibrium is as hard computationally as the Brouwer fixed-point computation problem, in a precise technical sense. The existence of the Nash equilibrium was established via Brouwer's fixed-point theorem; hence our result is the computational converse of Nash's theorem.
To alleviate the negative implications of this hardness result, I will consider special classes of games with potentially better computational features. One such class is the class of symmetric games, where all players are the same in that they have the same payoff functions and these functions are symmetric with respect to the other players' strategies. Symmetric games were already considered in Nash's original 1951 paper, where it was shown that there always exists a symmetric equilibrium, assigning the same mixed strategy to each player of the game. As a consequence of this result, an equilibrium for these games can be computed in polynomial time, as long as the number of strategies of the players is small.
Motivated by this positive result, I will consider a broader class of games, called anonymous, in which the players' utilities only depend on the aggregate behavior of the other players, like in symmetric games, but each player may have now a different utility function. This class of games is arguably more attractive and relevant to applications than symmetric games; examples arise in traffic, social interactions, and certain auction settings. I will present several approaches for approximating multiplayer anonymous games with a small number of strategies, culminating in an efficient polynomial time approximation scheme with quasi-polynomial running time in the approximation guarantee. All approximation schemes are based on characterizing the symmetries of these games via finitary Central Limit Theorems.
See other events that are part of Theory Colloquium 2008/2009
See other events happening in March 2009
