On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Standard

On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria. / Berthelsen, Marie Louisa Tølbøll; Hansen, Kristoffer Arnsfelt.

Algorithmic Game Theory - 12th International Symposium, SAGT 2019, Proceedings. ed. / Dimitris Fotakis; Evangelos Markakis. Cham : Springer VS, 2019. p. 153-167 (Lecture Notes in Computer Science, Vol. 11801).

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Harvard

Berthelsen, MLT & Hansen, KA 2019, On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria. in D Fotakis & E Markakis (eds), Algorithmic Game Theory - 12th International Symposium, SAGT 2019, Proceedings. Springer VS, Cham, Lecture Notes in Computer Science, vol. 11801, pp. 153-167, 12th International Symposium: International Symposium on Algorithmic Game Theory, Athen, Greece, 30/09/2019. https://doi.org/10.1007/978-3-030-30473-7_11

APA

Berthelsen, M. L. T., & Hansen, K. A. (2019). On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria. In D. Fotakis, & E. Markakis (Eds.), Algorithmic Game Theory - 12th International Symposium, SAGT 2019, Proceedings (pp. 153-167). Springer VS. Lecture Notes in Computer Science, Vol.. 11801 https://doi.org/10.1007/978-3-030-30473-7_11

CBE

Berthelsen MLT, Hansen KA. 2019. On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria. Fotakis D, Markakis E, editors. In Algorithmic Game Theory - 12th International Symposium, SAGT 2019, Proceedings. Cham: Springer VS. pp. 153-167. (Lecture Notes in Computer Science, Vol. 11801). https://doi.org/10.1007/978-3-030-30473-7_11

MLA

Berthelsen, Marie Louisa Tølbøll and Kristoffer Arnsfelt Hansen "On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria". and Fotakis, Dimitris Markakis, Evangelos (editors). Algorithmic Game Theory - 12th International Symposium, SAGT 2019, Proceedings. Cham: Springer VS. (Lecture Notes in Computer Science, Vol. 11801). 2019, 153-167. https://doi.org/10.1007/978-3-030-30473-7_11

Vancouver

Berthelsen MLT, Hansen KA. On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria. In Fotakis D, Markakis E, editors, Algorithmic Game Theory - 12th International Symposium, SAGT 2019, Proceedings. Cham: Springer VS. 2019. p. 153-167. (Lecture Notes in Computer Science, Vol. 11801). https://doi.org/10.1007/978-3-030-30473-7_11

Author

Berthelsen, Marie Louisa Tølbøll ; Hansen, Kristoffer Arnsfelt. / On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria. Algorithmic Game Theory - 12th International Symposium, SAGT 2019, Proceedings. editor / Dimitris Fotakis ; Evangelos Markakis. Cham : Springer VS, 2019. pp. 153-167 (Lecture Notes in Computer Science, Vol. 11801).

Bibtex

@inproceedings{77043cacaf5b4114abffb82b7ad19aaa,
title = "On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria",
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, ∃R-complete, when m≥3. We show that, unless they turn into trivial problems, they are ∃R-hard even for 3-player zero-sum games.We also obtain new results about several other decision problems. We show that when m≥3 the problems of deciding if a game has a Pareto optimal Nash equilibrium or deciding if a game has a strong Nash equilibrium are ∃R-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 ∃R-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 ∃R-complete when m≥3, answering a question of Garg, Mehta, Vazirani, and Yazdanbod.",
author = "Berthelsen, {Marie Louisa T{\o}lb{\o}ll} and Hansen, {Kristoffer Arnsfelt}",
year = "2019",
doi = "10.1007/978-3-030-30473-7_11",
language = "English",
isbn = "978-3-030-30472-0",
series = "Lecture Notes in Computer Science",
publisher = "Springer VS",
pages = "153--167",
editor = "Dimitris Fotakis and Evangelos Markakis",
booktitle = "Algorithmic Game Theory - 12th International Symposium, SAGT 2019, Proceedings",
note = "null ; Conference date: 30-09-2019 Through 03-10-2019",

}

RIS

TY - GEN

T1 - On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria

AU - Berthelsen, Marie Louisa Tølbøll

AU - Hansen, Kristoffer Arnsfelt

N1 - Conference code: 12

PY - 2019

Y1 - 2019

N2 - 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, ∃R-complete, when m≥3. We show that, unless they turn into trivial problems, they are ∃R-hard even for 3-player zero-sum games.We also obtain new results about several other decision problems. We show that when m≥3 the problems of deciding if a game has a Pareto optimal Nash equilibrium or deciding if a game has a strong Nash equilibrium are ∃R-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 ∃R-hard, answering a question of Biló 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 ∃R-complete when m≥3, answering a question of Garg, Mehta, Vazirani, and Yazdanbod.

AB - 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, ∃R-complete, when m≥3. We show that, unless they turn into trivial problems, they are ∃R-hard even for 3-player zero-sum games.We also obtain new results about several other decision problems. We show that when m≥3 the problems of deciding if a game has a Pareto optimal Nash equilibrium or deciding if a game has a strong Nash equilibrium are ∃R-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 ∃R-hard, answering a question of Biló 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 ∃R-complete when m≥3, answering a question of Garg, Mehta, Vazirani, and Yazdanbod.

U2 - 10.1007/978-3-030-30473-7_11

DO - 10.1007/978-3-030-30473-7_11

M3 - Article in proceedings

SN - 978-3-030-30472-0

T3 - Lecture Notes in Computer Science

SP - 153

EP - 167

BT - Algorithmic Game Theory - 12th International Symposium, SAGT 2019, Proceedings

A2 - Fotakis, Dimitris

A2 - Markakis, Evangelos

PB - Springer VS

CY - Cham

Y2 - 30 September 2019 through 3 October 2019

ER -