HasWinningStrategyInMem
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
- prioritized_borel_eventually_visible_determined_positionalA determined prioritized tree game has a memoryless winner if, along every legal play, all but finitely many moves are uniquely determined…
- prioritized_borel_fork_all_winning_memorylessThe all-winning fork game has a winning strategy using one memory state.
- has_winning_strategy_in_mem_monoIn any prioritized Borel game G with k priorities on state space Q, if a player has a winning strategy using at most m1 memory states, and…
- prioritized_borel_deterministic_opponent_memorylessIf every position controlled by Adam in a prioritized Borel game has at most one legal outgoing edge, then one of the players has a…
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