• Calendar

December 23, Wednesday
12:00 – 13:30

In 1951, John Nash proved that every game has an equilibrium, i.e. a set of strategies such that no player has an incentive to change her strategy. Nash's proof is non-constructive in nature, since it relies on Brouwer's fixed point theorem. This raises the following question - given a game, what is the computational complexity of finding a Nash equilibrium?

In this talk I will give an introduction to the area of Computing Equilibria in Algorithmic Game Theory and overview a breakthrough result suggesting that the problem of finding a Nash equilibrium is hard – Daskalakis et al. prove it is complete for the complexity class PPAD. The proof is based on a reduction from fixed point problems to finding equilibria, using small “gadget games” as means of performing arithmetic computations.

No prior knowledge is assumed.

References: C. Daskalakis, P. W. Goldberg and C. H. Papadimitriou. - The Complexity of Computing a Nash Equilibrium, SIAM Journal on Computing, 1:195-259, 2009. K. Etessami and M. Yannakakis. On the Complexity of Nash Equilibria and Other Fixed Points, - In the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007.