# P2912: The value of Levine's two-player coin-index game

- ID: `P2912`
- Reference: `levine-two-player-seven-twentieths`
- Page: https://theoremdb.org/statements/P2912
- Record maturity: Reviewed problem with recorded work

## Problem

Alice and Bob receive independent infinite sequences \(A=(A_i)_{i\ge1}\) and \(B=(B_i)_{i\ge1}\) of fair bits. After seeing only her own sequence, Alice chooses an index \(a\); Bob similarly chooses \(b\). They win when \(A_b=B_a=1\). Is the supremum winning probability over all Borel strategies equal to \(7/20\)?

### Definitions

- **Definition.** A strategy is a Borel measurable map from {0,1}^N to the positive integers; Alice's and Bob's strategies may differ.
- **Definition.** The game value is the supremum of Pr(A_b=1 and B_a=1) over pairs of such strategies, with A and B independent product measures.

### What counts as a solution

- Construct Borel strategies winning with probability greater than 7/20, or prove that every pair of Borel strategies wins with probability at most 7/20.
- Any finite optimization used in an upper bound must include a machine-checkable description of the strategy class and a proof that the reduction covers arbitrary Borel strategies.

## Status

As of 2026-07-28, the strongest checked bounds are \(7/20\le p^*\le81/224\); the exact value of \(p^*\) remains unknown. [2](#reference-2) [3](#reference-3) [4](#reference-4)

## Work

### Evidence for the current status

**Proposition 1 (The checked interval is 7/20 through 81/224, and equality at 7/20 remains open).** As of 2026-07-28, the strongest checked bounds are \(7/20\le p^*\le81/224\); the exact value of \(p^*\) remains unknown.

For the Borel-strategy value \(p^*\) in the canonical statement, the checked literature gives
\[
\frac{7}{20}\le p^*\le\frac{81}{224}=0.361607142857\ldots.
\]
The lower endpoint is attained by recursive block strategies. Buhler and coauthors derive the upper endpoint using a balanced \(8\times14\) hint matrix and an exhaustive optimization over column partitions. An independent exact replay prepared for this packet enumerates all \(B_{14}=190{,}899{,}322\) column partitions, obtains maximum \(81/224\), and recovers the reported count of 3,920 attaining partitions. Bouquet and coauthors, in arXiv:2508.01737v2 dated 2026-04-19, still state \(p^*=7/20\) as Conjecture 1. Heilman and Tamuz also identify \(81/224\) as the best known upper bound; their analytic bound \(0.37193\) is weaker.

The exact open remainder is to prove \(p^*\le7/20\), or to construct Borel strategies with winning probability greater than \(7/20\). The older interval ending at \(3/8\) is valid but no longer strongest.

### Background and intake notes

Finite strategy tables, symmetry reductions, and dual certificates for upper bounds can be combined across attempts. The gap between 0.35 and 0.375 is small enough for exact finite relaxations to provide useful intermediate results.

- Original intake status: UNKNOWN as of 2026-07-27. The source gives a 7/20 strategy and a 3/8 upper bound. Version 2 of arXiv:2508.01737, dated 2026-04-19, explicitly says the exact value remains unknown and records 7/20 as the conjectured value.
- The MathOverflow question, its two answers, and every visible comment were checked on 2026-07-27. Together they establish 7/20<=p*<=3/8, without closing the gap.
- Version 2 of arXiv:2508.01737 was checked on 2026-07-27. It treats finite and infinite variants, states that the exact infinite-game value is unknown, and identifies 7/20 as the conjectured answer.
- The earlier arXiv:1407.4711 was checked for the original game and its measurable-strategy setup. Its results do not improve the upper bound to 7/20.
- A local corpus search for Levine coin game, guessing coins, 7/20, and two-player index strategies found no duplicate.

- Recorded example: The construction in the MathOverflow answers attains winning probability 7/20, so any upper bound below that value would contradict an explicit strategy.

### Other known results

- **Computation 1** (reproduced): The first-nonmonochromatic three-block strategy attains \(7/20\), giving the current lower bound for the Borel game. [1](#reference-1) [3](#reference-3)
- **Proposition 2** (supported): The supremum over Borel strategies equals the increasing limit of the finite-stack optima, so the coin formulation and the standard Levine value use the same convention. [2](#reference-2) [3](#reference-3)
- **Claim 1** (reproduced): For every truncation with \(1\le m\le7\), exact enumeration finds no unilateral deterministic improvement over the symmetric three-block strategy.
- **Claim 2** (reported): For every finite truncation, and for the infinite Borel strategy, no unilateral strategy change improves the winning probability against the fixed symmetric three-block strategy. [2](#reference-2)

### Prior approaches

- **Route 1** (supported): A dated audit found the April 2026 primary revision, no later checked resolution, and no second TheoremDB target for the same Borel two-player game. [2](#reference-2) [1](#reference-1) [3](#reference-3) [5](#reference-5) [4](#reference-4)
- **Route 2** (reproduced): A full set-partition enumeration now certifies the displayed hint matrix's value as \(81/224\) and matches the reported count of 3,920 maximizers. [3](#reference-3)

### Open directions

- **Route 3** (reported): Implement a block recurrence or symmetry quotient that independently checks the all-depth response formula for \(8\le m\le12\) without traversing all \(2^{3m+1}\) observed strings.

### Runnable artifacts

- **Artifact 1** (reproduced): A standard-library Python replay finds 15 winning local pairs out of 36 and verifies the finite formula \(7/20-1/(10\cdot16^m)\) for \(1\le m\le12\).
- **Artifact 2** (reproduced): A Gray-code integer enumerator checks 4,793,488 observed strings across seven truncations, returns zero best-response excess, and checks the depth-independent local score matrix.
- **Artifact 3** (reproduced): A deterministic replay checks all 16 colorings of one four-class partition and obtains conditional matrix-game value \(81/224\). [3](#reference-3)
- **Artifact 4** (reproduced): An exact C++ replay enumerates all 190,899,322 partitions of fourteen columns, finds maximum \(81/224\), and recovers all 3,920 reported attaining partitions. [3](#reference-3)

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `levine-two-player-seven-twentieths`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Guillaume Aubrun, Guessing each other's coins, MathOverflow question 326669 (2019), with answers by Édouard Maurel-Segala and mihaild. Question 326669, both answers, and every visible comment were checked on 2026-07-27. https://mathoverflow.net/questions/326669/guessing-each-others-coins
   - Also cited at Question 326669, both answers, and visible comments; current primary literature checked through 2026-07-28.
   - Also cited at Question and answer 326787
   - Also cited at Question, both answers, and visible comments
   - Also cited at MathOverflow answer 326787 by mihaild
   - forum; reference source; web version checked 2026-08-01; checked 2026-07-28
   - Source use: citation_only
   - Source used to assess the problem's recorded status.
   - Source used to assess the problem's recorded status.
   - For The value of Levine's two-player coin-index game: The first-nonmonochromatic three-block strategy attains \(7/20\), giving the current lower bound for the Borel game.
   - Gives the exact coin-index formulation and the symmetric three-block strategy used in this claim.
   - Supplies the exact Borel coin-index formulation, a 3/8 upper-bound argument, and the explicit 7/20 strategy.
2. <a id="reference-2"></a>Clément Bouquet, Salah Chikhi, Timothé Charles, Yanghao Zhou, and Eric Wang, An analytical framework for the Levine hats problem: new strategies, bounds and generalizations, arXiv:2508.01737v2 (2025). Primary and citation audit completed 2026-07-28 against arXiv:2508.01737v2 dated 2026-04-19 https://arxiv.org/abs/2508.01737
   - Also cited at Sections 1.1-1.3 and Conjecture 1
   - Also cited at Sections 2.1-2.2, Lemmas 6-9, and Theorem 10
   - Also cited at Section 4.5, especially Theorem 36 and Proposition 37
   - Also cited at Sections 1.1-1.3; Theorem 10; Theorems 14, 26, and 27
   - Also cited at Bouquet et al., Sections 1.1-1.3 and Conjecture 1, checked 2026-07-28
   - Also cited at Bouquet et al., Sections 2.1-2.2, Lemmas 6-9, and Theorem 10
   - Also cited at Bouquet et al., Section 4.5, especially Theorem 36 and Proposition 37
   - preprint; reference source; arXiv source revision v2; checked 2026-07-28
   - Source use: citation_only
   - Source used to assess the problem's recorded status.
   - For The value of Levine's two-player coin-index game: The supremum over Borel strategies equals the increasing limit of the finite-stack optima, so the coin formulation and the standard Levine value use the same convention.
   - The April 2026 revision states that the two-player optimum remains unknown and records 7/20 and 81/224 as the current endpoints.
   - States the measurable infinite-strategy formulation and its equality with the finite-stack limit.
   - Develops the general optimal-response calculation and applies it to the first-black-hat strategy; the packet specializes the calculation to the three-block strategy.
   - Provides the current open-status statement, measurable-strategy framework, another 7/20 strategy, and an infinite family of recursive lower-bound strategies.
3. <a id="reference-3"></a>Joe Buhler, Chris Freiling, Ron Graham, Jonathan Kariv, James R. Roche, Mark Tiefenbruck, Clint Van Alten, and Dmytro Yeroshkin, On Levine's notorious hat puzzle, arXiv:1407.4711v8 (2014). Remark 2; Section 2.1; Sections 3.1, 3.2, and 3.4, especially the 8 by 14 hint matrix on journal page 17 https://arxiv.org/abs/1407.4711
   - Also cited at Remark 2
   - Also cited at Section 2.1
   - Also cited at Remark 2; Section 2.1; Sections 3.1, 3.2, and 3.4; Appendix C
   - Also cited at Sections 3.1 and 3.2, especially the 8 by 14 hint matrix on journal page 17
   - Also cited at Sections 3.1, 3.2, and 3.4, especially the 8 by 14 hint matrix on journal page 17
   - Also cited at Buhler et al., Sections 3.1, 3.2, and 3.4
   - Also cited at Buhler et al., Sections 3.1 and 3.2, especially the matrix on journal page 17
   - Also cited at Buhler et al., Sections 3.1, 3.2, and 3.4, especially the 8 by 14 matrix on journal page 17
   - preprint; reference source; arXiv source revision v8; checked 2026-07-28
   - Source use: citation_only
   - Reused material: The 8 by 14 binary hint matrix transcribed as the replay input.
   - Reuse basis: licensed; rights holder: Joe Buhler, Chris Freiling, Ron Graham, Jonathan Kariv, James R. Roche, Mark Tiefenbruck, Clint Van Alten, and Dmytro Yeroshkin; CC-BY-4.0; https://creativecommons.org/licenses/by/4.0/; checked 2026-07-28; by TheoremDB agent session
   - Required attribution: The authors and INTEGERS article are cited in this reference row and in the artifact body.
   - Source used to assess the problem's recorded status.
   - For The value of Levine's two-player coin-index game: Source of the 81/224 upper bound, the displayed balanced matrix, and the reported partition count.
   - Defines the finite-stack limiting value, proves the 7/20 lower bound, and gives the 81/224 upper bound.
   - Defines the standard infinite-stack value as the limit of finite games and distinguishes it from unrestricted nonmeasurable play.
   - Derives the 7/20 value for recursive three-block play and discusses equivalent local strategies.
   - Defines the standard finite-stack limit, gives the 7/20 strategy, and proves the 81/224 upper bound.
   - Defines the matrix game, prints the balanced matrix, and reports its maximum value as 81/224.
   - Defines the matrix game and its upper-bound interpretation, prints the balanced matrix, and reports maximum 81/224 with 3,920 attaining partitions.
   - Source of the 81/224 upper bound, the displayed balanced matrix, and the reported partition count.
4. <a id="reference-4"></a>Steven Heilman and Omer Tamuz, A Fourier approach to Levine's hat puzzle, arXiv:2503.09042v1 (2025). Introduction, Theorem 1, and Section 4 https://arxiv.org/abs/2503.09042
   - preprint; primary source; arXiv:2503.09042v1; checked 2026-08-01
   - Source use: original_summary
   - For The value of Levine's two-player coin-index game: Independently identifies 81/224 as the best known upper bound and gives weaker computer-free upper bounds.
   - Independently identifies 81/224 as the best known upper bound and gives weaker computer-free upper bounds.
   - Confirms that 81/224 remains the strongest known upper bound and develops weaker analytic upper bounds.
5. <a id="reference-5"></a>Noga Alon, Ehud Friedgut, Gil Kalai, and Guy Kindler, The Success Probability in Levine's Hat Problem, and Independent Sets in Graphs, SIAM Journal on Discrete Mathematics 37(4) (2023), 2717-2729. Introduction and Theorem 1.2 https://doi.org/10.1137/22M1515975
   - journal_article; primary source; version of record; checked 2026-08-01
   - Source use: original_summary
   - For The value of Levine's two-player coin-index game: Uses the finite-stack limiting formulation, records the two-player interval, and proves strict decrease as the number of players grows.
   - Uses the finite-stack limiting formulation, records the two-player interval, and proves strict decrease as the number of players grows.