The Computational Complexity of Finding a Nash Equilibrium

by Edith Elkind

In 1951, Nash proved his classical result that every game admits mixed
strategies that are optimal with respect to each other. Such a set of
strategies is known as a Nash equilibrium. The proof is
non-constructive, and the computational problem of constructing Nash
equilibria has subsequently attracted considerable attention within
the algorithmics community.
The search for a Nash equilibrium belongs to the complexity class
PPAD, a class of problems where solutions have an "inefficient proof
of existence" based on a parity argument in a directed graph. In this
talk, we discuss PPAD and several important variants of the problem of
finding a Nash equilibrium.
We overview a stream of exciting new results in this area, which
culminated in a proof that 2-player Nash is PPAD-complete. The talk
assumes no prior knowledge of complexity theory or game theory.