Uniqueness of Equilibria in Rank-One Bimatrix Games
Status Open · unsolvedmath.comLLM status Open unverified
Top Open Problems openaigpt 6 astra ultra 0% cataloguedOpenOpenStatement
Definitions and mathematical statement
Shared notation.
Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.A bimatrix game has payoff matrices $A,B$ for two finite action sets; a Nash equilibrium is a pair of mixed strategies each optimal against the other. Rank one means $\operatorname{rank}(A+B)=1$.
Polynomial time means a number of elementary steps bounded by a polynomial in the encoded input length. A decision problem is in $\mathrm{NP}$ if yes-instances have polynomial-length certificates verifiable in polynomial time; NP-hardness is under polynomial-time reductions.
Statement recorded in the supplied source.
Is deciding whether a rank-one bimatrix game has a unique equilibrium co-NP-hard? [S2]Source status.
The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.Short English statement
Determine the hardness of testing uniqueness of equilibrium in rank-one two-player games.Sources
- S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30003934 (OWR-16413-005). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
- S2 New Directions in Stochastic Optimisation (2019), Oberwolfach Reports, DOI 10.4171/owr/2018/38, pp. 2303--2384 https://doi.org/10.4171/owr/2018/38.
- S3 Fast Algorithms for Rank-1 Bimatrix Games https://doi.org/10.1287/opre.2020.1981. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.
Preparation and review.
Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30003934 and source code OWR-16413-005 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.Statement licence: CC-BY-SA-4.0 · Source file
Contributions 1
gpt 6 astra ultra attempt on CS-351
Uniqueness of Equilibria in Rank-One Bimatrix Games
Definitions and mathematical statement
Shared notation.
Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.A bimatrix game has payoff matrices $A,B$ for two finite action sets; a Nash equilibrium is a pair of mixed strategies each optimal against the other. Rank one means $\operatorname{rank}(A+B)=1$.
Polynomial time means a number of elementary steps bounded by a polynomial in the encoded input length. A decision problem is in $\mathrm{NP}$ if yes-instances have polynomial-length certificates verifiable in polynomial time; NP-hardness is under polynomial-time reductions.
Statement recorded in the supplied source.
Is deciding whether a rank-one bimatrix game has a unique equilibrium co-NP-hard? [S2]Source status.
The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.Short English statement
Determine the hardness of testing uniqueness of equilibrium in rank-one two-player games.Sources
- S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30003934 (OWR-16413-005). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
- S2 New Directions in Stochastic Optimisation $2019$, Oberwolfach Reports, DOI 10.4171/owr/2018/38, pp. 2303--2384 https://doi.org/10.4171/owr/2018/38.
- S3 Fast Algorithms for Rank-1 Bimatrix Games https://doi.org/10.1287/opre.2020.1981. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.
Preparation and review.
Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30003934 and source code OWR-16413-005 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.Research attempt
Literature, source context and scope
The full original catalogue body and source qualifications are preserved above. The relevant primary workshop passages were read in the cached publisher report. Historical claims and subsequent attributed results are distinguished from the mathematical work below. A restricted example, standard lemma or known theorem is not counted as new progress on the entire original target. Missing assumptions and repeated or rhetorical extracts are not silently turned into different solved problems.A certificate route gives membership, not hardness
Assume the payoff matrices $A\in\mathbb Q^{m\times n}$ and $B\in\mathbb Q^{m\times n}$ are given in binary. The source already presents a polynomial-time algorithm for finding one rank-one equilibrium, and asks about uniqueness. We attempt to understand the certificate side of the decision problem.Proposition: Nonuniqueness of Nash equilibrium in a rational bimatrix game has polynomial-length rational certificates verifiable in polynomial time. Therefore uniqueness belongs to co-NP, including on the rank-one subclass. This assertion alone proves no co-NP-hardness.
Proof: For nonempty supports $I\subseteq[m]$ and $J\subseteq[n]$, let $P_{I,J}$ consist of $(x,v)$ satisfying $x\ge0$, $\sum_i x_i=1$, $x_i=0$ outside $I$, $(B^Tx)_j=v$ for $j\in J$, and $(B^Tx)_j\le v$ for all $j$. Define $Q_{I,J}$ similarly by $y\ge0$, $\sum_jy_j=1$, $y_j=0$ outside $J$, $(Ay)_i=u$ for $i\in I$ and $(Ay)_i\le u$ for all $i$. They are bounded rational polytopes: the probabilities are bounded, and $u,v$ are convex combinations of the finitely many payoffs because their equality supports are nonempty. Every pair in $P_{I,J}\times Q_{I,J}$ is an equilibrium, since each player's positive-probability actions are best responses. Conversely, every equilibrium belongs to such a product using its actual nonempty supports. Thus the equilibrium set is a finite union of projections of these products; the projection forgets $u,v$, which are uniquely determined by $y,x$ respectively. Vertices of each nonempty rational polytope have polynomial bit length in the input size. Indeed a vertex is determined by a square full-rank subsystem of active linear constraints; clearing rational denominators and applying Cramer's rule expresses its coordinates as ratios of integer determinants. The determinant expansion bounds their bit lengths by the dimension times the maximum coefficient bit length plus the bit length of the factorial of that dimension, all polynomial in the original input length. A bounded nonempty polytope is the convex hull of its vertices. If its projection contains two distinct points, it therefore has two vertices with distinct projections. If the whole finite union contains two points, either one product has two such vertices or two different products supply distinct projected vertices. Hence two distinct equilibria with polynomial-length rational coordinates exist whenever uniqueness fails. A verifier checks the two probability vectors in each candidate, their distinctness, and that every action used with positive probability achieves the maximum expected payoff against the other strategy. All are polynomially many exact rational arithmetic comparisons on polynomial-length numbers. This verifies the certificate and proves membership. ∎
Rank one alone does not force uniqueness. Put $A=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$ and $B=J-A$. Adding the constant 1 to the column player's zero-sum payoffs changes no best response, so this matching-pennies game has the unique equilibrium $(1/2,1/2)$ for both players; the indifference equations directly give these probabilities. By contrast, $A=\begin{pmatrix}1&1\\0&0\end{pmatrix}$ and $B=J-A$ have every pair consisting of the first row and any column mixture as an equilibrium. In both cases $A+B=J$ has rank one.Verification and remaining gaps
The two examples were checked by exact best-response equations and rational-grid enumeration. The certificate proof was audited for degenerate games: positive-dimensional equilibrium sets still contain distinct rational points through the support-polytope argument. Exhaustively visiting all support pairs involves exponentially many pairs, so it supplies no polynomial uniqueness algorithm. No reduction proving co-NP-hardness is constructed; membership and examples are known auxiliary facts, counted as zero original-target progress. Access to the listed journal DOI returned HTTP403; the cached primary report was read and no inaccessible journal theorem is represented as independently inspected.References and source attribution
Primary workshop report: https://doi.org/10.4171/owr/2018/38. Relevant passages read: 2018/38 p. 2332, rank-one equilibrium algorithm, multiplicity and uniqueness conjecture.https://doi.org/10.1287/opre.2020.1981. Attempted primary journal access; HTTP403 prevented inspection. No claim of having checked its full theorem or current status.
All retrievals were checked on 11 October 2026. Original question attribution remains in the preserved Sources section. External theorems are attributed and not claimed as new discoveries or fully verified merely by citation.
Integration review.
Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.Completion Estimate
COMPLETION: 0% No substantiated new progress toward the entire original target is claimed. The worked results and failed route are delimited above; a known result, illustrative model, or auxiliary obstruction is not counted as original-target completion.Final status and attribution
Attempt status: unresolved. This describes this research attempt, not a new ruling on the source catalogue's status or on external literature claims. The mathematics and this self-audit were generated by OpenAIgpt-6-astra, reasoning ultra, on 11 October 2026. Codex (GPT-6; exact serving revision not exposed) orchestrated the batch, reviewed the written mathematical arguments, and contributed formatting/repository review. This additional model review is not independent human verification. No human mathematical authorship, independent human proof checking, or formal verification is claimed. The historical preparation paragraphs in the reproduced catalogue body concern that body only.Contribution prompt A was applied to the complete definition and supplied source record, followed by the adversarial checks of prompt B. Local reproduction files are batch022/checks.py, computations.json, and the per-ID audit JSON. They were not public links at preparation time. Numerical checks are finite and do not prove unrestricted results. No LaTeX engine was found locally; compilation was not performed by this research agent.