On the computational complexity of decision problems about multi-player Nash equilibria

DOI10.1007/978-3-030-30473-7_11MaRDI QIDQ5919366zbMATH OpenOpenAlexFDO

Authors Marie Louisa Tølbøll Berthelsen, Kristoffer Arnsfelt Hansen

Publication date 4 February 2020

Published in Algorithmic Game Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2001.05196, https://rd.springer.com/content/pdf/10.1007%2F978-3-030-30473-7_11.pdf

zbMATH Keywords

computational complexitydecision problemsmulti-player Nash equilibria

Mathematics Subject Classification ID

(n)-person games, (n>2) (91A06) Decision theory for games (91A35) Algorithmic game theory and complexity (91A68)

Abstract: We study the computational complexity of decision problems about Nash equilibria in $m$-player games. Several such problems have recently been shown to be computationally equivalent to the decision problem for the existential theory of the reals, or stated in terms of complexity classes, $existsmathbbR$-complete, when $mgeq3$. We show that, unless they turn into trivial problems, they are $existsmathbbR$-hard even for 3-player zero-sum games. We also obtain new results about several other decision problems. We show that when $mgeq3$ the problems of deciding if a game has a Pareto optimal Nash equilibrium or deciding if a game has a strong Nash equilibrium are $existsmathbbR$-complete. The latter result rectifies a previous claim of NP-completeness in the literature. We show that deciding if a game has an irrational valued Nash equilibrium is $existsmathbbR$-hard, answering a question of Bil`o and Mavronicolas, and address also the computational complexity of deciding if a game has a rational valued Nash equilibrium. These results also hold for 3-player zero-sum games. Our proof methodology applies to corresponding decision problems about symmetric Nash equilibria in symmetric games as well, and in particular our new results carry over to the symmetric setting. Finally we show that deciding whether a symmetric $m$-player games has a non-symmetric Nash equilibrium is $existsmathbbR$-complete when $mgeq3$, answering a question of Garg, Mehta, Vazirani, and Yazdanbod.

Recommendations

• On the computational complexity of decision problems about multi-player Nash equilibria
• \(\exists\mathbb{R}\)-complete decision problems about symmetric Nash equilibria in symmetric multi-player games
• ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
• A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
• Complexity of rational and irrational Nash equilibria

Cited in

(19)

• Final decisions, the Nash equilibrium and solvability in games with common knowledge of logical abilities
• On the NP-completeness of finding an optimal strategy in games with common payoffs
• On computational complexity of membership test in flow games and linear production games
• Complexity of rational and irrational Nash equilibria
• Computational complexity of multi-player evolutionarily stable strategies
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• Complexity of rational and irrational Nash equilibria
• ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
• A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
• \(\exists\mathbb{R}\)-complete decision problems about symmetric Nash equilibria in symmetric multi-player games
• scientific article; zbMATH DE number 7559416 (Why is no real title available?)
• The real computational complexity of minmax value and equilibrium refinements in multi-player games
• On the computational complexity of decision problems about multi-player Nash equilibria
• The real computational complexity of minmax value and equilibrium refinements in multi-player games
• Computational complexity of decision problems about Nash equilibria in win-lose multi-player games
• The complexity of recognizing geometric hypergraphs
• Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
• The complexity of recognizing geometric hypergraphs

This page was built for publication: On the computational complexity of decision problems about multi-player Nash equilibria

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5919366)