pith. sign in

arxiv: 1907.10468 · v1 · pith:ALVHQQ24new · submitted 2019-07-24 · 💻 cs.CC · cs.GT

The Complexity of Computational Problems about Nash Equilibria in Symmetric Win-Lose Games

Vittorio Bil\`o , Marios Mavronicolas This is my paper

Pith reviewed 2026-05-24 16:26 UTC · model grok-4.3

classification 💻 cs.CC cs.GT
keywords Nash equilibriawin-lose gamessymmetric gamesNP-hardnessbimatrix gamescomputational complexityGHR-symmetrizationdecision problems
0
0 comments X

The pith

NP-hardness of Nash equilibrium decision problems holds for symmetric win-lose bimatrix games

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper demonstrates that NP-hardness for deciding if a bimatrix game has a Nash equilibrium with certain properties continues to hold when the game is restricted to be both win-lose, with only 0 or 1 utilities, and symmetric. The authors achieve this by creating special win-lose gadgets for the reduction and by carefully adapting the GHR-symmetrization method to the win-lose case so that symmetry is preserved without losing the hardness. A sympathetic reader cares because these are strong restrictions that make the games simpler in structure, yet the computational difficulty for these problems does not decrease. The result also extends to show hardness for related search, counting, and parity problems in the same class of games.

Core claim

We show that the decision problems remain NP-hard for symmetric win-lose bimatrix games using win-lose gadgets and the GHR-symmetrization adapted to the win-lose setting. Symmetric win-lose bimatrix games are as complex as general bimatrix games for these problems. Hardness results are also derived for search, counting and parity problems about Nash equilibria in such games.

What carries the argument

Win-lose gadgets combined with an adapted GHR-symmetrization that maintains NP-hardness while enforcing 0-1 utilities and symmetry

If this is right

  • Decision problems about Nash equilibria with certain natural properties remain NP-hard in symmetric win-lose bimatrix games.
  • Search problems about Nash equilibria are hard in symmetric win-lose bimatrix games.
  • Counting problems about Nash equilibria are hard in symmetric win-lose bimatrix games.
  • Parity problems about Nash equilibria are hard in symmetric win-lose bimatrix games.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The result indicates that neither symmetry nor win-lose payoffs alone removes the hardness, since their combination preserves it.
  • Similar gadget-based reductions and symmetrization adaptations could apply when proving hardness under other payoff restrictions.

Load-bearing premise

The classical GHR-symmetrization can be adapted and analyzed in the win-lose setting without destroying the NP-hardness of the target decision problems.

What would settle it

Discovery of a polynomial-time algorithm for any of the decision problems about Nash equilibria with natural properties in symmetric win-lose bimatrix games would falsify the claim.

Figures

Figures reproduced from arXiv: 1907.10468 by Marios Mavronicolas, Vittorio Bil\`o.

Figure 1
Figure 1. Figure 1: A bimatricial representation of all profiles in [PITH_FULL_IMAGE:figures/full_fig_p028_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The utility functions for the game G = G(Gb, φ). (δij denotes the Kronecker delta.) 5.2 Properties of Nash Equilibria for G We now present a collection of properties for a Nash equilibrium σ ∈ N E(G). The first property is that either all players are exclusively playing gadget strategies or none is. Lemma 5.1 Fix a Nash equilibrium σ ∈ N E(G) with Supp (σi) ⊆ Σb i for some player i ∈ [r]. Then, for each pl… view at source ↗
Figure 3
Figure 3. Figure 3: The bimatrix game Ge = hS, S Ti with the mixed profile σ. Lemma 6.1 The win-lose GHR-symmetrization preserves the positive utility property. Given a mixed profile σ = hσ1, σ2i for Ge, denote, for each player i ∈ [2], as −→σi (resp., ←−σi) the restriction of σi to the last (resp., first) n strategies of player i, so that for each strategy j ∈ [n], ←−σi(j) = σi(j) and −→σi(j) = σi(n+j). Thus, σi = ←−σi ◦ −→σ… view at source ↗
Figure 4
Figure 4. Figure 4: Summary of the N P-hardness results for decision problems about Nash equilibria, and comparison to previous related work in [4, 7, 12, 13, 20, 28]. Columns correspond to classes of bimatrix games; specifically, the symbols G, S, WL and S+WL denote general, symmetric, win-lose and simultaneously symmetric and win-lose bimatrix games, respectively. The rightmost column gives the number of the corresponding t… view at source ↗
read the original abstract

We revisit the complexity of deciding, given a {\it bimatrix game,} whether it has a {\it Nash equilibrium} with certain natural properties; such decision problems were early known to be ${\mathcal{NP}}$-hard~\cite{GZ89}. We show that ${\mathcal{NP}}$-hardness still holds under two significant restrictions in simultaneity: the game is {\it win-lose} (that is, all {\it utilities} are $0$ or $1$) and {\it symmetric}. To address the former restriction, we design win-lose {\it gadgets} and a win-lose reduction; to accomodate the latter restriction, we employ and analyze the classical {\it ${\mathsf{GHR}}$-symmetrization}~\cite{GHR63} in the win-lose setting. Thus, {\it symmetric win-lose bimatrix games} are as complex as general bimatrix games with respect to such decision problems. As a byproduct of our techniques, we derive hardness results for search, counting and parity problems about Nash equilibria in symmetric win-lose bimatrix games.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proves that NP-hardness of several decision problems on the existence of Nash equilibria with specified properties (e.g., with support size constraints or other natural properties) continues to hold for bimatrix games that are simultaneously symmetric and win-lose (all payoffs in {0,1}). The proof proceeds by constructing win-lose gadgets that reduce from general bimatrix instances while preserving the 0/1 payoff restriction, followed by an adaptation of the classical GHR symmetrization that is shown to preserve both the win-lose property and the yes/no answer of the target decision problem. As a byproduct, the same techniques yield hardness results for the corresponding search, counting, and parity versions of these problems.

Significance. If the reductions are correct, the result establishes that the known NP-hardness for Nash-equilibrium decision problems is robust under two simultaneous, natural restrictions that are frequently studied in the literature. The explicit analysis of how GHR symmetrization interacts with the win-lose restriction supplies a reusable technical tool. The byproduct hardness statements for search, counting, and parity problems further extend the reach of the techniques.

minor comments (3)
  1. [Abstract] Abstract, line beginning 'To address the former restriction': the phrase 'a win-lose reduction' is used without a forward reference; a parenthetical citation to the section containing the gadget construction would improve readability.
  2. [Abstract] Abstract: 'accomodate' is a typographical error for 'accommodate'.
  3. [Abstract] The manuscript uses inline LaTeX markup such as {it ...} in the abstract; ensure that the final typeset version renders all mathematical terms consistently.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our results and the recommendation of minor revision. No major comments appear in the report, so we have nothing to address point by point.

Circularity Check

0 steps flagged

Reduction-based hardness proof with no circularity

full rationale

The paper proves NP-hardness of decision problems about Nash equilibria via explicit reductions: it constructs win-lose gadgets and a win-lose reduction from known hard instances, then adapts the external classical GHR-symmetrization (GHR63, 1963) while preserving 0/1 payoffs and yes/no answers. No equations, parameters, or results are defined in terms of the target claim; the central argument is a constructive reduction chain whose correctness is analyzed directly rather than by self-reference or fitting. Self-citations are absent from the load-bearing steps.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof relies on standard complexity-theoretic axioms and the correctness of the cited GHR construction; no free parameters or invented entities are introduced.

axioms (2)
  • standard math P is not equal to NP
    Implicit in any NP-hardness claim; invoked when stating that the decision problems remain NP-hard.
  • domain assumption Correctness of the classical GHR-symmetrization construction
    The paper invokes and adapts the 1963 GHR symmetrization; its validity is taken from prior literature.

pith-pipeline@v0.9.0 · 5723 in / 1227 out tokens · 24454 ms · 2026-05-24T16:26:39.593464+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Minimum Stable Cut and Treewidth

    cs.CC 2021-04 accept novelty 7.0

    The paper gives tight ETH-based lower bounds and matching algorithms for Minimum Stable Cut parameterized by treewidth and degree, plus an FPT approximation scheme for almost-stable cuts.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages · cited by 1 Pith paper

  1. [1]

    On the Complexity of Tw o-Player Win-Lose Games,

    T. Abbott, D. Kane and P. Valiant, “On the Complexity of Tw o-Player Win-Lose Games,” Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Sciences, pp. 113–122, October 2005

    work page 2005

  2. [2]

    A Polynomial Ti me Algorithm for Finding Nash Equilibria in Planar Win-Lose Games,

    L. Addario-Berry, N. Olver and A. Vetta, “A Polynomial Ti me Algorithm for Finding Nash Equilibria in Planar Win-Lose Games,” Journal of Graph Algorithms and Applications, Vol. 11, No. 1, pp. 309–319, 2007

    work page 2007

  3. [3]

    Computing Exact and Approximat e Nash Equilibria in 2-Player Games,

    V. Bil` o and A. Fanelli, “Computing Exact and Approximat e Nash Equilibria in 2-Player Games,” Proceedings of the 6th International Conference on Algorithm ic Aspects in In- formation and Management, pp. 58–69, Vol. 6124, Lecture Notes in Computer Science, Springer-Verlag, June 2010

    work page 2010

  4. [4]

    Complexity of Rational an d Irrational Nash Equilibria,

    V. Bil` o and M. Mavronicolas, “Complexity of Rational an d Irrational Nash Equilibria,” Theory of Computing Systems, Vol. 54, No. 3, pp. 491–527, April 2014

    work page 2014

  5. [5]

    A Catalog of ∃R-Complete Decision Problems about Nash Equilibria in Multi-Player Games,

    V. Bil` o and M. Mavronicolas, “A Catalog of ∃R-Complete Decision Problems about Nash Equilibria in Multi-Player Games,” Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science, Article No. 17, pp. 17:1–17:13, Vol. 47, LIPIcs, Schloss Dagstuhl - Leibniz Zentrum fuer Informatik, Februa ry 2016

    work page 2016

  6. [6]

    ∃R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games,

    V. Bil` o and M. Mavronicolas, “ ∃R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games,” Proceedings of the 34th International Sym- posium on Theoretical Aspects of Computer Science, Article No. 13, pp. 13:1–13:13, Vol. 66, LIPIcs, Schloss Dagstuhl - Leibniz Zentrum fuer Informatik , March 2017

    work page 2017

  7. [7]

    The Complexity of Un iform Nash Equilibria and Related Regular Subgraph Problems,

    V. Bonifaci, U. Di Orio and L. Laura, “The Complexity of Un iform Nash Equilibria and Related Regular Subgraph Problems,” Theoretical Computer Science, Vol. 401, Nos. 1–3, pp. 144–152, July 2008

    work page 2008

  8. [8]

    Solutions of Games by Differ ential Equations,

    G. W. Brown and J. von Neumann, “Solutions of Games by Differ ential Equations,” Con- tributions to the Theory of Games, Annals of Mathematics Stud ies, No. 24, pp. 73–79, Princeton University Press, 1950

    work page 1950

  9. [9]

    Settling the Complexity of Computing Two-Player Nash Equilibria,

    X. Chen, X. Deng and S.-H. Teng, “Settling the Complexity of Computing Two-Player Nash Equilibria,” Journal of the ACM, Vol. 56, No. 3, 2009

    work page 2009

  10. [10]

    The Approximation C omplexity of Win-Lose Games,

    X. Chen, S.-H. Teng and P. Valiant, “The Approximation C omplexity of Win-Lose Games,” Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 159– 168, January 2007. 80

    work page 2007

  11. [11]

    Efficient Comput ation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games,

    B. Codenotti, M. Leoncini and G. Resta, “Efficient Comput ation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games,” Proceedings of the 14th European Symposium on Algorithms, pp. 232–243, Vol. 4168, Lecture Notes in Computer Science, S pringer-Verlag, September 2006

    work page 2006

  12. [12]

    On the Computational Complexity of Nash Equ ilibria for (0 , 1) Bimatrix Games,

    B. Codenotti and D. ˇStefankoviˇ c, “On the Computational Complexity of Nash Equ ilibria for (0 , 1) Bimatrix Games,” Information Processing Letters, Vol. 94, No. 3, pp. 145–150, May 2005

    work page 2005

  13. [13]

    New Complexity Results ab out Nash Equilibria,

    V. Conitzer and T. Sandholm, “New Complexity Results ab out Nash Equilibria,” Games and Economic Behavior, Vol. 63, No. 2, pp. 621–641, July 2008

    work page 2008

  14. [14]

    The Complexity of Computing a Nash Equilibrium,

    C. Daskalakis, P. W. Goldberg and C. H. Papadimitriou, “ The Complexity of Computing a Nash Equilibrium,” SIAM Journal on Computing, Vol. 39, No. 1, pp. 195–259, 2009

    work page 2009

  15. [15]

    Some Tractable Win-Los e Games,

    S. Datta and N. Krishnamurthy, “Some Tractable Win-Los e Games,” Proceedings of the 8th Annual Conference on Theory and Applications of Models of Compu tation, pp. 365–376, Vol. 6648, Lecture Notes in Computer Science, Springer-Ver lag, May 2011

    work page 2011

  16. [16]

    On the Complexity of Nas h Equilibria and Other Fixed Points,

    K. Etessami and M. Yannakakis, “On the Complexity of Nas h Equilibria and Other Fixed Points,” SIAM Journal on Computing, Vol. 39, No. 6, pp. 2531–2597, 2010

    work page 2010

  17. [17]

    On Symmetric Games,

    D. Gale, H. W. Kuhn and A. W. Tucker, “On Symmetric Games, ” Contributions to the Theory of Games, Annals of Mathematics Studies, Vol. 24, Princeton Universi ty Press, pp. 81–87, 1950

    work page 1950

  18. [18]

    M. R. Garey and D. S. Johnson, Computers and Intractability — A Guide to the Theory ofNP -Completeness, W. H. Freeman & Co., 1979

    work page 1979

  19. [19]

    ETR -Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria,

    J. Garg, R. Mehta, V. V. Vazirani and S. Yazdanbov, “ ETR -Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria,” Proceedings of the 42nd Interna- tional Colloquium on Automata, Languages and Programming, pp. 554–566, Vol. 9134, Lecture Notes in Computer Science, Springer-Verlag, July 2 015

    work page

  20. [20]

    Nash and Correlated Equilibria : Some Complexity Considera- tions,

    I. Gilboa and E. Zemel, “Nash and Correlated Equilibria : Some Complexity Considera- tions,” Games and Economic Behavior, Vol. 1, No. 1, pp. 80–93, March 1989

    work page 1989

  21. [21]

    On Symmetri c Bimatrix Games,

    J. H. Griesmer, A. J. Hoffman and A. Robinson, “On Symmetri c Bimatrix Games,” IBM Research Paper RC-959, IBM Corp., T. J. Watson Research Cent er, 1963

    work page 1963

  22. [22]

    Symmetri zations of Two-Person Games,

    M. J. M. Jansen, J. A. M. Potters and S. H. Tijs, “Symmetri zations of Two-Person Games,” Methods of Operations Research, Vol. 54, pp. 385–402, 1986. 81

    work page 1986

  23. [23]

    A Symmetrization for Finite Two-Person Games,

    A. P. Jurg, M. J. M. Jansen, J. A. M. Potters and S. H. Tijs, “A Symmetrization for Finite Two-Person Games,” Methods and Models of Operations Research, Vol. 36, pp. 111–123, 1992

    work page 1992

  24. [24]

    The Complexity of Equil ibria for Risk-Modeling Valu- ations,

    M. Mavronicolas and B. Monien, “The Complexity of Equil ibria for Risk-Modeling Valu- ations,” Theoretical Computer Science, Vol. 634, pp. 67–96, June 2016

    work page 2016

  25. [25]

    Simple Complexity from Imit ation Games,

    A. McLennan and R. Tourky, “Simple Complexity from Imit ation Games,” Games and Economic Behavior, Vol. 68, No. 2, pp. 683–688, March 2010

    work page 2010

  26. [26]

    Imitation Games and Computa tion,

    A. McLennan and R. Tourky, “Imitation Games and Computa tion,” Games and Economic Behavior, Vol. 70, No. 1, pp. 4–11, September 2010

    work page 2010

  27. [27]

    On Total Functions , Existence Theorems and Computational Complexity,

    N. Megiddo and C. H. Papadimitriou, “On Total Functions , Existence Theorems and Computational Complexity,” Theoretical Computer Science, Vol. 81, pp. 317–324, April 1991

    work page 1991

  28. [28]

    Settling Som e Open Problems on 2-Player Symmetric Nash Equilibria,

    R. Mehta, V. V. Vazirani and S. Yazdanbod, “Settling Som e Open Problems on 2-Player Symmetric Nash Equilibria,” Proceedings of the 8th International Symposium on Algorith- mic Game Theory, pp. 272–284, Vol. 9347, Lecture Notes in Computer Science, S pringer- Verlag, October 2015

    work page 2015

  29. [29]

    Equilibrium Points in n-Person Games,

    J. F. Nash, “Equilibrium Points in n-Person Games,” Proceedings of the National Academy of Sciences of the United States of America, Vol. 36, pp. 48–49, 1950

    work page 1950

  30. [30]

    Non-Cooperative Games,

    J. F. Nash, “Non-Cooperative Games,” Annals of Mathematics, Vol. 54, No. 2, pp. 286–295, 1951

    work page 1951

  31. [31]

    On the Complexity of the Parity Ar gument and Other Inefficient Proofs of Existence,

    C. H. Papadimitriou, “On the Complexity of the Parity Ar gument and Other Inefficient Proofs of Existence,” Journal of Computer and System Sciences, Vol. 48, No. 3, pp. 498– 532, August 1994

    work page 1994

  32. [32]

    The Complexity of Finding Nash Eq uilibria,

    C. H. Papadimitriou, “The Complexity of Finding Nash Eq uilibria,” Chapter 2 in N. Nisan, T. Roughgarden, ´E. Tardos and V. V. Vazirani eds., Algorithmic Game Theory, pp. 29–50, Cambridge University Press, 2007

    work page 2007

  33. [33]

    Two Remarks on the Po wer of Counting,

    C. H. Papadimitriou and S. Zachos, “Two Remarks on the Po wer of Counting,” Proceedings of Theoretical Computer Science, 6th GI-Conference, pp. 269–276, Vol. 145, Lecture Notes in Computer Science, Springer-Verlag, January 1983

    work page 1983

  34. [34]

    Fixed Points, Nash Equilibria and the Existential Theory of the Reals,

    M. Schaefer and D. ˇStefankoviˇ c, “Fixed Points, Nash Equilibria and the Existential Theory of the Reals,” Theory of Computing Systems, Vol. 60, No. 2, pp. 172–193, February 2017. 82

    work page 2017

  35. [35]

    The Complexity of Computing the Permane nt,

    L. G. Valiant, “The Complexity of Computing the Permane nt,” Theoretical Computer Science, Vol. 8, No. 2, pp. 189–201, 1979

    work page 1979

  36. [36]

    Completeness for Parity Problems,

    L. G. Valiant, “Completeness for Parity Problems,” Proceedings of the 11th Annual Inter- national Conference on Computing and Combinatorics, pp. 1–8, Vol. 3595, Lecture Notes in Computer Science, Springer-Verlag, August 2005. 83

    work page 2005