prioritized_borel_eventually_visible_determined_positional
A determined prioritized tree game has a memoryless winner if, along every legal play, all but finitely many moves are uniquely determined by the current position and public branch direction. This permits infinitely many visible choices and makes no finite-state or uniform hidden-choice-bound assumption.
Statement
theorem prioritized_borel_eventually_visible_determined_positional {Q : Type} {k : ℕ} (G : PrioritizedBorelGame Q k) (hdet : ∃ (pl : BorelGamePlayer) (M : Type) (σ : FiniteMemoryStrategy G pl M), PrioritizedBorelStrategyWins G pl σ) (hvisible : ∀ π : ℕ → TreeGameEdge Q k, (∀ n, π n ∈ G.edges) → (π 0).source_node = [] ∧ (π 0).source_state = G.init_state → (∀ n, (π (n+1)).source_node = (π n).source_node ++ [(π n).dir] ∧ (π (n+1)).source_state = (π n).target_state) → ∃ N, ∀ n ≥ N, ∀ e ∈ G.edges, e.source_node = (π n).source_node → e.source_state = (π n).source_state → e.dir = (π n).dir → e = π n) : HasWinningStrategyInMem G 1
- Related work
- Eventual visible-choice reduction related to arXiv:2611.10136, Conjecture 19.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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…
- PrioritizedBorelStrategyWinsA strategy wins for its player if every legal play from the initial position consistent with its memory update and choices is won by that…
- HasWinningStrategyInMemThe proposition HasWinningStrategyInMem G m_bound asserts that for a prioritized Borel game G with state space Q and k priorities, there…
- TreeGameEdgeA structure TreeGameEdge (Q : Type*) (k : ℕ) representing an edge in a binary tree game arena with state space Q and k priorities, with…
- BorelGamePlayerThe two players in a prioritized Borel game, Eve and Adam.
- prioritized_borel_finite_hidden_opponent_choices_positionalFix a winning strategy in a prioritized tree game, with an arbitrary state type. Suppose that on every legal play, all but finitely many…
Read back from the Lean
For any state type Q and number of priorities k : ℕ, let G be a PrioritizedBorelGame Q k.
Assume:
1. (hdet): There exist a player pl : BorelGamePlayer (Eve or Adam), a memory type M : Type, and a strategy σ : FiniteMemoryStrategy G pl M that is winning for pl in G.
2. (hvisible): For every valid play π : ℕ → TreeGameEdge Q k (i.e. every sequence of edges in G.edges starting at node [] and state G.init_state, where each step extends the node by the chosen direction and matches the target state), there exists a threshold N : ℕ such that for all n ≥ N, any edge e ∈ G.edges with the same source_node, source_state, and dir as π n must be equal to π n (i.e. the edge is eventually uniquely determined by its source node, source state, and direction).
Then HasWinningStrategyInMem G 1: there exists a player pl, a finite memory type M with Fintype.card M ≤ 1 (a positional strategy on tree vertices List Bool × Q), and a winning strategy for pl with memory M in G.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof reduces positional determinacy to an existing result (`prioritized_borel_finite_hidden_opponent_choices_positional`), which shows that any finite-memory winning strategy can be made memoryless whenever the opponent eventually has no hidden choices along every play. By assumption, some player has a finite-memory winning strategy, and all transitions are eventually uniquely determined by the current position and direction. Because this uniqueness condition trivially eliminates hidden choices for all players, the reduction immediately provides a 1-memory winning strategy for the winning player.
Fix a winning player $pl$, a finite memory space $M$, and a winning strategy $\sigma$ with memory $M$.
From the determinacy assumption `hdet`, we unpack the winning player `pl`, their finite memory type `M`, their strategy `σ`, and the proof `hwin` that `σ` wins against all counter-strategies.
obtain ⟨pl, M, σ, hwin⟩ := hdetAlong every valid play $\pi$, for all sufficiently large $n$, either the position is owned by $pl$ or the transition is uniquely determined by the source position and direction.
Consider an arbitrary legal play $\pi$ starting at the initial state and following the tree game dynamics. By the visibility hypothesis `hvisible`, there is an index $N$ beyond which every transition from the current position in direction $(\pi\, n).\text{dir}$ is uniquely determined. This directly proves the right disjunct of the condition for all $n \ge N$.
uses
Or.inrhave hfinite : ∀ π : ℕ → TreeGameEdge Q k, (∀ n, π n ∈ G.edges) → (π 0).source_node = [] ∧ (π 0).source_state = G.init_state → (∀ n, (π (n+1)).source_node = (π n).source_node ++ [(π n).dir] ∧ (π (n+1)).source_state = (π n).target_state) → ∃ N, ∀ n ≥ N, G.owner ((π n).source_node, (π n).source_state) = pl ∨ ∀ e ∈ G.edges, e.source_node = (π n).source_node → e.source_state = (π n).source_state → e.dir = (π n).dir → e = π n := by intro π he hi hn obtain ⟨N, hN⟩ := hvisible π he hi hn exact ⟨N, fun n hn => Or.inr (hN n hn)⟩
There exists a winning strategy $\tau$ for $pl$ that uses a single memory state (`Unit`).
We apply the theorem `prioritized_borel_finite_hidden_opponent_choices_positional`, which reduces any finite-memory winning strategy to a 1-memory (positional) winning strategy whenever the opponent eventually has no hidden choices along every valid play.
uses
prioritized_borel_finite_hidden_opponent_choices_positionalobtain ⟨τ, hτ⟩ := prioritized_borel_finite_hidden_opponent_choices_positional G pl M σ hwin hfiniteThe game has a winning strategy using memory of size at most 1.
We instantiate `HasWinningStrategyInMem G 1` with player `pl`, memory type `Unit`, and winning strategy $\tau$. The cardinality requirement $|\text{Unit}| \le 1$ holds because `Unit` has exactly one element, which linear simplification verifies immediately.
exact ⟨pl, Unit, inferInstance, by simp, τ, hτ⟩
Or.inr- Constructs a proof of a disjunction $A \lor B$ from a proof of the right disjunct $B$.
prioritized_borel_finite_hidden_opponent_choices_positional- In a prioritized Borel game, if a player has a finite-memory winning strategy and along every legal play the opponent eventually has no hidden choices (every transition is either owned by that player or uniquely determined by the direction), then that player has a winning strategy with trivial memory (`Unit`).
- Positional (memoryless) strategies are formalized as finite-memory strategies over the singleton memory type `Unit`, satisfying `Fintype.card Unit ≤ 1`, which means the strategy depends only on the current game position rather than the history.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem prioritized_borel_eventually_visible_determined_positional {Q : Type} {k : ℕ} (G : PrioritizedBorelGame Q k) (hdet : ∃ (pl : BorelGamePlayer) (M : Type) (σ : FiniteMemoryStrategy G pl M), PrioritizedBorelStrategyWins G pl σ) (hvisible : ∀ π : ℕ → TreeGameEdge Q k, (∀ n, π n ∈ G.edges) → (π 0).source_node = [] ∧ (π 0).source_state = G.init_state → (∀ n, (π (n+1)).source_node = (π n).source_node ++ [(π n).dir] ∧ (π (n+1)).source_state = (π n).target_state) → ∃ N, ∀ n ≥ N, ∀ e ∈ G.edges, e.source_node = (π n).source_node → e.source_state = (π n).source_state → e.dir = (π n).dir → e = π n) : HasWinningStrategyInMem G 1 := by obtain ⟨pl, M, σ, hwin⟩ := hdet have hfinite : ∀ π : ℕ → TreeGameEdge Q k, (∀ n, π n ∈ G.edges) → (π 0).source_node = [] ∧ (π 0).source_state = G.init_state → (∀ n, (π (n+1)).source_node = (π n).source_node ++ [(π n).dir] ∧ (π (n+1)).source_state = (π n).target_state) → ∃ N, ∀ n ≥ N, G.owner ((π n).source_node, (π n).source_state) = pl ∨ ∀ e ∈ G.edges, e.source_node = (π n).source_node → e.source_state = (π n).source_state → e.dir = (π n).dir → e = π n := by intro π he hi hn obtain ⟨N, hN⟩ := hvisible π he hi hn exact ⟨N, fun n hn => Or.inr (hN n hn)⟩ obtain ⟨τ, hτ⟩ := prioritized_borel_finite_hidden_opponent_choices_positional G pl M σ hwin hfinite exact ⟨pl, Unit, inferInstance, by simp, τ, hτ⟩