AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_bounded_opponent_branching_compression

theoremverifiedoriginal

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.

  1. 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.

    lines 2–11

      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
  2. 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.

    lines 12–38

    uses Finset.le_sup, Set.Finite.subset, Set.finite_Iio, Set.ncard_le_ncard, Set.ncard_coe_finset

        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
  3. 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.

    lines 39–50

    uses Or.inl

        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⟩⟩
  4. 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.

    line 51

    uses prioritized_borel_finite_hidden_opponent_choices_positional

      obtain ⟨τ, hτ⟩ := prioritized_borel_finite_hidden_opponent_choices_positional G pl M σ hwin hfinite
  5. The 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.

    lines 52–55

    uses Fintype.card_unit, Nat.one_le_pow

      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
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.

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

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