A flow reduction for equilibrium uniqueness in rank-one bimatrix games
Read the paper (PDF, 9 pages) · Source and verification (tar.gz) · Zenodo record
Plain-English explanation · Read on this page · Collaboration
Abstract
For explicitly listed rational bimatrix games of variable positive dimensions and exact rank rank(A + B) = 1, deciding whether there is exactly one mixed-strategy equilibrium pair is coNP-complete. Its nonuniqueness counterpart is NP-complete. Arbitrary degeneracy is allowed. A polynomial reduction from nonempty positive-integer Partition produces a known strict pure equilibrium and an additional equilibrium exactly when the source instance admits a partition. The construction applies the signed flow counter of Disser and Skutella and the auxiliary zero-sum representation of Adsul and coauthors. A comparison-preserving rational perturbation isolates every real-demand flow optimum, an injective simplex encoding transfers diagnostic arc flow to a scalar consistency equation, and a uniform polynomial-bit exact penalty controls every auxiliary minimizer. Rational support-polytope certificates establish membership, including positive-dimensional equilibrium sets. A bounded source audit found no matching proof among the inspected bodies; worldwide priority remains unknown.
The idea in plain English
A Nash equilibrium is a pair of strategies in which neither player can improve their expected payoff by changing strategy alone. Players may randomize. In a rank-one bimatrix game, the two payoff tables have a special algebraic relationship that allows one equilibrium to be found in polynomial time.
This paper asks whether that equilibrium is the only one. It proves that deciding uniqueness is coNP-complete, while deciding whether a second equilibrium exists is NP-complete. The difficulty persists even when the input supplies a known strict pure equilibrium.
The construction turns a Partition problem into a game with a specified equilibrium. A second equilibrium exists exactly when the original integers can be split into two groups of equal total weight. This separates the task of finding one equilibrium from the task of ruling out every alternative.
The precise result
The input consists of explicitly listed rational payoff matrices A and B of variable positive dimensions, encoded in binary, with exact rank(A + B) = 1. Uniqueness concerns the entire mixed-strategy equilibrium pair, including pure strategies.
On these inputs, uniqueness is coNP-complete and nonuniqueness is NP-complete under polynomial-time many-one reductions. Arbitrary degeneracy is allowed, including positive-dimensional equilibrium sets. Hardness also holds when a known strict pure equilibrium is supplied.
For a nonempty list of n positive integers, the reduction constructs a game with (8n + 9) rows and (16n + 22) columns. Its rational entries have polynomial total binary encoding length. No partition gives exactly the specified equilibrium; a partition gives at least one additional equilibrium.
The formal languages reject malformed encodings and games whose payoff sum does not have exact rank one. The two languages are complements within the valid rank-one input class; rank-invalid inputs belong to neither.
Why the result holds
The proof starts from Disser and Skutella’s signed counting flow network. Flow through a designated bridge detects a partition. A small rational perturbation preserves the decisive comparisons while making the minimum-cost flow unique at every real demand.
An injective encoding places those flows inside a strategy simplex. A uniform exact penalty excludes infeasible minimizers, and the auxiliary zero-sum representation of Adsul and coauthors translates the bridge condition into the scalar consistency equation for a rank-one equilibrium.
The proof controls every auxiliary minimizer and every equilibrium, including degenerate cases. Rational certificates for two distinct equilibrium pairs establish membership in NP for nonuniqueness; checking input validity completes the coNP membership argument for uniqueness.
Scope and limitations
These are worst-case complexity statements. Unless P = NP, they rule out a polynomial-time algorithm for every valid input; they do not say that every particular game is difficult.
The result does not establish strong hardness, hardness at fixed dimensions, hardness under a nondegeneracy promise, or uniqueness of equilibrium payoffs. It does not classify the number of equilibria beyond one versus more than one.
Some network capacities and penalty values can be exponentially large in numerical value while retaining polynomially many bits. The reduction constructs the game directly; it does not run the potentially exponential sequence of flow augmentations.
The signed counter, auxiliary zero-sum representation, unrestricted uniqueness hardness, rational certificate ideas and perturbation methods have earlier sources. The contribution here is their quantitative connection to a diagnostic bridge and the control of the complete rank-one equilibrium set.
The bounded literature comparison does not establish worldwide priority or continued open status of the historical conjecture. The support package records the sources inspected and the remaining coverage gaps. Finite exact checks support the proof but do not prove its universal claims.
Status and AI use
AI tools were used extensively in mathematical solving, source inspection, verification and writing, including independent and adversarial AI reviews. These reviews are not conventional human journal peer review or proof-assistant verification. Journal acceptance is not claimed.
Read the paper
Open PDF in a full window · Download the original from Zenodo
Collaborate on this result
I welcome substantive collaboration on an independent mathematical review, comparison with the rank-one games and complexity literature, or preparation for journal submission. Expertise in computational game theory, network flows or exact optimization would be especially useful.
Authorship and responsibilities would be discussed in relation to the substantive contributions made.
Cite this paper
Alec Kriebel. (2026). A flow reduction for equilibrium uniqueness in rank-one bimatrix games (Version 1.0) [Preprint]. Zenodo. https://doi.org/10.5281/zenodo.23430642
Background and prior work
- Adsul, Garg, Mehta, Sohoni and von Stengel, Fast algorithms for rank-1 bimatrix games: This work supplies polynomial-time computation of one rank-one equilibrium and the auxiliary zero-sum family with its scalar consistency condition. The present paper uses that established representation.
- Disser and Skutella, The simplex algorithm is NP-mighty: The signed counting network and designated bridge are imported from this work. The journal Lemmas 3.1–3.2 are the controlling source for the flow construction.
- von Stengel, Algorithms for rank-1 bimatrix games, Oberwolfach Report 38/2018: The contribution on printed page 2332 states the historical rank-one uniqueness conjecture as joint work with Adsul, Garg, Mehta and Sohoni. This documents the question’s provenance, without certifying its present worldwide status.
- Gilboa and Zemel, Nash and correlated equilibria: some complexity considerations: Unrestricted bimatrix uniqueness was already known to be coNP-complete, with rational certificate methods. The additional requirement addressed here is exact rank one of the payoff sum.
- Erickson, Fox and Lkhamsuren, Holiest minimum-cost paths and flows in surface graphs: Earlier perturbation arguments already give unique minimum-cost flows with real capacities and demands. The present construction needs a specific rational perturbation that preserves its diagnostic comparisons.