In complexity, the most exciting work studied the problem of finding equilibriums of games. How does one find a Nash Equilibrium when each player's payoffs are given by a matrix. In a 2-player zero-sum game (my gain is your loss), one can easily find equilibriums using linear programming. But if we have unrelated payoffs, computing the equilibrium can be much more difficult.

- The Complexity of Computing a Nash Equilibrium by Constantinos Daskalakis, Paul Goldberg and Christos Papadimitriou
- Settling the Complexity of Two-Player Nash Equilibrium by Xi Chen and Xiaotie Deng

Daskalakis et al. showed that computing the Nash Equilibrium between three players in PPAD-complete and Chen and Deng extended their work to 2-player games. PPAD represents a search problem, solvable if P = NP though not believed to be NP-hard.

You don't have to know the formal definition of PPAD to appreciate this work. PPAD corresponds to a discrete version of the Brouwer fixed-point theorem, the critical tool in proving that Nash Equilibriums exist. One proof of the fixed-point theorem uses Sperner's Lemma, also PPAD-complete. The New York Times has a nice example of using Sperner's Lemma to fairly divide up the rent among three friends who share an apartment with different sized rooms.

Paul Goldberg wrote a nice survey on these and related results, such as finding equilibria in markets.

Are there any important or really interesting problems left in this area? A quick look at the survey you point to turned up a list of maybe 3-4 open problems out of which maybe one (complexity of computing approximate equilibria) seems to be somewhat important and interesting and the rest seem technical and of only marginal interest (but I am not sure---I don't work in this area).

ReplyDeleteHow about a definition of PPAD independent of singling out a particular problem?

ReplyDeleteHow about a definition of PPAD independent of singling out a particular problem?

ReplyDelete