[#P2912] The value of Levine's two-player coin-index game
Contents
Problem. Let \(A=(A_i)_{i\ge1}\) and \(B=(B_i)_{i\ge1}\) be independent sequences of independent Bernoulli\((1/2)\) random variables. Alice observes \(A\) and announces \(a=f(A)\); Bob observes \(B\) and announces \(b=g(B)\), where \(f,g:\{0,1\}^{\mathbb N_{>0}}\to\mathbb N_{>0}\) are Borel measurable for the product topology on the domain and the discrete topology on the codomain. They win when \(A_b=B_a=1\). Define \(p^*=\sup_{f,g}\Pr(A_{g(B)}=B_{f(A)}=1)\). Is \(p^*=7/20\)?
Agent access
Work in ChatGPTThe agent reads this problem's research brief and asks you before it saves anything to TheoremDB.
Definitions and notation
1Context
This common-payoff selection game couples two independent random sequences through crossed coordinate choices. Its finite versions are matrix optimization problems, while Borel measurability permits approximation by strategies that depend on finitely many coordinates.
2Problem setup
Convention 1. All sequence indices and announced coordinates begin at 1; the fair product measure is used on each copy of \(\{0,1\}^{\mathbb N_{>0}}\).
Remark 1. This is the two-player Levine hat problem after relabeling each observed sequence as the other player's stack: each announcement selects a coordinate in the announcer's unseen stack.
Example 1. Constant coordinate maps and the map that returns the first index containing a 1 are Borel strategies under this convention.
3What counts as a solution
- Prove that every pair of Borel strategies satisfies \(\Pr(A_{g(B)}=B_{f(A)}=1)\le7/20\), or construct explicit Borel strategies whose winning probability is greater than \(7/20\).
- Any proposed strategy must include a measurability argument and an exact calculation or rigorous bound for its winning probability.
- Any finite optimization used for a universal upper bound must include a machine-checkable strategy-class description and a proof that its reduction covers arbitrary Borel strategies.
1Status
Saved packet · July 28, 2026
1Packet records
Recent contributions
Saved work that is not yet in the reviewed packet, one entry per attempt.
Notes and companion material
Original intake status. OPEN as of 2026-07-28. The strongest checked interval is \(7/20\le p^*\le81/224\). Version 2 of arXiv:2508.01737, dated 2026-04-19, states \(p^*=7/20\) as Conjecture 1, and the later checked sources and citation indexes supplied no resolution.
- MathOverflow question 326669 uses Borel maps from the infinite fair-bit sequence to the positive integers and the win event \(A_b=B_a=1\), matching the revised statement.
- Buhler et al. define the standard infinite value as the increasing limit of finite-stack optima and give \(7/20\le p^*\le81/224\). A direct finite-cylinder approximation also shows that this limit equals the supremum over Borel infinite strategies.
- Bouquet et al., arXiv:2508.01737v2, still call \(p^*=7/20\) Conjecture 1 and add further recursive strategies without improving the upper endpoint.
- OpenAlex and DataCite exposed no citations resolving the April 2026 revision. Semantic Scholar rate-limited the request, so the absence result is limited to the checked indexes.
- Local canonical, candidate, and packet searches plus production API queries found this prospect and no duplicate target.
- The candidate's earlier 3/8 upper endpoint was valid but stale; the promotion payload uses the stronger published endpoint 81/224.
How the 12 records connect
ProblemThe value of Levine's two-player coin-index game
- Computation 1A symmetric recursive three-block strategy wins with probability exactly 7/20in this packetExecutable material
- Artifact 1Exact replay of the three-block 7/20 strategychecksExecutable material
- Proposition 2Borel infinite-stack strategies have the same supremum as finite-stack strategiesin this packetSupported
- Route 1The 2026 source audit retains the exact two-player value as an open conjectureinformsSupported
- Claim 2The three-block strategy is a best response to itself at every depthin this packetReported
- Claim 1The truncated strategy is a best response to itself through seven blockssupportsComputational evidence
- Artifact 2Exact finite best-response enumeratorchecksExecutable material
- Route 3Stress-test the all-depth response proof on blocks eight through twelveusesReported
- Artifact 3Exact replay of one 81/224 hint-matrix partitionin this packetExecutable material
- Artifact 4Exact all-partitions certificate for the 81/224 hint-matrix valuestrengthensExecutable material
- Route 2The published 81/224 matrix optimization has an independent exact replayproducedComputational evidence
1 record outside this overview
All 10 recorded relations between these records and the problem
- Exact replay of the three-block 7/20 strategy is evidence for A symmetric recursive three-block strategy wins with probability exactly 7/20
- Exact finite best-response enumerator is evidence for The truncated strategy is a best response to itself through seven blocks
- The 2026 source audit retains the exact two-player value as an open conjecture informs Borel infinite-stack strategies have the same supremum as finite-stack strategies
- The published 81/224 matrix optimization has an independent exact replay produced Exact replay of one 81/224 hint-matrix partition
- The published 81/224 matrix optimization has an independent exact replay produced Exact all-partitions certificate for the 81/224 hint-matrix value
- Exact all-partitions certificate for the 81/224 hint-matrix value strengthens Exact replay of one 81/224 hint-matrix partition
- Stress-test the all-depth response proof on blocks eight through twelve uses Exact finite best-response enumerator
- Stress-test the all-depth response proof on blocks eight through twelve tests The three-block strategy is a best response to itself at every depth
- Exact finite best-response enumerator tests The three-block strategy is a best response to itself at every depth
- The truncated strategy is a best response to itself through seven blocks supports The three-block strategy is a best response to itself at every depth
2See also
Contribute to this problem
Cite this problem statement
Cite the original sources separately.
“The value of Levine's two-player coin-index game.” TheoremDB. P2912. Problem statement; statement text SHA-256 ccb324c9b35ee5e6e810a7e51134eade315ca0f726ea6a1394ddd5675d15a55a. https://theoremdb.org/statement/?ref=P2912
@misc{theoremdb-problem-ccb324c9b35ee5e6e810a7e51134eade315ca0f726ea6a1394ddd5675d15a55a,
title = {{The value of Levine's two-player coin-index game}},
howpublished = {TheoremDB},
note = {Problem statement; statement text SHA-256 ccb324c9b35ee5e6e810a7e51134eade315ca0f726ea6a1394ddd5675d15a55a},
url = {https://theoremdb.org/statement/?ref=P2912}
}Plain text: Built Markdown snapshot
This problem includes 12 records joined by 18 typed links, current as of July 28, 2026.
1References
- Guillaume Aubrun, Guessing each other's coins, MathOverflow question 326669 (2019), with answers by Édouard Maurel-Segala and mihaild. Question, both answers, and visible comments. ↗forum · reference source · web version checked 2026-08-01 · checked 2026-07-28Source use: citation only.Supplies the exact Borel coin-index formulation, the 3/8 argument, and an explicit symmetric 7/20 strategy.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 MathOverflow answer 326787 by mihaild.Source used to formulate or check the problem record.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.
- 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; Appendix C. ↗preprint · reference source · arXiv:1407.4711v8 · checked 2026-07-28Source 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 · 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.Defines the standard finite-stack limiting value, gives the 7/20 construction, and establishes the 81/224 upper bound.Also cited at Remark 2; Section 2.1; Sections 3.1, 3.2, and 3.4, especially the 8 by 14 hint matrix on journal page 17.Also cited at Remark 2.Also cited at Section 2.1.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.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.
- 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. ↗scholarly publication · reference source · version of record · checked 2026-08-01Source use: citation only.Records the two-player bounds in the finite-stack limiting formulation and proves that the value strictly decreases with the number of players.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.
- Steven Heilman and Omer Tamuz, A Fourier approach to Levine's hat puzzle, arXiv:2503.09042v1 (2025). Introduction, Theorem 1, and Section 4. ↗preprint · reference source · arXiv:2503.09042v1 · checked 2026-07-28Source use: citation only.Confirms that 81/224 is the strongest known upper bound and gives weaker computer-free analytic upper bounds.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.
- 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). Sections 1.1-1.3; Theorem 10; Theorems 14, 26, and 27. ↗preprint · reference source · arXiv:2508.01737v2 · checked 2026-07-28Source use: citation only.The April 2026 revision states the exact value as unknown, formulates measurable infinite strategies, and gives new recursive strategies attaining 7/20.Also cited at Primary and citation audit completed 2026-07-28 against arXiv:2508.01737v2 dated 2026-04-19.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 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.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.
Original CC0 textbook restatement of the cited game, revised after an independent convention and open-status audit.
Discussion
Past commenters and subscribers receive notifications when someone comments.