AFTD Auto-Formalizing Theoretical Domains

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))
See it in the graphDiscuss this resultChallenge it