← All problems

The GM-rule Nash equilibrium conjecture for exact slow NIM

3 years old · traced to

Consider the exact slow game NIM(n,n−1)(n,n-1) for ℓ\ell players: a position is a non-negative nn-vector, players move cyclically, and on each move a player keeps one entry unchanged and decreases each of the other n−1n-1 positive entries by 11. A position with at least two non-positive entries is terminal; the player whose turn it is loses, and the other ℓ−1\ell-1 players share the payoff C−L(P)ℓ−1\frac{C-L(P)}{\ell-1}, where L(P)L(P) is the play length and CC exceeds the length of every play from the initial position. The GM-rule specifies a strategy for each player, including the move that keeps the largest entry when no entry is a multiple of ℓ\ell. GM-rule Nash equilibrium conjecture. The set of ℓ\ell GM-strategies forms a uniform Nash equilibrium. The claim concerns the strategic behavior induced by the GM-rule in the multiplayer exact slow NIM game; the supplied text does not state whether it has been proved or disproved.

References
  1. Vladimir Gurvich and Mariya Naumova, “GM-rule and its applications to impartial games”, arXiv:2311.03257 (2023).

Progress summary

Refreshed
Open

A reader-submitted refutation has not been independently verified, so the general conjecture remains open.

The conjecture asserts that the prescribed strategies form a uniform Nash equilibrium in the multiplayer exact slow NIM game. The 2023 published source records the conjecture but does not resolve the case of three or more players.

Known results

  • The two-player case follows from earlier results, as recorded in the 2023 source.

November 2026 community submission (unverified)

A submitted argument claims that, for n≥3n \ge 3 and ℓ≥3\ell \ge 3, an infinite family of initial positions lets one player profit by deviating from the GM strategy, thereby refuting the conjecture in that range. This claim has not received independent mathematical assessment in the retrieved sources.

Current status (as of November 2026): The two-player case is recorded as known, while the conjecture for n≥3n \ge 3 and ℓ≥3\ell \ge 3 remains open because the submitted counterexample is unverified.

Sources

Solutions 1

Conjecture 1 fails for every n >= 3 and l >= 3 (ordinary block-invariant proof; Lean certifies (4,4,5)); a computed certificate at (5,5,6) shows no completion of the no-multiple convention rescues it; l = 2 is the GMMV23 theoremSee full solutionHide full solution

For every n >= 3 piles and l >= 3 players, the paper constructs a positive initial position where all-GM play makes the first player lose but changing only that player's first move makes that player win. The proof uses the source's monetary payoff and a block invariant giving the exact play lengths. The infinite family is an ordinary proof; the Lean endpoint certifies a finite witness. This same conjecture also appears as MathDB 361128. The two-player theorem is not contradicted.

Result and scope: Conjecture 1 fails for every n >= 3 and l >= 3 (ordinary block-invariant proof; Lean certifies (4,4,5)); a computed certificate at (5,5,6) shows no completion of the no-multiple convention rescues it; l = 2 is the GMMV23 theorem

Complete proof and verification sources: GM strategies are not a Nash equilibrium in l-player exact slow NIM(n, n-1) for n, l >= 3: a refutation of Gurvich-Naumova Conjecture 1 (arXiv:2311.03257) · PDF.

The paper page includes the supplementary proof-source JSON attachment and extract_sources.py, which reconstruct the archived proof and verification sources. The linked paper gives the complete rigorous argument and specifies exactly which statements are formalized.

This is an AI-assisted research preprint. Internal review is not external journal peer review; bounded prior-art searches do not certify worldwide priority. See the paper for the source, interpretation, formalization, and trust limitations.