TY - GEN

T1 - Settling some open problems on 2-player symmetric nash equilibria

AU - Mehta, Ruta

AU - Vazirani, Vijay V.

AU - Yazdanbod, Sadra

PY - 2015/1/1

Y1 - 2015/1/1

N2 - Over the years, researchers have studied the complexity of several decision versions of Nash equilibrium in (symmetric) two-player games (bimatrix games). To the best of our knowledge, the last remaining open problem of this sort is the following; it was stated by Papadimitriou in 2007: find a non-symmetric Nash equilibrium (NE) in a symmetric game. We show that this problem is NP-complete and the problem of counting the number of non-symmetric NE in a symmetric game is #Pcomplete. In 2005, Kannan and Theobald defined the rank of a bimatrix game represented by matrices (A,B) to be rank(A + B) and asked whether a NE can be computed in rank 1 games in polynomial time. Observe that the rank 0 case is precisely the zero sum case, for which a polynomial time algorithm follows from von Neumann’s reduction of such games to linear programming. In 2011, Adsul et al. obtained an algorithm for rank 1 games; however, it does not guarantee symmetric NE in symmetric rank 1 game. We resolve this problem.

AB - Over the years, researchers have studied the complexity of several decision versions of Nash equilibrium in (symmetric) two-player games (bimatrix games). To the best of our knowledge, the last remaining open problem of this sort is the following; it was stated by Papadimitriou in 2007: find a non-symmetric Nash equilibrium (NE) in a symmetric game. We show that this problem is NP-complete and the problem of counting the number of non-symmetric NE in a symmetric game is #Pcomplete. In 2005, Kannan and Theobald defined the rank of a bimatrix game represented by matrices (A,B) to be rank(A + B) and asked whether a NE can be computed in rank 1 games in polynomial time. Observe that the rank 0 case is precisely the zero sum case, for which a polynomial time algorithm follows from von Neumann’s reduction of such games to linear programming. In 2011, Adsul et al. obtained an algorithm for rank 1 games; however, it does not guarantee symmetric NE in symmetric rank 1 game. We resolve this problem.

UR - http://www.scopus.com/inward/record.url?scp=84983800989&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84983800989&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-48433-3_21

DO - 10.1007/978-3-662-48433-3_21

M3 - Conference contribution

AN - SCOPUS:84983800989

SN - 9783662484326

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 272

EP - 284

BT - Algorithmic Game Theory - 8th International Symposium, SAGT 2015

A2 - Hoefer, Martin

A2 - Hoefer, Martin

PB - Springer

T2 - 8th International Symposium on Algorithmic Game Theory, SAGT 2015

Y2 - 28 September 2015 through 30 September 2015

ER -