Two-player zero-sum games are easy to solve: one can write down a linear program whose solution is the value of the game and the optimal strategies of the players. This program is polynomial in the size of the game, and therefore the whole procedure of solving a two-player zero-sum game is polynomial. Similarly, computing a correlated equilibrium in a multi-player game can be done using a linear program, and is therefore as easy as taking a nap (when the kids do not have fever).
Solving a two-player non-zero-sum game, on the other hand, is a much more difficult task. Gilboa and Zemel proved that the questions “does there exist a Nash equilibrium where all players receive a payoff at least r” and “is there a unique Nash equilibrium” are difficult, NP-hard for computer scientists. The standard proof for the existence of a Nash equilibrium uses the unconstructive Brouwer’s fixed point theorem, and various procedures can be used to approximate a Nash equilibrium.
One reason to attend the conference at Stony Brook was to hear the talk of Noah Stein from MIT. In his talk, Stein presented a recent paper he wrote with Pablo Parrilo and Asuman Ozdaglar. In this paper the trio shows how to prove the existence of a Nash equilibrium using Hart and Schmeidler’s proof for the existence of a correlated equilibrium. Now, this proof for the existence of Nash equilibrium does not use Brouwer’s fixed point theorem or any advanced topological tool, and therefore it is interesting and worth reading. The main idea of the proof, if I got it right, is to show that a Nash equilibrium of the game can be approximated by a special kind of correlated equilibrium of an auxiliary game; the auxiliary game is an ingenious composition of k copies of the original game, and the approximation of the Nash equilibrium improves as k increases. A variation on the proof of Hart and Schmeidler exnsures that the special type of correlated equilibrium exists.
It was evident that the audience at the talk was interested: the talk took almost twice the time allotted to it, and many people were surprised by the proof. When you have time, read this paper. This is what I am going to do on my way to Erice for the workshop on Stochastic Methods in Game Theory.