Settling some open problems on 2-player symmetric nash equilibria

Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationAlgorithmic Game Theory - 8th International Symposium, SAGT 2015
EditorsMartin Hoefer, Martin Hoefer
PublisherSpringer-Verlag
Pages272-284
Number of pages13
ISBN (Print)9783662484326
DOIs
StatePublished - Jan 1 2015
Externally publishedYes
Event8th International Symposium on Algorithmic Game Theory, SAGT 2015 - Saarbrucken, Germany
Duration: Sep 28 2015Sep 30 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9347
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other8th International Symposium on Algorithmic Game Theory, SAGT 2015
CountryGermany
CitySaarbrucken
Period9/28/159/30/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Settling some open problems on 2-player symmetric nash equilibria'. Together they form a unique fingerprint.

Cite this