ETR-completeness for decision versions of multi-player (Symmetric) nash equilibria

Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod

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

Abstract

As a result of some important works [4–6, 10, 15], the complexity of 2-player Nash equilibrium is by now well understood, even when equilibria with special properties are desired and when the game is symmetric. However, for multi-player games, when equilibria with special properties are desired, the only result known is due to Schaefer and Štefankovič [18]: that checking whether a 3-player NE (3-Nash) instance has an equilibrium in a ball of radius half in l∞-norm is ETR-complete, where ETR is the class Existential Theory of Reals. Building on their work, we show that the following decision versions of 3-Nash are also ETR-complete: checking whether (i) there are two or more equilibria, (ii) there exists an equilibrium in which each player gets at least h payoff, where h is a rational number, (iii) a given set of strategies are played with non-zero probability, and (iv) all the played strategies belong to a given set. Next, we give a reduction from 3-Nash to symmetric 3-Nash, hence resolving an open problem of Papadimitriou [14]. This yields ETRcompleteness for symmetric 3-Nash for the last two problems stated above as well as completeness for the class FIXPa, a variant of FIXP for strong approximation. All our results extend to k-Nash, for any constant k ≥ 3.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings
EditorsMagnus M. Halldorsson, Naoki Kobayashi, Bettina Speckmann, Kazuo Iwama
PublisherSpringer-Verlag
Pages554-566
Number of pages13
ISBN (Print)9783662476710
DOIs
StatePublished - Jan 1 2015
Externally publishedYes
Event42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 - Kyoto, Japan
Duration: Jul 6 2015Jul 10 2015

Publication series

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

Other

Other42nd International Colloquium on Automata, Languages and Programming, ICALP 2015
CountryJapan
CityKyoto
Period7/6/157/10/15

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'ETR-completeness for decision versions of multi-player (Symmetric) nash equilibria'. Together they form a unique fingerprint.

  • Cite this

    Garg, J., Mehta, R., Vazirani, V. V., & Yazdanbod, S. (2015). ETR-completeness for decision versions of multi-player (Symmetric) nash equilibria. In M. M. Halldorsson, N. Kobayashi, B. Speckmann, & K. Iwama (Eds.), Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings (pp. 554-566). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9134). Springer-Verlag. https://doi.org/10.1007/978-3-662-47672-7_45