The Complexity of Symmetric Bimatrix Games with Common Payoffs
ACM Transactions on Economics and Computation · 10.06.2026
DOI: 10.1145/3820246 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Economics and Computation, online erschienen am 10.06.2026. Verfasst von Abheek Ghosh und 1 weiteren Autor:innen. Die Arbeit nennt 35 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Ghosh, A., & Hollender, A. (2026). The Complexity of Symmetric Bimatrix Games with Common Payoffs. ACM Transactions on Economics and Computation. https://doi.org/10.1145/3820246
Vancouver
Ghosh A, Hollender A. The Complexity of Symmetric Bimatrix Games with Common Payoffs. ACM Transactions on Economics and Computation. 2026. doi:10.1145/3820246
BibTeX
@article{Ghosh2026,
author = {Ghosh, Abheek and Hollender, Alexandros},
title = {The Complexity of Symmetric Bimatrix Games with Common Payoffs},
journal = {ACM Transactions on Economics and Computation},
year = {2026},
doi = {10.1145/3820246}
}
EUVIMED