Title :
Settling the Complexity of Two-Player Nash Equilibrium
Author :
Chen, Xi ; Deng, Xiaotie
Author_Institution :
Dept. of Comput. Sci., Tsinghua Univ., Beijing
Abstract :
Even though many people thought the problem of finding Nash equilibria is hard in general, and it has been proven so for games among three or more players recently, it´s not clear whether the two-player case can be shown in the same class of PPAD-complete problems. We prove that the problem of finding a Nash equilibrium in a two-player game is PPAD-complete
Keywords :
computational complexity; decision theory; game theory; PPAD-complete problems; two-player Nash equilibrium complexity; two-player games; Application software; Computer science; Ellipsoids; Game theory; Linear programming; Mathematical model; Nash equilibrium; Optimization methods; Polynomials; Sampling methods;
Conference_Titel :
Foundations of Computer Science, 2006. FOCS '06. 47th Annual IEEE Symposium on
Conference_Location :
Berkeley, CA
Print_ISBN :
0-7695-2720-5
DOI :
10.1109/FOCS.2006.69
