AFTD Auto-Formalizing Theoretical Domains

HasWinningStrategyInMem

def

The proposition HasWinningStrategyInMem G m_bound asserts that for a prioritized Borel game G with state space Q and k priorities, there exists a player pl : BorelGamePlayer and a finite memory type M with Fintype.card M ≤ m_bound, having a strategy strat : FiniteMemoryStrategy G pl M such that for every valid play (an infinite sequence of edges starting at ([], G.init_state) with matching consecutive source and target nodes and states) consistent with strat, pl wins: if pl = Eve, the branch traced by the play belongs to the winning set G.winning_sets p for the maximal priority p : Fin k occurring infinitely often; if pl = Adam, this condition fails.

Statement

def HasWinningStrategyInMem {Q : Type*} {k : ℕ} (G : PrioritizedBorelGame Q k) (m_bound : ℕ) : Prop
Defined in
arXiv:2611.10136, Def. 18 and Sec. 5.1
Verified
10 Nov 2026
Axioms
none listed
Built on 4
  • BorelGamePlayerThe two players in a prioritized Borel game, Eve and Adam.
  • TreeGameEdgeA structure TreeGameEdge (Q : Type*) (k : ℕ) representing an edge in a binary tree game arena with state space Q and k priorities, with…
  • PrioritizedBorelGameA structure PrioritizedBorelGame (Q : Type*) (k : ℕ) representing a prioritized Borel game with state space Q and k priorities, with…
  • FiniteMemoryStrategyA structure FiniteMemoryStrategy {Q : Type*} {k : ℕ} (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (M : Type*) representing a…
Used by 4

Read back from the Lean

Given a state space Q, a natural number k, a prioritized Borel game G : PrioritizedBorelGame Q k, and a natural number memory bound m_bound, HasWinningStrategyInMem G m_bound asserts that: There exist: 1. a player pl : BorelGamePlayer (either BorelGamePlayer.Eve or BorelGamePlayer.Adam), 2. a memory type M : Type equipped with a Fintype M instance such that Fintype.card M ≤ m_bound, and 3. a finite-memory strategy strat : FiniteMemoryStrategy G pl M for player pl, such that for every play (a sequence of edges play : ℕ → TreeGameEdge Q k), if: 1. every edge belongs to G.edges (∀ n, play n ∈ G.edges), 2. the initial edge starts at the root node [] and initial state G.init_state ((play 0).source_node = [] ∧ (play 0).source_state = G.init_state), 3. consecutive edges follow tree transitions: for each n, (play (n + 1)).source_node = (play n).source_node ++ [(play n).dir] and (play (n + 1)).source_state = (play n).target_state, and 4. the play is consistent with strat: there exists a sequence of memory states mem : ℕ → M such that mem 0 = strat.init_mem, mem (n + 1) = strat.update (mem n) (play n) for all n, and whenever the position ((play n).source_node, (play n).source_state) is owned by pl (G.owner ... = pl), the edge chosen is play n = strat.choice (mem n) (play n).source_node (play n).source_state, then: - if pl = BorelGamePlayer.Eve: there exists a priority p : Fin k such that: - (play n).prio = p holds for infinitely many n (Filter.Frequently (fun n => (play n).prio = p) Filter.atTop), - for all q : Fin k with p < q, (play n).prio = q holds for only finitely many n (does not hold frequently), and - the sequence of directions (fun n => (play n).dir) : ℕ → Bool belongs to G.winning_sets p. - if pl = BorelGamePlayer.Adam: the negation of Eve's winning condition holds: there does not exist any p : Fin k satisfying the three conditions above.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Predicate that a prioritized Borel game has a winning strategy with at most m_bound memory states. -/
def HasWinningStrategyInMem {Q : Type*} {k : ℕ} (G : PrioritizedBorelGame Q k) (m_bound : ℕ) : Prop := ∃ (pl : BorelGamePlayer) (M : Type) (_ : Fintype M),
    Fintype.card M ≤ m_bound ∧
    ∃ strat : FiniteMemoryStrategy G pl M,
      ∀ play : ℕ → TreeGameEdge Q k,
        (∀ n, play n ∈ G.edges) →
        (play 0).source_node = [] ∧ (play 0).source_state = G.init_state →
        (∀ n, (play (n + 1)).source_node = (play n).source_node ++ [(play n).dir] ∧
              (play (n + 1)).source_state = (play n).target_state) →
        (∃ mem : ℕ → M, mem 0 = strat.init_mem ∧
          (∀ n, mem (n + 1) = strat.update (mem n) (play n)) ∧
          (∀ n, G.owner ((play n).source_node, (play n).source_state) = pl →
            play n = strat.choice (mem n) (play n).source_node (play n).source_state)) →
        match pl with
        | BorelGamePlayer.Eve =>
            ∃ p : Fin k,
              (Filter.Frequently (fun n => (play n).prio = p) Filter.atTop) ∧
              (∀ q : Fin k, p < q → ¬ Filter.Frequently (fun n => (play n).prio = q) Filter.atTop) ∧
              (fun n => (play n).dir) ∈ G.winning_sets p
        | BorelGamePlayer.Adam =>
            ¬ ∃ p : Fin k,
              (Filter.Frequently (fun n => (play n).prio = p) Filter.atTop) ∧
              (∀ q : Fin k, p < q → ¬ Filter.Frequently (fun n => (play n).prio = q) Filter.atTop) ∧
              (fun n => (play n).dir) ∈ G.winning_sets p
See it in the graphDiscuss this resultChallenge it