On the Computational Complexity of Decision Problems about Multi-Player Nash Equilibria

Autor: Berthelsen, Marie Louisa Tølbøll, Hansen, Kristoffer Arnsfelt

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

Externí odkaz: http://arxiv.org/abs/2001.05196

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

Autor: Berthelsen, Marie Louisa Tølbøll, Hansen, Kristoffer Arnsfelt

Publikováno v: 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 . 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

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 st

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=pure_au_____::6312905d31e677868d978bbc7491389e
https://pure.au.dk/portal/da/publications/on-the-computational-complexity-of-decision-problems-about-multiplayer-nash-equilibria(77043cac-af5b-4114-abff-b82b7ad19aaa).html