NDLI: The Complexity of Computing a Nash Equilibrium

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Daskalakis, Constantinos Papadimitriou, Christos H. Goldberg, Paul W.
Copyright Year	2009
Abstract	In 1951, John F. Nash proved that every game has a Nash equilibrium [Ann. of Math. (2), 54 (1951), pp. 286295]. His proof is nonconstructive, relying on Brouwer's fixed point theorem, thus leaving open the questions, Is there a polynomial-time algorithm for computing Nash equilibria? And is this reliance on Brouwer inherent? Many algorithms have since been proposed for finding Nash equilibria, but none known to run in polynomial time. In 1991 the complexity class PPAD (polynomial parity arguments on directed graphs), for which Brouwer's problem is complete, was introduced [C. Papadimitriou, J. Comput. System Sci., 48 (1994), pp. 489532], motivated largely by the classification problem for Nash equilibria; but whether the Nash problem is complete for this class remained open. In this paper we resolve these questions: We show that finding a Nash equilibrium in three-player games is indeed PPAD-complete; and we do so by a reduction from Brouwer's problem, thus establishing that the two problems are computationally equivalent. Our reduction simulates a (stylized) Brouwer function by a graphical game [M. Kearns, M. Littman, and S. Singh, Graphical model for game theory, in 17th Conference in Uncertainty in Artificial Intelligence (UAI), 2001], relying on gadgets, graphical games performing various arithmetic and logical operations. We then show how to simulate this graphical game by a three-player game, where each of the three players is essentially a color class in a coloring of the underlying graph. Subsequent work [X. Chen and X. Deng, Setting the complexity of 2-player Nash-equilibrium, in 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006] established, by improving our construction, that even two-player games are PPAD-complete; here we show that this result follows easily from our proof.
Starting Page	195
Ending Page	259
Page Count	65
File Format	PDF
ISSN	00975397
DOI	10.1137/070699652
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	1 (Special Issue On The Thirty-Eighth Annual ACM Symposium On Theory Of Computing (STOC 2006))
Volume Number	39
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2009-05-28
Access Restriction	Subscribed
Subject Keyword	Computational difficulty of problems complexity General equilibrium theory Noncooperative games 2-person games PPAD-completeness game theory Nash equilibrium $n$-person games, $n>2$ Symbolic computation and algebraic computation
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the Complexity of Nash Equilibria and Other Fixed Points

Reducibility among Fractional Stability Problems

Existential Theory of the Reals Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games

The complexity of computing a Nash equilibrium

A Survey of PPAD-Completeness for Computing Nash Equilibria

Multilinear formulations for computing Nash equilibrium of multi-player matrix games

Cmsc 858f: algorithmic game theory fall 2010 complexity of finding nash equilibrium: ppad completeness results (2010).

Evaluating Matrix Circuits

Even faster integer multiplication

The Complexity of Computing a Nash Equilibrium

Similar Documents

On the Complexity of Nash Equilibria and Other Fixed Points

Reducibility among Fractional Stability Problems

Existential Theory of the Reals Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games

The complexity of computing a Nash equilibrium

A Survey of PPAD-Completeness for Computing Nash Equilibria

Multilinear formulations for computing Nash equilibrium of multi-player matrix games

Cmsc 858f: algorithmic game theory fall 2010 complexity of finding nash equilibrium: ppad completeness results (2010).

Evaluating Matrix Circuits

Even faster integer multiplication

The Complexity of Computing a Nash Equilibrium