The authors leave open the complexity of finding Nash Equilibrium for two and three players. They conjecture that for three players the problem remains complete for PPAD but two player Nash Equilibriums can be found in polynomial time.
Tuesday, October 18, 2005
Finding Nash has Same Complexity as Finding Fixed Points
In a new paper, Daskalakis, Goldberg and Papadimitriou show that finding Nash Equilibrium in matrix games with four or more players is complete for the search class PPAD. PPAD is best described by the problem: Given an exponential-size direced graph with every node having in-degre and out-degree at most one described by a polynomial-time computable function f(v) that outputs the predecessor and successor of v, and a vertex s with a successor but no predecessors, find a t≠s that either has no successors or predecessors. The underlying combinatorial statement that such a t exists is used to prove Sperner's Lemma which can be used to prove the Brouwer fixed point theorem which in turn can be used to prove the existence of Nash Equilibrium.