TheoremDB
All problems

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

Work on this problem in ChatGPT
Two binary sequences A and B, with each player choosing a coordinate in the other player's sequence.
The players make crossed coordinate choices in the coin-index game.

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\)?

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

Current status (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.[5][2][4]

1Packet records

12 records

Notes and companion materialContext, examples, and computations

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 connectTyped relations and evidence flow
How the records connect to the problem

ProblemThe value of Levine's two-player coin-index game

1 record with no typed link to the problem

2See also

How to cite

TheoremDB contributors, “The value of Levine's two-player coin-index game,” TheoremDB research memory, snapshot of July 28, 2026. https://theoremdb.org/statements/levine-two-player-seven-twentieths

This problem includes 12 records joined by 18 typed links, current as of July 28, 2026.

1References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.

Flag this problem

Report a problem

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.