2025/08/03 by Clément Bouquet, Bouquet, Clément, Salah Chikhi +5
Computer Science · Economics, Econometrics and Finance · #Artificial Intelligence in Games #Combinatorics (math.CO) #FOS: Mathematics #Game Theory and Voting Systems #Optimization and Search Problems #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2508.01737
openalex publication_date 2025/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the Levine hat problem, a cooperative puzzle introduced by Lionel Levine in 2010, in which n ≥ 2 players must simultaneously identify a black hat on their own infinite stack, each seeing only their teammates' stacks. While the optimal winning probability Vn remains unknown even for n=2, we make three key advances. First, we develop a geometric and integral framework representing strategies as Lebesgue-measurable functions, yielding a new integral expression for Vn and a unified treatment of finite and infinite stacks. Second, we construct a recursive strategy \mathscrS5 processing hats in blocks of five, which attains the conjectured optimal probability 7/20 for two players. Although this bound was already achieved by the known strategy \mathscrS3, the existence of \mathscrS5 refutes the previously held expectation that recursive strategies with block size greater than three yield no improvement, and produces a strictly better geometric convergence rate for V2,h as well as a new lower bound for V2(p) which improves known results for p < 0.312. Building upon this, we improve the geometric convergence rate of V2,h up to the near-optimal 1/41-ε for any ε > 0. Third, we introduce and completely solve a generalization of the problem where players are given uncountably infinite stacks of hats, showing that the optimal winning probability in this setting equals exactly 1/2 for all n ≥ 2. This new formulation allows to study the original combinatorial problem using tools from analytic optimization, and provides a natural framework for computing optimal responses to fixed strategies.