Computational Complexity of Multi-player Evolutionarily Stable Strategies

Autor:	Manon Blanc, Kristoffer Arnsfelt Hansen
Rok vydání:	2021
Předmět:	Discrete mathematics Computer Science::Computer Science and Game Theory Class (set theory) Hierarchy (mathematics) Computational complexity theory Complexity class Sigma Special case Time complexity Mathematics Evolutionarily stable strategy
Zdroj:	Computer Science – Theory and Applications ISBN: 9783030794156 CSR
Popis:	In this paper we study the computational complexity of computing an evolutionary stable strategy (ESS) in multi-player symmetric games. For two-player games, deciding existence of an ESS is complete for \(\mathrm {\Sigma }^\mathrm {p}_2\), the second level of the polynomial time hierarchy. We show that deciding existence of an ESS of a multi-player game is closely connected to the second level of the real polynomial time hierarchy. Namely, we show that the problem is hard for a complexity class we denote as \(\exists ^\mathrm {D}\cdot \forall \mathbb {R}\) and is a member of \(\exists \forall \mathbb {R}\), where the former class restrict the latter by having the existentially quantified variables be Boolean rather then real-valued. As a special case of our results it follows that deciding whether a given strategy is an ESS is complete for \(\forall \mathbb {R}\).
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::429e4ae1a8d9f7ed088c9788bee1da0a https://doi.org/10.1007/978-3-030-79416-3_1 Zobrazit plný text záznamu