prioritized_borel_bounded_opponent_branching_compression
Fix a winning strategy, possibly using infinite memory, in a finite-state prioritized tree game with k priorities. If along every legal play the opponent has a genuine choice at at most d positions, then the same player has a winning strategy with at most (2k|Q|+1)^d memory states. This construction does not use Borel determinacy and works for any branch-winning sets.
Statement
theorem prioritized_borel_bounded_opponent_branching_compression {Q : Type} [Fintype Q] {k : ℕ} (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (M : Type) (σ : FiniteMemoryStrategy G pl M) (hwin : PrioritizedBorelStrategyWins G pl σ) (d : ℕ) (hbounded : ∀ π : ℕ → 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, Set.ncard {j : ℕ | j < N ∧ G.owner ((π j).source_node, (π j).source_state) ≠ pl ∧ ∃ e ∈ G.edges, e.source_node = (π j).source_node ∧ e.source_state = (π j).source_state ∧ e ≠ π j} ≤ d) : ∃ (M' : Type) (_ : Fintype M'), Fintype.card M' ≤ (2 * k * Fintype.card Q + 1) ^ d ∧ ∃ τ : FiniteMemoryStrategy G pl M', PrioritizedBorelStrategyWins G pl τ
- Related work
- Bounded-adversary-branching strategy compression related to arXiv:2611.10136, Conjecture 19.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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…
- 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_record_replayA compatible finite history can be reconstructed from its length and the sequence of choices at opponent-controlled branching positions.
- prioritized_borel_record_injectiveCompatible finite histories with equal length and equal records of opponent branching choices are identical.
- prioritized_borel_outgoing_edge_card_boundAt any fixed position in a finite-state game with k priorities there are at most 2k times the number of states legal outgoing edges.
- 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
Given:
- a finite type of game states Q,
- a number of priorities k : ℕ,
- a prioritized Borel game G over states Q with k priorities,
- a player pl : BorelGamePlayer (either Eve or Adam),
- a memory type M and a strategy σ for pl with memory M,
- a proof hwin that σ is a winning strategy for pl in G, and
- a natural number d : ℕ such that (hbounded): for every valid play π : ℕ → TreeGameEdge Q k in G (meaning: every edge is in G.edges, the initial edge starts at the empty tree node [] and G.init_state, and each step moves to the child node determined by dir and the target state), and for every natural number N, the number of indices j < N at which the vertex is owned by the opponent (G.owner ≠ pl) and has an alternative outgoing edge in G.edges different from π j is at most d.
Then:
There exists a type M' and a Fintype M' instance such that:
1. Fintype.card M' ≤ (2 * k * Fintype.card Q + 1) ^ d, and
2. There exists a strategy τ for player pl with memory M' such that τ is a winning strategy for pl 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
To compress a winning strategy when the opponent has genuine branching choices at at most d positions along every legal play, the proof shows that the opponent choices along any play are in particular finite. By a pigeonhole contradiction against the prefix bound d, any play's set of opponent branching points must be bounded by some cutoff N. Applying the known result prioritized_borel_finite_hidden_opponent_choices_positional then yields a winning positional strategy with trivial memory Unit (size 1), which trivially satisfies the bound 1 ≤ (2k|Q| + 1)^d.
For any legal play π, the set S of time steps where the opponent owns the position and has an alternative outgoing edge has at most d elements in any initial prefix of length N.
We enable classical logic and consider an arbitrary valid play π starting from the initial state at the empty tree node. Let S be the set of steps j where the opponent owns the node and state and there exists an alternative outgoing edge in G distinct from π(j). By the assumption hbounded, the number of such steps j < N is at most d for any prefix length N.
classical 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 π h1 h2 h3 let S := {j : ℕ | G.owner ((π j).source_node, (π j).source_state) ≠ pl ∧ ∃ e ∈ G.edges, e.source_node = (π j).source_node ∧ e.source_state = (π j).source_state ∧ e ≠ π j} have hS : ∀ N, Set.ncard {j : ℕ | j < N ∧ j ∈ S} ≤ d := by intro N have : {j : ℕ | j < N ∧ j ∈ S} = {j : ℕ | j < N ∧ G.owner ((π j).source_node, (π j).source_state) ≠ pl ∧ ∃ e ∈ G.edges, e.source_node = (π j).source_node ∧ e.source_state = (π j).source_state ∧ e ≠ π j} := by ext j; simp [S] rw [this] exact hbounded π h1 h2 h3 N
The set S of opponent choice points along π is bounded above, so all its elements are strictly less than some cutoff N.
Assume for contradiction that no such upper bound N exists. Then S must be infinite, because any finite set of natural numbers is bounded above by its maximum. An infinite subset of ℕ contains a finite subset t of size d + 1. Setting N = max(t) + 1, all elements of t are strictly less than N, so t ⊆ {j < N | j ∈ S}. Since this set is a subset of [0, N), it is finite, and its cardinality must be at least |t| = d + 1. But by the prefix bound from the previous step, its cardinality is at most d, yielding d + 1 ≤ d, a contradiction.
uses
Finset.le_sup,Set.Finite.subset,Set.finite_Iio,Set.ncard_le_ncard,Set.ncard_coe_finsethave hN_ex : ∃ N, ∀ n ≥ N, n ∉ S := by by_contra hc have hinf : S.Infinite := by intro hfin have hb := hfin.bddAbove obtain ⟨B, hB⟩ := hb apply hc refine ⟨B + 1, ?_⟩ intro n hn hnS have := hB hnS omega obtain ⟨t, htS, htcard⟩ := hinf.exists_subset_card_eq (d + 1) let N := t.sup id + 1 have hsub : (t : Set ℕ) ⊆ {j : ℕ | j < N ∧ j ∈ S} := by intro x hx refine ⟨?_, htS hx⟩ have : id x ≤ t.sup id := Finset.le_sup hx dsimp [id] at this omega have hfinN : Set.Finite {j : ℕ | j < N ∧ j ∈ S} := by apply Set.Finite.subset (Set.finite_Iio N) intro x hx exact hx.1 have hcard := Set.ncard_le_ncard hsub hfinN rw [Set.ncard_coe_finset, htcard] at hcard have hN := hS N omega
Beyond step N along the play π, the opponent never has a genuine branching choice: either player pl owns the position, or the play edge π(n) is the unique outgoing edge.
Using the threshold N where no n ≥ N belongs to S, we consider any step n ≥ N. If player pl owns the vertex, the disjunction holds immediately. Otherwise, if the opponent owns it, suppose there is an outgoing edge e from the same node and state. If e ≠ π(n), then n would belong to S, contradicting n ∉ S. Thus e must equal π(n), meaning the opponent has no alternative choice.
uses
Or.inlobtain ⟨N, hN⟩ := hN_ex refine ⟨N, ?_⟩ intro n hn have hnot := hN n hn dsimp [S] at hnot by_cases ho : G.owner ((π n).source_node, (π n).source_state) = pl · exact Or.inl ho · right intro e he hsn hss hdir by_contra hne apply hnot exact ⟨ho, ⟨e, he, hsn, hss, hne⟩⟩
Player pl has a winning positional (memory Unit) strategy τ.
Having shown that the opponent has genuine branching choices only finitely many times along any legal play, we invoke the lemma prioritized_borel_finite_hidden_opponent_choices_positional. This simplifies the winning finite-memory strategy σ into a winning positional strategy τ whose memory type is the singleton type Unit.
uses
prioritized_borel_finite_hidden_opponent_choices_positionalobtain ⟨τ, hτ⟩ := prioritized_borel_finite_hidden_opponent_choices_positional G pl M σ hwin hfiniteThe positional strategy τ satisfies the memory size bound |Unit| ≤ (2k|Q| + 1)^d.
The memory type Unit has cardinality 1 by Fintype.card_unit. Since 2k|Q| + 1 ≥ 1, any power (2k|Q| + 1)^d is at least 1 by Nat.one_le_pow. Therefore, the memory bound 1 ≤ (2k|Q| + 1)^d holds, concluding the proof.
uses
Fintype.card_unit,Nat.one_le_powrefine ⟨Unit, inferInstance, ?_, ⟨τ, hτ⟩⟩ simp only [Fintype.card_unit] have : 1 ≤ 2 * k * Fintype.card Q + 1 := by omega exact Nat.one_le_pow d (2 * k * Fintype.card Q + 1) this
Finset.le_sup- Any element b in a finite set s satisfies f(b) ≤ s.sup f under a suitable order.
Fintype.card_unit- The cardinality of the singleton type Unit is 1.
Nat.one_le_pow- For any natural numbers n and m with m > 0, 1 ≤ m^n.
Or.inl- From a proof of A, deduces the disjunction A ∨ B.
Set.Finite.subset- A subset of a finite set is finite.
Set.finite_Iio- The set of natural numbers strictly less than a is finite.
Set.ncard_coe_finset- The cardinality (Set.ncard) of a finset coerced to a set equals its Finset.card.
Set.ncard_le_ncard- If s ⊆ t and t is finite, then |s| ≤ |t| (in terms of Set.ncard).
prioritized_borel_finite_hidden_opponent_choices_positional- In a prioritized Borel game, if along every legal play the opponent has genuine branching choices at only finitely many steps, then any winning strategy can be replaced by a winning positional (memory Unit) strategy.
- Although the theorem statement establishes an upper bound of (2k|Q| + 1)^d memory states (which suggests a tree-tracking compression scheme of depth d), the Lean proof actually constructs a positional strategy with memory Unit, having size 1. The bound 1 ≤ (2k|Q| + 1)^d is then satisfied trivially since the base is at least 1.
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_bounded_opponent_branching_compression {Q : Type} [Fintype Q] {k : ℕ} (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (M : Type) (σ : FiniteMemoryStrategy G pl M) (hwin : PrioritizedBorelStrategyWins G pl σ) (d : ℕ) (hbounded : ∀ π : ℕ → 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, Set.ncard {j : ℕ | j < N ∧ G.owner ((π j).source_node, (π j).source_state) ≠ pl ∧ ∃ e ∈ G.edges, e.source_node = (π j).source_node ∧ e.source_state = (π j).source_state ∧ e ≠ π j} ≤ d) : ∃ (M' : Type) (_ : Fintype M'), Fintype.card M' ≤ (2 * k * Fintype.card Q + 1) ^ d ∧ ∃ τ : FiniteMemoryStrategy G pl M', PrioritizedBorelStrategyWins G pl τ := by classical 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 π h1 h2 h3 let S := {j : ℕ | G.owner ((π j).source_node, (π j).source_state) ≠ pl ∧ ∃ e ∈ G.edges, e.source_node = (π j).source_node ∧ e.source_state = (π j).source_state ∧ e ≠ π j} have hS : ∀ N, Set.ncard {j : ℕ | j < N ∧ j ∈ S} ≤ d := by intro N have : {j : ℕ | j < N ∧ j ∈ S} = {j : ℕ | j < N ∧ G.owner ((π j).source_node, (π j).source_state) ≠ pl ∧ ∃ e ∈ G.edges, e.source_node = (π j).source_node ∧ e.source_state = (π j).source_state ∧ e ≠ π j} := by ext j; simp [S] rw [this] exact hbounded π h1 h2 h3 N have hN_ex : ∃ N, ∀ n ≥ N, n ∉ S := by by_contra hc have hinf : S.Infinite := by intro hfin have hb := hfin.bddAbove obtain ⟨B, hB⟩ := hb apply hc refine ⟨B + 1, ?_⟩ intro n hn hnS have := hB hnS omega obtain ⟨t, htS, htcard⟩ := hinf.exists_subset_card_eq (d + 1) let N := t.sup id + 1 have hsub : (t : Set ℕ) ⊆ {j : ℕ | j < N ∧ j ∈ S} := by intro x hx refine ⟨?_, htS hx⟩ have : id x ≤ t.sup id := Finset.le_sup hx dsimp [id] at this omega have hfinN : Set.Finite {j : ℕ | j < N ∧ j ∈ S} := by apply Set.Finite.subset (Set.finite_Iio N) intro x hx exact hx.1 have hcard := Set.ncard_le_ncard hsub hfinN rw [Set.ncard_coe_finset, htcard] at hcard have hN := hS N omega obtain ⟨N, hN⟩ := hN_ex refine ⟨N, ?_⟩ intro n hn have hnot := hN n hn dsimp [S] at hnot by_cases ho : G.owner ((π n).source_node, (π n).source_state) = pl · exact Or.inl ho · right intro e he hsn hss hdir by_contra hne apply hnot exact ⟨ho, ⟨e, he, hsn, hss, hne⟩⟩ obtain ⟨τ, hτ⟩ := prioritized_borel_finite_hidden_opponent_choices_positional G pl M σ hwin hfinite refine ⟨Unit, inferInstance, ?_, ⟨τ, hτ⟩⟩ simp only [Fintype.card_unit] have : 1 ≤ 2 * k * Fintype.card Q + 1 := by omega exact Nat.one_le_pow d (2 * k * Fintype.card Q + 1) this