EUVIMEDDescoperă EUVIMED
Crossref

The Complexity of Symmetric Bimatrix Games with Common Payoffs

Abheek Ghosh, Alexandros Hollender

ACM Transactions on Economics and Computation · 2026-06-10

DOI: 10.1145/3820246 ↗

At a glance

Journal article in ACM Transactions on Economics and Computation, published online on 2026-06-10. Written by Abheek Ghosh and 1 co-authors. 35 references.

RezumatDate bibliograficeCiteRelated studies

Abstract (original language)

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.

Cite

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}
}
Start for free →