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.
Subscribe to:
Post Comments (Atom)
How important a result is this?
ReplyDeleteIt is essentially one of the strongest "hardness" results that one could hope to prove for the problem. Most people believe that PPAD-complete problems do not have polynomial-time algorithms, I think.
ReplyDeleteSomeone asked "How important a result is this?"
ReplyDeleteVery important. PPAD is a sub-class of TFNP, which consists of all "NP search problems" for which a solution is guaranteed to exist. An easy example is factoring an integer into its prime factors. Others include computing Nash equilibria, finding "Minkowski vectors" in lattices (vectors of length no more than a poly-time computable bound that were proved to exist by Minkowski), computing Brouwer fixed points, etc. There are also other cute problems like the one Lance mentioned, and also things like: given a circuit that maps n bits into n bits, either find an input that maps to all-0's or find two inputs that map to the same thing.
How one establishes the membership of a problem in TFNP (that is, how one shows that every instance has a solution) decides which sub-class of TFNP it goes into. Two papers --- one by Megiddo and Papadimitriou and one by Papadimitriou, circa 1990 --- placed several problems into this class. The type of techniques used include the use of pigeon-hole principle (as in the lattices example and the circuit example above), the use of parity arguments (as in Sperner's Lemma, Brouwer fixed points and Nash), simple graph-theoretic principles (every directed acyclic graph has a sink), etc.
Besides being natural bridges to much of classical mathematics, problems in TFNP tend not to be NP complete (where's the decision here?!), are not often polynomial-time solvable, have formed the bases of public-key cryptosystems (factoring and lattices), admit worst-case/average-case equivalence, etc.
These are truly curious beasts. On a more speculative note, it is conceivable that we separate P and NP by showing that one of these problems cannot be solved in polynomial time.
What exactly does PPAD complete mean? That every problem whose "guarantee of solution" comes from a certain type of parity argument can be reduced to the computation of Nash equilibria on a game with 4+ players. No more, no less --- our understanding of these problems is even worse than our understanding of the "famous" NP-complete problems.
Siva
Thanks for that informative comment D. Sivakumar.
ReplyDeleteI for one, had never heard of PPAD or TFNP but they sound quite natural.
Right, s has no predecessor but it must have a successor. I'll fix the post.
ReplyDeleteI know nothing about PPAD/TFNP, but am very interested in learning more. Do you know of a good overview reference, or at least one or two papers that cover the important aspects in some clarity?
ReplyDeleteAs a co-author of the paper (as well as a reader of this blog), let me thank Lance for taking the trouble to bring it to the attention of other readers! Anonymous wrote:
ReplyDeleteDo you know of a good overview reference [for PPAD/TFNP], or at least one or two papers that cover the important aspects in some clarity?
I recommend Papadimitriou's 1994 JCSS paper that is cited in the Nash/PPAD paper. The definitions start in Section 2; you may wish to skip Section 1 to begin with. I must admit, when I read it, I was in the happy position of being able to quiz the author on bits that weren't clear to me, always a big help.
Well, it appears that now both the 2- and 3-player cases are solved; both are PPAD-complete.
ReplyDeleteI know the results on PPAD-Completeness of >=3 player games. But is this also true for 2 player games? Is there a reference for this?
ReplyDeleteThanx in advance.
Here's a link to the paper about 2-Nash being PPAD-complete. Papadimitriou mentioned it in his invited talk at the NIPS conference, along with the clever comment "Game Over." :-)
ReplyDeleteCan someone comment on the relation between PPAD and NP? Does a polytime algorithm for one imply a polytime algorithm for the other?
Oops, forgot the link:
ReplyDeleteftp://ftp.eccc.uni-trier.de/pub/eccc/reports/2005/TR05-140/Paper.pdf
"Can someone comment on the relation between PPAD and NP? Does a polytime algorithm for one imply a polytime algorithm for the other?"
ReplyDeletePolynomial algorithm for NP implies polynomial one for TFNP (and PPAD in particular). The proof is easy - you can iteratively ask the hypothetical NP algorithm for consecutive bits of the solution for the TFNP problem.
The other implication is unproven. In particular, proving a TFNP problem to be NP-hard would imply NP=co-NP.