The Complexity of Symmetric Bimatrix Games with Common Payoffs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913959101071360 |
|---|---|
| author | Ghosh, Abheek Hollender, Alexandros |
| author_facet | Ghosh, Abheek Hollender, Alexandros |
| contents | We study symmetric bimatrix games that also have the common-payoff property, i.e., the two players receive the same payoff at any outcome of the game. Due to the symmetry property, these games are guaranteed to have symmetric Nash equilibria, where the two players play the same (mixed) strategy. While the problem of computing such symmetric equilibria in general symmetric bimatrix games is known to be intractable, namely PPAD-complete, this result does not extend to our setting. Indeed, due to the common-payoff property, the problem lies in the lower class CLS, ruling out PPAD-hardness. In this paper, we show that the problem remains intractable, namely it is CLS-complete. On the way to proving this result, as our main technical contribution, we show that computing a Karush-Kuhn-Tucker (KKT) point of a quadratic program remains CLS-hard, even when the feasible domain is a simplex. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08031 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Complexity of Symmetric Bimatrix Games with Common Payoffs Ghosh, Abheek Hollender, Alexandros Computer Science and Game Theory Computational Complexity We study symmetric bimatrix games that also have the common-payoff property, i.e., the two players receive the same payoff at any outcome of the game. Due to the symmetry property, these games are guaranteed to have symmetric Nash equilibria, where the two players play the same (mixed) strategy. While the problem of computing such symmetric equilibria in general symmetric bimatrix games is known to be intractable, namely PPAD-complete, this result does not extend to our setting. Indeed, due to the common-payoff property, the problem lies in the lower class CLS, ruling out PPAD-hardness. In this paper, we show that the problem remains intractable, namely it is CLS-complete. On the way to proving this result, as our main technical contribution, we show that computing a Karush-Kuhn-Tucker (KKT) point of a quadratic program remains CLS-hard, even when the feasible domain is a simplex. |
| title | The Complexity of Symmetric Bimatrix Games with Common Payoffs |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2410.08031 |