spr_value
def
The minimax value of the sign-preservation-with-reuse game with r rounds left from a given board: the pointer (maximizer) may stop or select an empty cell j; the labeler (minimizer) then removes any subset of the minus signs to the left of j and the plus signs to the right of j and places a plus or minus in j; the game ends when the pointer stops, the rounds run out, or no cell is empty, and the payoff is the number of signs on the board.
Statement
def spr_value (n : ℕ) : ℕ → (Fin n → Option Bool) → ℕ- Defined in
- arXiv:2610.07623 (Explicit asymptotic bounds for sequential calibration beyond T^{2/3}), Sec. 2.2 (the game is one of perfect information, so the value with randomized strategies equals this pure minimax value)
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 2
- spr_sign_countThe number of signs on a board of the sign-preservation-with-reuse game with n cells, each empty or holding a plus or a minus.
- spr_moveThe board after the labeler empties the cells of a set R and places the sign s in the selected cell j.
- Used by 5
- spr_opt_capacity_leFor every integer k ≥ 1, board size n ∈ {2k - 1, 2k}, and horizon t, the sign-preservation-with-reuse minimax value satisfies spr_opt n t…
- spr_minimax_sign_deletion_monotonicityIn the sign-preservation-with-reuse game, the minimax value is monotone under adding existing signs: for every number n of ordered cells,…
- spr_minimax_sign_deletion_monotonicity_two_twoOn two cells with horizon two, the minimax value is monotone under sign deletion: for any boards b, b' : Fin 2 → Option Bool with…
- spr_value_zero_monoAt horizon 0, the sign-preservation-with-reuse game value equals the sign count, which is monotone under sign deletion: if b' is a…
- spr_optopt(n, t): the number of signs remaining at the end of the sign-preservation-with-reuse game with n cells and at most t rounds, under…
Lean source view module on GitHub
/-- Value of the sign-preservation-with-reuse game with `r` rounds left from board `b`, under optimal play: the pointer (maximizer) may stop, or select an empty cell `j`; the labeler (minimizer) then empties any legal set `R` (minus signs left of `j`, plus signs right of `j`) and places a sign in `j`. The game ends when the pointer stops, no rounds are left, or no cell is empty; the payoff is the number of signs on the board. -/ def spr_value (n : ℕ) : ℕ → (Fin n → Option Bool) → ℕ := fun | 0, b => spr_sign_count b | r + 1, b => max (spr_sign_count b) ((Finset.univ.filter fun j => b j = none).sup fun j => ((Finset.univ : Finset (Finset (Fin n) × Bool)).filter fun p => ∀ i ∈ p.1, (i < j ∧ b i = some false) ∨ (j < i ∧ b i = some true)).inf' ⟨(∅, true), Finset.mem_filter.2 ⟨Finset.mem_univ _, fun i hi => absurd hi (Finset.notMem_empty i)⟩⟩ fun p => spr_value n r (spr_move b j p.1 p.2))