AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_reverse_deterministic_finite_hidden_priorities_positional

theoremverifiedoriginal

Consider a prioritized tree game. Assume that any two legal edges at the same source node with the same direction and target state have the same source state. Fix a player and a winning strategy for that player, allowing any memory type. Suppose that for every legal infinite play there is an index N such that, at each opponent-controlled position from N onward, the edge actually played is the only legal edge with that source node, source state, direction, and target state. Then that same player has a winning strategy whose memory type is Unit. The hypothesis is relative to the edge actually played: it allows other edges with a different direction or target state.

Statement

theorem prioritized_borel_reverse_deterministic_finite_hidden_priorities_positional {Q : Type} {k : ℕ} (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (M : Type) (σ : FiniteMemoryStrategy G pl M) (hwin : PrioritizedBorelStrategyWins G pl σ) (hreverse : ∀ e ∈ G.edges, ∀ e' ∈ G.edges, e.source_node = e'.source_node → e.dir = e'.dir → e.target_state = e'.target_state → e.source_state = e'.source_state) (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.target_state = (π n).target_state → e = π n) : ∃ τ : FiniteMemoryStrategy G pl Unit, PrioritizedBorelStrategyWins G pl τ
Related work
Reverse state reconstruction and eventual hidden-priority compression related to arXiv:2611.10136, Conjecture 19.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 12
  • 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_reverse_state_histories_uniqueIf a tree-game edge is reverse-deterministic in the state at each fixed parent node and child direction, then at most one state history…
  • 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…
  • PrioritizedBorelStrategyHistoryAn encoded finite history follows legal edges from the initial position and agrees with the chosen strategy at its player's positions.…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • prioritized_borel_eventual_hidden_shadowCompatible finite histories whose hidden-choice records eventually do not increase and whose extensions add no hidden choices eventually…
  • prioritized_borel_payoff_tail_congrTwo prioritized-game plays have the same payoff when their directions agree everywhere and their priorities agree eventually.

Read back from the Lean

For any state type Q, natural number k, prioritized Borel game G over Q with k priorities, player pl (Eve or Adam), and memory type M, if player pl has a winning strategy σ with memory M, under the assumptions: 1. (hreverse) the game is reverse deterministic: for any edges e, e' ∈ G.edges, if e and e' have the same source_node, dir, and target_state, then they have the same source_state; and 2. (hfinite) for every valid play π (a sequence of edges in G.edges starting at ([], G.init_state) where each step connects properly in tree node and state), there is some step N such that for all n ≥ N, either player pl owns the state at step n, or the edge π n is uniquely determined among edges in G.edges by its source_node, source_state, dir, and target_state (i.e., its priority is uniquely determined); then player pl has a winning positional strategy (formalized as a strategy τ with memory type Unit).

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 construct a positional (memoryless) winning strategy τ from a finite-memory winning strategy σ, we define an abstract deterministic replay framework that reconstructs full interaction histories from visible actions and a record of the opponent's 'hidden' choices (moves where multiple legal edges share the same direction and target state). Reverse determinism ensures that any two legal histories reaching the same position (v, q) have identical visible projections, so we can associate each reachable position with a canonical 'representative' history that minimizes the record of hidden choices under a well-founded linear order. The positional strategy τ at position (v, q) simply imitates the move that σ would make given this canonical representative history. Along any infinite play π against τ, the assumption that hidden opponent choices cease after some stage N guarantees that the sequence of records is non-increasing and thus stabilizes, forcing the canonical representatives to eventually trace out an actual play ρ compatible with σ; because π and ρ share the same directions and eventually identical priorities, the winning payoff of σ on ρ transfers to π.

  1. Replaying visible actions with the recorded hidden choices faithfully recovers the original compatible history.

    By induction on the action list xs. In the base case xs = [], both the replay and record are trivial. In the inductive step a :: xs, we case-split on whether the current step is the player's turn (own hist) and whether the opponent's choice is hidden (hidden hist (vis a)). In each case, compatibility determines a (either as the player's policy move or the unique forced edge), matching the corresponding branch of rdhHiddenReplay and allowing the induction hypothesis to close the goal.

    lines 49–68

    uses rdhHiddenRecord, rdhHiddenReplay, rdhHiddenCompatible, rdhHiddenStep

      induction xs generalizing hist with
      | nil => simp [rdhHiddenRecord, rdhHiddenReplay]
      | cons a xs ih =>
        simp only [rdhHiddenCompatible] at h
        cases ho : own hist <;> cases hb : hidden hist (vis a)
        · have ha' : a = forced hist (vis a) := by simpa [rdhHiddenStep, ho, hb] using h.1
          have ha : forced hist (vis a) = a := ha'.symm
          simpa [rdhHiddenRecord, rdhHiddenReplay, ho, hb, ha, List.append_assoc] using
            ih (hist ++ [a]) h.2
        · simpa [rdhHiddenRecord, rdhHiddenReplay, ho, hb, List.append_assoc] using
            ih (hist ++ [a]) h.2
        · have ha : a = policy hist := by simpa [rdhHiddenStep, ho, hb] using h.1
          subst a
          simpa [rdhHiddenRecord, rdhHiddenReplay, ho, hb, List.append_assoc] using
            ih (hist ++ [policy hist]) h.2
        · have ha : a = policy hist := by simpa [rdhHiddenStep, ho, hb] using h.1
          subst a
          simpa [rdhHiddenRecord, rdhHiddenReplay, ho, hb, List.append_assoc] using
            ih (hist ++ [policy hist]) h.2
    
  2. Two compatible histories starting from the same prefix are equal if their visible projections and hidden records match.

    Applying rdh_hidden_replay_recovers to both histories produces identical replay inputs, hence equal replay outputs some (hist ++ xs, []) = some (hist ++ ys, []). Canceling the common prefix hist yields xs = ys.

    lines 69–82

    uses rdh_hidden_replay_recovers, List.append_cancel_left

    theorem rdh_hidden_record_injective {A B : Type} [DecidableEq B] (vis : A → B) (own : List A → Bool)
        (hidden : List A → B → Bool) (policy : List A → A)
        (forced : List A → B → A) (hist xs ys : List A)
        (hx : rdhHiddenCompatible vis own hidden policy forced hist xs)
        (hy : rdhHiddenCompatible vis own hidden policy forced hist ys)
        (hvis : xs.map vis = ys.map vis)
        (hrecord : rdhHiddenRecord vis own hidden hist xs =
          rdhHiddenRecord vis own hidden hist ys) : xs = ys := by
      have hx' := rdh_hidden_replay_recovers vis own hidden policy forced hist xs hx
      have hy' := rdh_hidden_replay_recovers vis own hidden policy forced hist ys hy
      rw [hvis, hrecord] at hx'
      have h := hx'.symm.trans hy'
      exact List.append_cancel_left (congrArg Prod.fst (Option.some.inj h))
    
  3. Compatibility of a sequence with an appended step decomposes into compatibility of the prefix and compatibility of the last step.

    By induction on xs. The base case is immediate from the definition of rdhHiddenCompatible, and the inductive step follows by unfolding rdhHiddenCompatible and applying the induction hypothesis with conjunction associativity.

    lines 83–93

    uses rdhHiddenCompatible, rdhHiddenStep

    theorem rdh_hidden_compatible_snoc {A B : Type} (vis : A → B) (own : List A → Bool)
        (hidden : List A → B → Bool) (policy : List A → A)
        (forced : List A → B → A) (hist xs : List A) (a : A) :
        rdhHiddenCompatible vis own hidden policy forced hist (xs ++ [a]) ↔
          rdhHiddenCompatible vis own hidden policy forced hist xs ∧
          rdhHiddenStep vis own hidden policy forced (hist ++ xs) a := by
      induction xs generalizing hist with
      | nil => simp [rdhHiddenCompatible]
      | cons x xs ih =>
        simp [rdhHiddenCompatible, ih, List.append_assoc, and_assoc]
    
  4. The hidden record of a sequence with an appended step appends the step if and only if it is an opponent-controlled hidden move.

    By induction on xs, unfolding rdhHiddenRecord at each step and applying the induction hypothesis.

    lines 94–104

    uses rdhHiddenRecord

    theorem rdh_hidden_record_snoc {A B : Type} (vis : A → B) (own : List A → Bool)
        (hidden : List A → B → Bool) (hist xs : List A) (a : A) :
        rdhHiddenRecord vis own hidden hist (xs ++ [a]) =
          rdhHiddenRecord vis own hidden hist xs ++
            (if !own (hist ++ xs) && hidden (hist ++ xs) (vis a) then [a] else []) := by
      induction xs generalizing hist with
      | nil => simp [rdhHiddenRecord]
      | cons x xs ih =>
        cases hb : (!own hist && hidden hist (vis x)) <;>
          simp [rdhHiddenRecord, hb, ih, List.append_assoc]
    
  5. If a sequence of compatible histories has non-increasing hidden records after stage N and extensions preserve the record, then the histories eventually grow by exactly the actual steps played.

    Because the order on records is well-founded, the antitone sequence of records must eventually stabilize to a constant value at some K ≥ N by op1385_eventually_antitone_well_order_stabilizes. For all n ≥ K, the record of histories (n+1) equals that of histories n ++ [actual n]. Since their visible projections also match by assumption, injectivity of the record (rdh_hidden_record_injective) implies that histories (n+1) = histories n ++ [actual n].

    lines 105–133

    uses op1385_eventually_antitone_well_order_stabilizes, rdh_hidden_record_injective

    theorem rdh_eventual_hidden_shadow {A B : Type} [LinearOrder (List A)]
        [WellFoundedLT (List A)] (vis : A → B) (own : List A → Bool)
        (hidden : List A → B → Bool) (policy : List A → A)
        (forced : List A → B → A) (histories : ℕ → List A) (actual : ℕ → A)
        (N : ℕ)
        (hcompat : ∀ n, rdhHiddenCompatible vis own hidden policy forced [] (histories n))
        (hdir : ∀ n, (histories (n+1)).map vis = (histories n).map vis ++ [vis (actual n)])
        (hext : ∀ n ≥ N, rdhHiddenCompatible vis own hidden policy forced []
          (histories n ++ [actual n]))
        (hrecord : ∀ n ≥ N, rdhHiddenRecord vis own hidden [] (histories n ++ [actual n]) =
          rdhHiddenRecord vis own hidden [] (histories n))
        (hstep : ∀ n ≥ N, rdhHiddenRecord vis own hidden [] (histories (n+1)) ≤
          rdhHiddenRecord vis own hidden [] (histories n)) :
        ∃ K ≥ N, ∀ n ≥ K, histories (n+1) = histories n ++ [actual n] := by
      classical
      let rank : ℕ → List A := fun n => rdhHiddenRecord vis own hidden [] (histories n)
      obtain ⟨K, hKN, hstable⟩ := op1385_eventually_antitone_well_order_stabilizes rank N hstep
      refine ⟨K, hKN, ?_⟩
      intro n hn
      have hnN : N ≤ n := le_trans hKN hn
      have hrec : rdhHiddenRecord vis own hidden [] (histories (n+1)) =
          rdhHiddenRecord vis own hidden [] (histories n ++ [actual n]) := by
        rw [hrecord n hnN]
        exact (hstable (n+1) (by omega)).trans (hstable n hn).symm
      apply rdh_hidden_record_injective vis own hidden policy forced []
        (histories (n+1)) (histories n ++ [actual n]) (hcompat (n+1)) (hext n hnN)
      · simpa using hdir n
      · exact hrec
    
  6. Definitions of visible projection, hidden choices, and forced opponent edges in the tree game.

    The visible projection rdhVis extracts the direction and target state of an edge signature. The predicate rdhHidden decides whether there exist two distinct legal edges with the same source node, source state, direction, and target state. When no two such edges exist, rdhForced selects the unique matching legal edge using classical choice.

    lines 134–155

    uses op1385Eval, Classical.choose

    def rdhVis {Q : Type} {k : ℕ} (a : op1385Sig Q k) : Bool × Q := (a.1, a.2.1)
    
    noncomputable def rdhHidden {Q M : Type} {k : ℕ} (G : PrioritizedBorelGame Q k)
        (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (h : List (op1385Sig Q k)) (b : Bool × Q) : Bool := by
      classical
      let st := op1385Eval G pl σ h
      exact decide (∃ e ∈ G.edges, ∃ e' ∈ G.edges,
        e.source_node = st.2.1 ∧ e.source_state = st.2.2 ∧ e.dir = b.1 ∧ e.target_state = b.2 ∧
        e'.source_node = st.2.1 ∧ e'.source_state = st.2.2 ∧ e'.dir = b.1 ∧
          e'.target_state = b.2 ∧ e ≠ e')
    
    noncomputable def rdhForced {Q M : Type} {k : ℕ} (G : PrioritizedBorelGame Q k)
        (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (h : List (op1385Sig Q k)) (b : Bool × Q) : op1385Sig Q k := by
      classical
      let st := op1385Eval G pl σ h
      exact if hex : ∃ e ∈ G.edges,
          e.source_node = st.2.1 ∧ e.source_state = st.2.2 ∧ e.dir = b.1 ∧ e.target_state = b.2
        then op1385EdgeSig (Classical.choose hex)
        else op1385EdgeSig (σ.choice st.1 st.2.1 st.2.2)
    
  7. When an opponent move is not hidden, the matching legal edge is unique and recovered by rdhForced.

    If rdhHidden is false, any two legal edges with the specified direction and target state must be identical, establishing uniqueness (rdh_hidden_false_unique). Consequently, Classical.choose in rdhForced selects the true edge e, showing that rdhForced equals the edge signature of e (rdh_forced_eq).

    lines 156–196

    uses rdh_hidden_false_unique, rdh_forced_eq, Classical.choose_spec, dif_pos

    lemma rdh_hidden_false_unique {Q M : Type} {k : ℕ} (G : PrioritizedBorelGame Q k)
        (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (h : List (op1385Sig Q k)) (b : Bool × Q)
        (e e' : TreeGameEdge Q k) (he : e ∈ G.edges) (he' : e' ∈ G.edges)
        (hv : e.source_node = (op1385Eval G pl σ h).2.1)
        (hq : e.source_state = (op1385Eval G pl σ h).2.2) (hd : e.dir = b.1) (ht : e.target_state = b.2)
        (hv' : e'.source_node = (op1385Eval G pl σ h).2.1)
        (hq' : e'.source_state = (op1385Eval G pl σ h).2.2) (hd' : e'.dir = b.1)
        (ht' : e'.target_state = b.2)
        (hhidden : rdhHidden G pl σ h b = false) : e = e' := by
      classical
      have hn : ¬ ∃ a ∈ G.edges, ∃ a' ∈ G.edges,
          a.source_node = (op1385Eval G pl σ h).2.1 ∧
          a.source_state = (op1385Eval G pl σ h).2.2 ∧ a.dir = b.1 ∧ a.target_state = b.2 ∧
          a'.source_node = (op1385Eval G pl σ h).2.1 ∧
          a'.source_state = (op1385Eval G pl σ h).2.2 ∧ a'.dir = b.1 ∧
            a'.target_state = b.2 ∧ a ≠ a' := by
        simpa [rdhHidden] using hhidden
      by_contra hne
      exact hn ⟨e, he, e', he', hv, hq, hd, ht, hv', hq', hd', ht', hne⟩
    
    lemma rdh_forced_eq {Q M : Type} {k : ℕ} (G : PrioritizedBorelGame Q k)
        (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (h : List (op1385Sig Q k)) (e : TreeGameEdge Q k) (he : e ∈ G.edges)
        (hv : e.source_node = (op1385Eval G pl σ h).2.1)
        (hq : e.source_state = (op1385Eval G pl σ h).2.2)
        (hhidden : rdhHidden G pl σ h (e.dir, e.target_state) = false) :
        rdhForced G pl σ h (e.dir, e.target_state) = op1385EdgeSig e := by
      classical
      have hex : ∃ a ∈ G.edges,
          a.source_node = (op1385Eval G pl σ h).2.1 ∧
          a.source_state = (op1385Eval G pl σ h).2.2 ∧ a.dir = (e.dir, e.target_state).1 ∧
            a.target_state = (e.dir, e.target_state).2 :=
        ⟨e, he, hv, hq, rfl, rfl⟩
      have hs := Classical.choose_spec hex
      have hsame : Classical.choose hex = e :=
        rdh_hidden_false_unique G pl σ h (e.dir, e.target_state) (Classical.choose hex) e
          hs.1 he hs.2.1 hs.2.2.1 hs.2.2.2.1 hs.2.2.2.2 hv hq rfl rfl hhidden
      unfold rdhForced
      simp only [dif_pos hex, hsame]
    
  8. Every strategy history generated by the game rules is compatible with the replay model.

    By induction on the derivation of PrioritizedBorelStrategyHistory. The root is trivially compatible. For the inductive step, we check that the appended edge satisfies rdhHiddenStep: if the player owns the node, the edge matches the strategy's choice policy; if the opponent owns the node, either the move is hidden (which is vacuously allowed) or not hidden (in which case it equals rdhForced by rdh_forced_eq).

    lines 197–227

    uses rdh_hidden_compatible_snoc, op1385_eval_history, rdh_forced_eq

    theorem rdh_history_hidden_compatible {Q M : Type} {k : ℕ}
        (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (h : List (op1385Sig Q k)) (m : M) (v : List Bool) (q : Q)
        (hh : PrioritizedBorelStrategyHistory G pl σ h m v q) :
        rdhHiddenCompatible rdhVis (op1385Own G pl σ) (rdhHidden G pl σ)
          (op1385Policy G pl σ) (rdhForced G pl σ) [] h := by
      classical
      induction hh with
      | root => trivial
      | @step h m v q e hh he hnode hstate hchoice ih =>
        apply (rdh_hidden_compatible_snoc rdhVis (op1385Own G pl σ)
          (rdhHidden G pl σ) (op1385Policy G pl σ) (rdhForced G pl σ)
          [] h (op1385EdgeSig e)).2
        refine ⟨ih, ?_⟩
        simp only [List.nil_append]
        have heval := op1385_eval_history G pl σ h m v q hh
        have hnode' : e.source_node = (op1385Eval G pl σ h).2.1 := by simpa [heval] using hnode
        have hstate' : e.source_state = (op1385Eval G pl σ h).2.2 := by simpa [heval] using hstate
        by_cases howner : G.owner (v, q) = pl
        · have ho : op1385Own G pl σ h = true := by simp [op1385Own, heval, howner]
          have hs : op1385EdgeSig e = op1385Policy G pl σ h := by
            simp only [op1385Policy, heval]
            rw [hchoice howner]
          simp [rdhHiddenStep, ho, hs]
        · have ho : op1385Own G pl σ h = false := by simp [op1385Own, heval, howner]
          cases hhidden : rdhHidden G pl σ h (e.dir, e.target_state) with
          | true => simp [rdhHiddenStep, ho, op1385EdgeSig, rdhVis, hhidden]
          | false =>
            have hf := rdh_forced_eq G pl σ h e he hnode' hstate' hhidden
            simpa [rdhHiddenStep, ho, op1385EdgeSig, rdhVis, hhidden] using hf.symm
    
  9. Each reachable position admits a canonical representative strategy history with a minimal hidden record.

    For each reachable tree node v and state q, rdhReachableRecords is the set of hidden records of all strategy histories reaching (v, q). Using the well-founded linear order, rdhBestRecord selects the minimal record in this set (rdh_best_record_spec), and rdhRepresentative chooses a strategy history achieving this minimal record (rdh_representative_spec).

    lines 228–280

    uses rdh_best_record_spec, rdh_representative_spec, le_of_not_gt

    def rdhReachableRecords {Q M : Type} {k : ℕ} (G : PrioritizedBorelGame Q k)
        (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (v : List Bool) (q : Q) : Set (List (op1385Sig Q k)) :=
      {r | ∃ h m, PrioritizedBorelStrategyHistory G pl σ h m v q ∧
        rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) [] h = r}
    
    noncomputable def rdhBestRecord {Q M : Type} {k : ℕ}
        [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]
        (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (v : List Bool) (q : Q) : List (op1385Sig Q k) := by
      classical
      let S := rdhReachableRecords G pl σ v q
      exact if hs : S.Nonempty then Classical.choose (wellFounded_lt.has_min S hs) else []
    
    lemma rdh_best_record_spec {Q M : Type} {k : ℕ}
        [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]
        (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (v : List Bool) (q : Q) (hs : (rdhReachableRecords G pl σ v q).Nonempty) :
        rdhBestRecord G pl σ v q ∈ rdhReachableRecords G pl σ v q ∧
          ∀ r ∈ rdhReachableRecords G pl σ v q, rdhBestRecord G pl σ v q ≤ r := by
      classical
      have hmin := Classical.choose_spec (wellFounded_lt.has_min (rdhReachableRecords G pl σ v q) hs)
      have hbest : rdhBestRecord G pl σ v q =
          Classical.choose (wellFounded_lt.has_min (rdhReachableRecords G pl σ v q) hs) := by
        simp [rdhBestRecord, hs]
      rw [hbest]
      refine ⟨hmin.1, ?_⟩
      intro r hr
      exact le_of_not_gt (hmin.2 r hr)
    
    noncomputable def rdhRepresentative {Q M : Type} {k : ℕ}
        [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]
        (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (v : List Bool) (q : Q) : List (op1385Sig Q k) := by
      classical
      let S := rdhReachableRecords G pl σ v q
      exact if hs : S.Nonempty then
        Classical.choose ((rdh_best_record_spec G pl σ v q hs).1) else []
    
    lemma rdh_representative_spec {Q M : Type} {k : ℕ}
        [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]
        (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (v : List Bool) (q : Q) (hs : (rdhReachableRecords G pl σ v q).Nonempty) :
        ∃ m, PrioritizedBorelStrategyHistory G pl σ (rdhRepresentative G pl σ v q) m v q ∧
          rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) []
            (rdhRepresentative G pl σ v q) = rdhBestRecord G pl σ v q := by
      classical
      have hmem := (rdh_best_record_spec G pl σ v q hs).1
      have hrep : rdhRepresentative G pl σ v q = Classical.choose hmem := by
        simp [rdhRepresentative, hs]
      rw [hrep]
      exact Classical.choose_spec hmem
    
  10. Definition of the memoryless strategy rdhPositional.

    The strategy rdhPositional has memory type Unit. At position (v, q), if reachable records exist, it evaluates the finite-memory strategy σ's choice on the memory state reached by the canonical representative history rdhRepresentative; otherwise it falls back to a default legal edge. Its choices are verified to be legal outgoing edges by op1385_fallback_spec.

    lines 281–298

    uses op1385Fallback, op1385_fallback_spec

    noncomputable def rdhPositional {Q M : Type} {k : ℕ}
        [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]
        (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M) :
        FiniteMemoryStrategy G pl Unit where
      init_mem := ()
      update := fun _ _ => ()
      choice := fun _ v q => by
        classical
        exact if (rdhReachableRecords G pl σ v q).Nonempty then
          σ.choice (op1385Eval G pl σ (rdhRepresentative G pl σ v q)).1 v q
        else op1385Fallback G v q
      choice_edge := by
        classical
        intro _ v q howner
        split
        · exact σ.choice_edge _ v q howner
        · exact op1385_fallback_spec G v q
    
  11. Extending the representative history by a legal edge yields a valid history whose record upper-bounds the next position's best record.

    Lemma rdh_representative_extend appends edge e to the representative history at (v, q), which remains a valid strategy history because e is either chosen by σ on the player's turn or played by the opponent. In rdh_next_record_bound, this extended history witnesses that the set of reachable records at the successor position is nonempty, and by minimality, the successor's best record is at most the record of this extension.

    lines 299–332

    uses rdh_representative_spec, rdh_representative_extend, rdh_next_record_bound, rdh_best_record_spec

    lemma rdh_representative_extend {Q M : Type} {k : ℕ}
        [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]
        (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (v : List Bool) (q : Q) (hs : (rdhReachableRecords G pl σ v q).Nonempty)
        (e : TreeGameEdge Q k) (he : e ∈ G.edges) (hv : e.source_node = v) (hq : e.source_state = q)
        (hchosen : G.owner (v, q) = pl →
          e = σ.choice (op1385Eval G pl σ (rdhRepresentative G pl σ v q)).1 v q) :
        ∃ m, PrioritizedBorelStrategyHistory G pl σ
          (rdhRepresentative G pl σ v q ++ [op1385EdgeSig e]) m (v ++ [e.dir]) e.target_state := by
      obtain ⟨m, hh, _⟩ := rdh_representative_spec G pl σ v q hs
      have heval := op1385_eval_history G pl σ _ m v q hh
      refine ⟨σ.update m e, PrioritizedBorelStrategyHistory.step e hh he hv hq ?_⟩
      intro howner
      simpa [heval] using hchosen howner
    
    lemma rdh_next_record_bound {Q M : Type} {k : ℕ}
        [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]
        (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (v : List Bool) (q : Q) (hs : (rdhReachableRecords G pl σ v q).Nonempty)
        (e : TreeGameEdge Q k) (he : e ∈ G.edges) (hv : e.source_node = v) (hq : e.source_state = q)
        (hchosen : G.owner (v, q) = pl →
          e = σ.choice (op1385Eval G pl σ (rdhRepresentative G pl σ v q)).1 v q) :
        (rdhReachableRecords G pl σ (v ++ [e.dir]) e.target_state).Nonempty ∧
        rdhBestRecord G pl σ (v ++ [e.dir]) e.target_state ≤
          rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) []
            (rdhRepresentative G pl σ v q ++ [op1385EdgeSig e]) := by
      obtain ⟨m, hh⟩ := rdh_representative_extend G pl σ v q hs e he hv hq hchosen
      let r := rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) []
        (rdhRepresentative G pl σ v q ++ [op1385EdgeSig e])
      have hr : r ∈ rdhReachableRecords G pl σ (v ++ [e.dir]) e.target_state := by
        exact ⟨_, m, hh, rfl⟩
      have hne : (rdhReachableRecords G pl σ (v ++ [e.dir]) e.target_state).Nonempty := ⟨r, hr⟩
      exact ⟨hne, (rdh_best_record_spec G pl σ (v ++ [e.dir]) e.target_state hne).2 r hr⟩
    
  12. Every position reached in a play following the positional strategy has nonempty reachable records.

    By induction on the play length n. At n = 0, the root history witnesses reachability. In the inductive step, the play follows rdhPositional, so the edge played matches the condition of rdh_next_record_bound, which ensures the successor position is also reachable.

    lines 333–361

    uses PrioritizedBorelStrategyHistory.root, rdh_next_record_bound

    theorem rdh_positional_reachable {Q M : Type} {k : ℕ}
        [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]
        (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (π : ℕ → TreeGameEdge Q k) (hlegal : ∀ n, π n ∈ G.edges)
        (hinit : (π 0).source_node = [] ∧ (π 0).source_state = G.init_state)
        (hnext : ∀ n, (π (n+1)).source_node = (π n).source_node ++ [(π n).dir] ∧
          (π (n+1)).source_state = (π n).target_state)
        (hfollow : ∀ n, G.owner ((π n).source_node, (π n).source_state) = pl →
          π n = (rdhPositional G pl σ).choice () (π n).source_node (π n).source_state) :
        ∀ n, (rdhReachableRecords G pl σ (π n).source_node (π n).source_state).Nonempty := by
      classical
      intro n
      induction n with
      | zero =>
        rw [hinit.1, hinit.2]
        refine ⟨[], [], σ.init_mem, PrioritizedBorelStrategyHistory.root, ?_⟩
        rfl
      | succ n ih =>
        have hc : G.owner ((π n).source_node, (π n).source_state) = pl →
            π n = σ.choice (op1385Eval G pl σ
              (rdhRepresentative G pl σ (π n).source_node (π n).source_state)).1
              (π n).source_node (π n).source_state := by
          intro howner
          simpa [rdhPositional, ih] using hfollow n howner
        have hbound := rdh_next_record_bound G pl σ (π n).source_node (π n).source_state
          ih (π n) (hlegal n) rfl rfl hc
        rw [(hnext n).1, (hnext n).2]
        exact hbound.1
    
  13. If an edge is played by the player or is the unique legal edge matching its direction and target state, extending the representative history does not increase the hidden record.

    In either case, the condition (!own && hidden) is false at this step: if the player owns the turn, own is true; if the opponent owns the turn, the uniqueness hypothesis implies rdhHidden is false. By rdh_hidden_record_snoc, the appended edge adds nothing to the record, so the record of the extended history equals the best record of the source position.

    lines 362–392

    uses rdh_representative_spec, op1385_eval_history, rdh_hidden_record_snoc

    lemma rdh_extension_record_unchanged {Q M : Type} {k : ℕ}
        [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]
        (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (v : List Bool) (q : Q) (hs : (rdhReachableRecords G pl σ v q).Nonempty)
        (e : TreeGameEdge Q k) (he : e ∈ G.edges) (hv : e.source_node = v) (hq : e.source_state = q)
        (hnonhidden : G.owner (v, q) = pl ∨ ∀ e' ∈ G.edges,
          e'.source_node = v → e'.source_state = q → e'.dir = e.dir →
            e'.target_state = e.target_state → e' = e) :
        rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) []
          (rdhRepresentative G pl σ v q ++ [op1385EdgeSig e]) =
        rdhBestRecord G pl σ v q := by
      classical
      obtain ⟨m, hh, hrec⟩ := rdh_representative_spec G pl σ v q hs
      have heval := op1385_eval_history G pl σ _ m v q hh
      have hstore : (!op1385Own G pl σ (rdhRepresentative G pl σ v q) &&
          rdhHidden G pl σ (rdhRepresentative G pl σ v q) (e.dir, e.target_state)) = false := by
        rcases hnonhidden with howner | hunique
        · simp [op1385Own, heval, howner]
        · have hn : ¬ ∃ a ∈ G.edges, ∃ a' ∈ G.edges,
              a.source_node = v ∧ a.source_state = q ∧ a.dir = e.dir ∧ a.target_state = e.target_state ∧
              a'.source_node = v ∧ a'.source_state = q ∧ a'.dir = e.dir ∧
                a'.target_state = e.target_state ∧ a ≠ a' := by
            rintro ⟨a, ha, a', ha', hav, haq, had, hat, hav', haq', had', hat', hne⟩
            exact hne ((hunique a ha hav haq had hat).trans (hunique a' ha' hav' haq' had' hat').symm)
          have hhfalse : rdhHidden G pl σ (rdhRepresentative G pl σ v q)
              (e.dir, e.target_state) = false := by
            simpa [rdhHidden, heval] using hn
          simp [hhfalse]
      rw [rdh_hidden_record_snoc]
      simpa [op1385EdgeSig, rdhVis, hstore] using hrec
    
  14. Under reverse determinism, any two strategy histories reaching the same position (v, q) have identical visible projections.

    By induction on the strategy history hh. The base case is length zero. In the inductive step, we decompose any competing history h' into a prefix and final edge e'. Since both reach the same node and state, the directions must match, and reverse determinism implies their source states must also match. By the induction hypothesis, their visible prefixes agree, and adding the final direction and target state preserves agreement.

    lines 393–431

    uses op1385_eval_node, op1385_eval_history, op1385_history_snoc_inv, List.append_inj'

    theorem rdh_history_vis_unique {Q M : Type} {k : ℕ} (G : PrioritizedBorelGame Q k)
        (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (hreverse : ∀ e ∈ G.edges, ∀ e' ∈ G.edges, e.source_node = e'.source_node →
          e.dir = e'.dir → e.target_state = e'.target_state → e.source_state = e'.source_state)
        (h : List (op1385Sig Q k)) (m : M) (v : List Bool) (q : Q)
        (hh : PrioritizedBorelStrategyHistory G pl σ h m v q) :
        ∀ (h' : List (op1385Sig Q k)) (m' : M), PrioritizedBorelStrategyHistory G pl σ h' m' v q →
          h.map rdhVis = h'.map rdhVis := by
      induction hh with
      | root =>
        intro h' m' hh'
        have hn := op1385_eval_node G pl σ h'
        rw [op1385_eval_history G pl σ h' m' [] G.init_state hh'] at hn
        have hl := congrArg List.length hn
        simp only [List.length_nil, List.length_map] at hl
        have : h' = [] := List.eq_nil_of_length_eq_zero hl.symm
        subst this
        rfl
      | @step h m v q e hh he hv hq hc ih =>
        intro h' m' hh'
        have hn := op1385_eval_node G pl σ h'
        rw [op1385_eval_history G pl σ h' m' _ _ hh'] at hn
        obtain ⟨h0, a, rfl⟩ : ∃ h0 a, h' = h0 ++ [a] := by
          rcases List.eq_nil_or_concat h' with h0 | ⟨L, b, hL⟩
          · subst h0
            simp at hn
          · exact ⟨L, b, by simpa using hL⟩
        obtain ⟨m₀, v₀, q₀, e', hh0, he', hv', hq', _, ha, _, hvv, hqq⟩ :=
          op1385_history_snoc_inv G pl σ _ m' _ _ hh' h0 a rfl
        obtain ⟨hv0, hd⟩ := List.append_inj' hvv rfl
        have hd' : e.dir = e'.dir := by simpa using hd
        have hs := hreverse e he e' he' (hv.trans (hv0.trans hv'.symm)) hd' hqq
        have hq0 : q = q₀ := hq.symm.trans (hs.trans hq')
        subst hv0
        subst hq0
        have hih := ih h0 m₀ hh0
        rw [← ha]
        simp [List.map_append, hih, rdhVis, op1385EdgeSig, hd', hqq]
    
  15. Along any play following the positional strategy, the sequence of representative histories eventually extends by the actual edges played.

    We define histories n as the representative history at step n and check the hypotheses of rdh_eventual_hidden_shadow: each history is compatible; their visible projections grow by the actual visible move (by rdh_history_vis_unique); beyond stage N, non-hidden moves leave the record unchanged (rdh_extension_record_unchanged); and the best record sequence is antitone (rdh_next_record_bound). Applying rdh_eventual_hidden_shadow yields a stage K ≥ N after which histories (n+1) = histories n ++ [op1385EdgeSig (π n)].

    lines 432–505

    uses rdh_positional_reachable, rdh_representative_spec, rdh_history_hidden_compatible, rdh_representative_extend, rdh_history_vis_unique, rdh_extension_record_unchanged, rdh_next_record_bound, rdh_eventual_hidden_shadow

    theorem rdh_positional_representatives_stabilize {Q M : Type} {k : ℕ}
        [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]
        (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)
        (π : ℕ → TreeGameEdge Q k) (hlegal : ∀ n, π n ∈ G.edges)
        (hinit : (π 0).source_node = [] ∧ (π 0).source_state = G.init_state)
        (hnext : ∀ n, (π (n+1)).source_node = (π n).source_node ++ [(π n).dir] ∧
          (π (n+1)).source_state = (π n).target_state)
        (hfollow : ∀ n, G.owner ((π n).source_node, (π n).source_state) = pl →
          π n = (rdhPositional G pl σ).choice () (π n).source_node (π n).source_state)
        (hreverse : ∀ e ∈ G.edges, ∀ e' ∈ G.edges, e.source_node = e'.source_node →
          e.dir = e'.dir → e.target_state = e'.target_state → e.source_state = e'.source_state)
        (N : ℕ) (hnonhidden : ∀ 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.target_state = (π n).target_state → e = π n) :
        ∃ K ≥ N, ∀ n ≥ K,
          rdhRepresentative G pl σ (π (n+1)).source_node (π (n+1)).source_state =
          rdhRepresentative G pl σ (π n).source_node (π n).source_state ++ [op1385EdgeSig (π n)] := by
      classical
      let histories : ℕ → List (op1385Sig Q k) := fun n =>
        rdhRepresentative G pl σ (π n).source_node (π n).source_state
      let actual : ℕ → op1385Sig Q k := fun n => op1385EdgeSig (π n)
      have hreach := rdh_positional_reachable G pl σ π hlegal hinit hnext hfollow
      have hrep (n : ℕ) : ∃ m, PrioritizedBorelStrategyHistory G pl σ (histories n) m
          (π n).source_node (π n).source_state ∧
          rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) [] (histories n) =
            rdhBestRecord G pl σ (π n).source_node (π n).source_state :=
        rdh_representative_spec G pl σ (π n).source_node (π n).source_state (hreach n)
      have hcompat (n : ℕ) : rdhHiddenCompatible rdhVis (op1385Own G pl σ)
          (rdhHidden G pl σ) (op1385Policy G pl σ) (rdhForced G pl σ) [] (histories n) := by
        obtain ⟨m, hh, _⟩ := hrep n
        exact rdh_history_hidden_compatible G pl σ _ m _ _ hh
      have hnode (n : ℕ) : (histories n).map Prod.fst = (π n).source_node := by
        obtain ⟨m, hh, _⟩ := hrep n
        have heval := op1385_eval_history G pl σ (histories n) m _ _ hh
        simpa [heval] using (op1385_eval_node G pl σ (histories n)).symm
      have hchosen (n : ℕ) : G.owner ((π n).source_node, (π n).source_state) = pl →
          π n = σ.choice (op1385Eval G pl σ (histories n)).1
            (π n).source_node (π n).source_state := by
        intro howner
        simpa [histories, rdhPositional, hreach n] using hfollow n howner
      have hext (n : ℕ) : rdhHiddenCompatible rdhVis (op1385Own G pl σ)
          (rdhHidden G pl σ) (op1385Policy G pl σ) (rdhForced G pl σ) []
          (histories n ++ [actual n]) := by
        obtain ⟨m, hh⟩ := rdh_representative_extend G pl σ (π n).source_node (π n).source_state
          (hreach n) (π n) (hlegal n) rfl rfl (hchosen n)
        exact rdh_history_hidden_compatible G pl σ _ m _ _ hh
      have hdir (n : ℕ) : (histories (n+1)).map rdhVis =
          (histories n).map rdhVis ++ [rdhVis (actual n)] := by
        obtain ⟨m, hh⟩ := rdh_representative_extend G pl σ (π n).source_node (π n).source_state
          (hreach n) (π n) (hlegal n) rfl rfl (hchosen n)
        obtain ⟨m', hh', _⟩ := hrep (n+1)
        rw [(hnext n).1, (hnext n).2] at hh'
        have hu := rdh_history_vis_unique G pl σ hreverse _ _ _ _ hh' _ _ hh
        rw [hu, List.map_append]
        rfl
      have hrecord (n : ℕ) (hn : N ≤ n) :
          rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) []
            (histories n ++ [actual n]) =
          rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) [] (histories n) := by
        have heq := rdh_extension_record_unchanged G pl σ (π n).source_node (π n).source_state
          (hreach n) (π n) (hlegal n) rfl rfl (hnonhidden n hn)
        exact heq.trans (hrep n).choose_spec.2.symm
      have hstep (n : ℕ) (hn : N ≤ n) :
          rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) [] (histories (n+1)) ≤
          rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) [] (histories n) := by
        have hb := (rdh_next_record_bound G pl σ (π n).source_node (π n).source_state
          (hreach n) (π n) (hlegal n) rfl rfl (hchosen n)).2
        rw [← (hnext n).1, ← (hnext n).2, ← (hrep (n+1)).choose_spec.2, hrecord n hn] at hb
        exact hb
      exact rdh_eventual_hidden_shadow rdhVis (op1385Own G pl σ) (rdhHidden G pl σ)
        (op1385Policy G pl σ) (rdhForced G pl σ) histories actual N hcompat hdir
        (fun n _ => hext n) hrecord hstep
    
  16. Construct the well-ordering and positional strategy τ, and show that representative histories along play π stabilize.

    We endow the type of edge-signature lists with a well-founded linear order using exists_wellFoundedLT, defining τ = rdhPositional G pl σ. For any legal play π complying with τ, the memory state is uniquely (), so π follows τ's choices. The finiteness hypothesis gives an index N after which opponent moves are unique, and rdh_positional_representatives_stabilize produces a cutoff K ≥ N where representative histories nest.

    lines 506–531

    uses exists_wellFoundedLT, rdhPositional, Subsingleton.elim, rdh_positional_representatives_stabilize, rdh_positional_reachable, rdh_representative_spec

    theorem prioritized_borel_reverse_deterministic_finite_hidden_priorities_positional {Q : Type} {k : ℕ} (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (M : Type) (σ : FiniteMemoryStrategy G pl M) (hwin : PrioritizedBorelStrategyWins G pl σ) (hreverse : ∀ e ∈ G.edges, ∀ e' ∈ G.edges, e.source_node = e'.source_node → e.dir = e'.dir → e.target_state = e'.target_state → e.source_state = e'.source_state) (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.target_state = (π n).target_state → e = π n) : ∃ τ : FiniteMemoryStrategy G pl Unit, PrioritizedBorelStrategyWins G pl τ := by
      classical
      obtain ⟨ord, hwf⟩ := exists_wellFoundedLT (List (op1385Sig Q k))
      letI : LinearOrder (List (op1385Sig Q k)) := ord
      letI : WellFoundedLT (List (op1385Sig Q k)) := hwf
      let τ := rdhPositional G pl σ
      refine ⟨τ, ?_⟩
      unfold PrioritizedBorelStrategyWins
      intro π hlegal hinit hnext hmem
      obtain ⟨mem, hm0, hmu, hchoice⟩ := hmem
      have hfollow : ∀ n, G.owner ((π n).source_node, (π n).source_state) = pl →
          π n = (rdhPositional G pl σ).choice () (π n).source_node (π n).source_state := by
        intro n hn
        have hm : mem n = () := Subsingleton.elim _ _
        simpa [hm, τ] using hchoice n hn
      obtain ⟨N, hnonhidden⟩ := hfinite π hlegal hinit hnext
      obtain ⟨K, hKN, hstable⟩ :=
        rdh_positional_representatives_stabilize G pl σ π hlegal hinit hnext hfollow hreverse N hnonhidden
      let histories : ℕ → List (op1385Sig Q k) := fun n =>
        rdhRepresentative G pl σ (π n).source_node (π n).source_state
      let actual : ℕ → op1385Sig Q k := fun n => op1385EdgeSig (π n)
      have hreach := rdh_positional_reachable G pl σ π hlegal hinit hnext hfollow
      have hrep (n : ℕ) : ∃ m, PrioritizedBorelStrategyHistory G pl σ (histories n) m
          (π n).source_node (π n).source_state := by
        obtain ⟨m, hh, _⟩ := rdh_representative_spec G pl σ _ _ (hreach n)
        exact ⟨m, hh⟩
  17. Construct an infinite shadow play consistent with the original strategy σ whose prefixes match the representative histories.

    The lengths of the representative histories equal n, and their visible projections match the node prefix of π. Applying op1385_nested_histories_visible_shadow provides an infinite sequence f of edge signatures whose prefixes agree with the representative histories for n ≥ K. Through op1385_all_shadow_prefixes and op1385_shadow_play_of_histories, f generates a valid infinite play ρ consistent with the original winning strategy σ.

    lines 532–550

    uses op1385_eval_node, op1385_play_nodes, op1385_nested_histories_visible_shadow, op1385_all_shadow_prefixes, op1385_shadow_play_of_histories

      have hnode (n : ℕ) : (histories n).map Prod.fst = (π n).source_node := by
        obtain ⟨m, hh⟩ := hrep n
        have heval := op1385_eval_history G pl σ (histories n) m _ _ hh
        simpa [heval] using (op1385_eval_node G pl σ (histories n)).symm
      have hnodes := op1385_play_nodes π hinit.1 (fun n => (hnext n).1)
      have hlen (n : ℕ) : (histories n).length = n := by
        have h := congrArg List.length (hnode n)
        simpa [hnodes, op1385FnPrefix] using h
      have hvis (n : ℕ) : (histories n).map Prod.fst =
          List.ofFn (fun i : Fin n => Prod.fst (actual i)) := by
        simpa [actual, op1385EdgeSig, op1385FnPrefix] using (hnode n).trans (hnodes n)
      obtain ⟨f, hprefix, htail, hvisall⟩ :=
        op1385_nested_histories_visible_shadow Prod.fst histories actual K hlen hvis hstable
      have hrepall (n : ℕ) : ∃ m v q, PrioritizedBorelStrategyHistory G pl σ (histories n) m v q := by
        obtain ⟨m, hh⟩ := hrep n
        exact ⟨m, _, _, hh⟩
      have hall := op1385_all_shadow_prefixes G pl σ histories f K hrepall hprefix
      have hshadow := op1385_shadow_play_of_histories G pl σ f (by simpa [op1385FnPrefix] using hall)
      let ρ := op1385ShadowEdge G pl σ f
  18. The actual play π wins for player pl because its directions match ρ everywhere and its priorities match ρ on a tail.

    Since σ is winning, ρ satisfies the winning condition. The directions of π and ρ are identical at all steps, and for all n ≥ K, their priorities coincide because f n equals the actual edge signature. By prioritized_borel_payoff_tail_congr, the prioritized Borel payoff depends only on directions and tail priority frequencies, so π has the same winning status as ρ, completing the proof for both Eve and Adam.

    lines 551–564

    uses op1385ShadowEdge, Filter.eventually_atTop.mpr, prioritized_borel_payoff_tail_congr

      have hw := hwin ρ hshadow.1 hshadow.2.1 hshadow.2.2.1 hshadow.2.2.2
      have hdir : ∀ n, (π n).dir = (ρ n).dir := by
        intro n
        simpa [ρ, op1385ShadowEdge, op1385MakeEdge, actual, op1385EdgeSig] using (hvisall n).symm
      have hprio : ∀ᶠ n in Filter.atTop, (π n).prio = (ρ n).prio := by
        apply Filter.eventually_atTop.mpr
        refine ⟨K, ?_⟩
        intro n hn
        simpa [ρ, op1385ShadowEdge, op1385MakeEdge, actual, op1385EdgeSig] using
          congrArg (fun a : op1385Sig Q k => a.2.2) (htail n hn).symm
      have hequiv := prioritized_borel_payoff_tail_congr G π ρ hdir hprio
      cases pl with
      | Eve => exact hequiv.mpr hw
      | Adam => exact fun h => hw (hequiv.mp h)
rdh_hidden_replay_recovers
Replaying the visible projection of a compatible history with its recorded hidden choices reconstructs the original history and an empty remaining record.
List.append_cancel_left
If as ++ bs = as ++ cs, then bs = cs.
rdhHiddenCompatible
A sequence of steps is compatible if every step satisfies the step-compatibility predicate with respect to the accumulated history.
rdhHiddenStep
A step is compatible if on player turns it follows the policy, on non-hidden opponent turns it matches the unique forced choice, and on hidden opponent turns any choice is allowed.
rdhHiddenRecord
The sublist of actions taken by the opponent at positions where the choice was hidden.
op1385_eventually_antitone_well_order_stabilizes
Any sequence in a well-founded partial order that is eventually non-increasing eventually becomes constant.
rdh_hidden_record_injective
Two compatible histories starting from the same prefix that have identical visible projections and identical hidden records must be identical.
op1385Eval
Computes the strategy memory state, tree node, and game state reached after a history of edge signatures.
Classical.choose
Extracts a witness from an existential proof.
rdh_hidden_false_unique
If an opponent position is not hidden, there is at most one legal edge with the specified direction and target state.
rdh_forced_eq
When an opponent position is not hidden, the forced edge function selects the unique matching legal edge.
Classical.choose_spec
The witness extracted by Classical.choose satisfies the given predicate.
dif_pos
Simplifies a dependent if-then-else to its positive branch when the condition is true.
rdh_hidden_compatible_snoc
Appending an action to a history yields a compatible sequence if and only if the prefix is compatible and the action satisfies the step condition.
op1385_eval_history
Evaluating a strategy history yields the memory state, node, and state tracked by the inductive history predicate.
rdh_best_record_spec
The best record at a position is reachable and is less than or equal to every other reachable hidden record.
rdh_representative_spec
The canonical representative history at a position is a valid strategy history whose hidden record achieves the best record.
le_of_not_gt
In a linear order, if b is not strictly less than a, then a ≤ b.
op1385Fallback
Provides a default outgoing legal edge from any node and state.
op1385_fallback_spec
The fallback edge is a legal outgoing edge from the given node and state.
rdh_representative_extend
Extending a representative history by a legal edge produces a valid strategy history reaching the successor node and state.
rdh_next_record_bound
The best record at a successor position is bounded above by the record obtained from extending the current representative history.
PrioritizedBorelStrategyHistory.root
The empty history at the initial state with initial memory is a valid strategy history.
rdh_hidden_record_snoc
Appending an action to a history appends that action to the hidden record if and only if the position is an opponent turn and hidden.
op1385_eval_node
The node reached after a history of actions equals the list of directions of those actions.
op1385_history_snoc_inv
Deconstructs a non-empty strategy history into a predecessor history and a final legal edge.
List.append_inj'
If as ++ [a] = bs ++ [b] with equal list lengths, then as = bs and a = b.
rdh_positional_reachable
Every position reached during a play conforming to the positional strategy has a nonempty set of reachable records.
rdh_history_hidden_compatible
Any valid strategy history is compatible with the deterministic replay system.
rdh_history_vis_unique
Under reverse determinism, any two strategy histories reaching the same node and state have identical visible projections.
rdh_extension_record_unchanged
Extending a representative history by an edge on a player turn or a non-hidden opponent turn leaves its hidden record unchanged.
rdh_eventual_hidden_shadow
A sequence of compatible histories with non-increasing records eventually extends by the actual played actions.
exists_wellFoundedLT
Every type admits a well-founded linear order.
rdhPositional
Constructs a memoryless strategy (with memory type Unit) from a finite-memory strategy by copying its choices on canonical representative histories.
Subsingleton.elim
Any two elements of a subsingleton type, such as Unit, are equal.
rdh_positional_representatives_stabilize
Along any play against the positional strategy, the representative histories eventually grow step-by-step by the edges of the play.
op1385_play_nodes
The nodes along any legal play are the successive prefix lists of played directions.
op1385_nested_histories_visible_shadow
Constructs an infinite sequence of edge signatures whose finite prefixes match an eventually nested sequence of histories and whose directions match the play.
op1385_all_shadow_prefixes
Shows that every finite prefix of the shadow sequence is a valid strategy history.
op1385_shadow_play_of_histories
An infinite sequence of edge signatures whose prefixes are all strategy histories defines an infinite play consistent with the strategy.
op1385ShadowEdge
Converts the n-th edge signature of a shadow sequence into a tree game edge.
Filter.eventually_atTop.mpr
A property holds eventually at infinity if it holds for all indices greater than or equal to some cutoff.
prioritized_borel_payoff_tail_congr
The prioritized Borel winning condition on two plays is equivalent if their directions coincide and their priorities coincide eventually.

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

def rdhHiddenStep {A B : Type} (vis : A → B) (own : List A → Bool)    (hidden : List A → B → Bool) (policy : List A → A)    (forced : List A → B → A) (hist : List A) (a : A) : Prop :=  if own hist then a = policy hist  else if hidden hist (vis a) then True else a = forced hist (vis a)def rdhHiddenCompatible {A B : Type} (vis : A → B) (own : List A → Bool)    (hidden : List A → B → Bool) (policy : List A → A)    (forced : List A → B → A) : List A → List A → Prop  | _, [] => True  | hist, a :: rest =>    rdhHiddenStep vis own hidden policy forced hist a ∧      rdhHiddenCompatible vis own hidden policy forced (hist ++ [a]) restdef rdhHiddenRecord {A B : Type} (vis : A → B) (own : List A → Bool)    (hidden : List A → B → Bool) : List A → List A → List A  | _, [] => []  | hist, a :: rest =>    if !own hist && hidden hist (vis a) then      a :: rdhHiddenRecord vis own hidden (hist ++ [a]) rest    else rdhHiddenRecord vis own hidden (hist ++ [a]) restdef rdhHiddenReplay {A B : Type} [DecidableEq B] (vis : A → B) (own : List A → Bool)    (hidden : List A → B → Bool) (policy : List A → A)    (forced : List A → B → A) : List A → List B → List A → Option (List A × List A)  | hist, [], record => some (hist, record)  | hist, b :: bs, record =>    if own hist then      let a := policy hist      if vis a = b then rdhHiddenReplay vis own hidden policy forced (hist ++ [a]) bs record      else none    else if hidden hist b then      match record with      | [] => none      | a :: tail =>        if vis a = b then rdhHiddenReplay vis own hidden policy forced (hist ++ [a]) bs tail        else none    else      let a := forced hist b      if vis a = b then rdhHiddenReplay vis own hidden policy forced (hist ++ [a]) bs record      else nonetheorem rdh_hidden_replay_recovers {A B : Type} [DecidableEq B] (vis : A → B) (own : List A → Bool)    (hidden : List A → B → Bool) (policy : List A → A)    (forced : List A → B → A) (hist xs : List A)    (h : rdhHiddenCompatible vis own hidden policy forced hist xs) :    rdhHiddenReplay vis own hidden policy forced hist (xs.map vis)      (rdhHiddenRecord vis own hidden hist xs) = some (hist ++ xs, []) := by  induction xs generalizing hist with  | nil => simp [rdhHiddenRecord, rdhHiddenReplay]  | cons a xs ih =>    simp only [rdhHiddenCompatible] at h    cases ho : own hist <;> cases hb : hidden hist (vis a)    · have ha' : a = forced hist (vis a) := by simpa [rdhHiddenStep, ho, hb] using h.1      have ha : forced hist (vis a) = a := ha'.symm      simpa [rdhHiddenRecord, rdhHiddenReplay, ho, hb, ha, List.append_assoc] using        ih (hist ++ [a]) h.2    · simpa [rdhHiddenRecord, rdhHiddenReplay, ho, hb, List.append_assoc] using        ih (hist ++ [a]) h.2    · have ha : a = policy hist := by simpa [rdhHiddenStep, ho, hb] using h.1      subst a      simpa [rdhHiddenRecord, rdhHiddenReplay, ho, hb, List.append_assoc] using        ih (hist ++ [policy hist]) h.2    · have ha : a = policy hist := by simpa [rdhHiddenStep, ho, hb] using h.1      subst a      simpa [rdhHiddenRecord, rdhHiddenReplay, ho, hb, List.append_assoc] using        ih (hist ++ [policy hist]) h.2theorem rdh_hidden_record_injective {A B : Type} [DecidableEq B] (vis : A → B) (own : List A → Bool)    (hidden : List A → B → Bool) (policy : List A → A)    (forced : List A → B → A) (hist xs ys : List A)    (hx : rdhHiddenCompatible vis own hidden policy forced hist xs)    (hy : rdhHiddenCompatible vis own hidden policy forced hist ys)    (hvis : xs.map vis = ys.map vis)    (hrecord : rdhHiddenRecord vis own hidden hist xs =      rdhHiddenRecord vis own hidden hist ys) : xs = ys := by  have hx' := rdh_hidden_replay_recovers vis own hidden policy forced hist xs hx  have hy' := rdh_hidden_replay_recovers vis own hidden policy forced hist ys hy  rw [hvis, hrecord] at hx'  have h := hx'.symm.trans hy'  exact List.append_cancel_left (congrArg Prod.fst (Option.some.inj h))theorem rdh_hidden_compatible_snoc {A B : Type} (vis : A → B) (own : List A → Bool)    (hidden : List A → B → Bool) (policy : List A → A)    (forced : List A → B → A) (hist xs : List A) (a : A) :    rdhHiddenCompatible vis own hidden policy forced hist (xs ++ [a]) ↔      rdhHiddenCompatible vis own hidden policy forced hist xs ∧      rdhHiddenStep vis own hidden policy forced (hist ++ xs) a := by  induction xs generalizing hist with  | nil => simp [rdhHiddenCompatible]  | cons x xs ih =>    simp [rdhHiddenCompatible, ih, List.append_assoc, and_assoc]theorem rdh_hidden_record_snoc {A B : Type} (vis : A → B) (own : List A → Bool)    (hidden : List A → B → Bool) (hist xs : List A) (a : A) :    rdhHiddenRecord vis own hidden hist (xs ++ [a]) =      rdhHiddenRecord vis own hidden hist xs ++        (if !own (hist ++ xs) && hidden (hist ++ xs) (vis a) then [a] else []) := by  induction xs generalizing hist with  | nil => simp [rdhHiddenRecord]  | cons x xs ih =>    cases hb : (!own hist && hidden hist (vis x)) <;>      simp [rdhHiddenRecord, hb, ih, List.append_assoc]theorem rdh_eventual_hidden_shadow {A B : Type} [LinearOrder (List A)]    [WellFoundedLT (List A)] (vis : A → B) (own : List A → Bool)    (hidden : List A → B → Bool) (policy : List A → A)    (forced : List A → B → A) (histories : ℕ → List A) (actual : ℕ → A)    (N : ℕ)    (hcompat : ∀ n, rdhHiddenCompatible vis own hidden policy forced [] (histories n))    (hdir : ∀ n, (histories (n+1)).map vis = (histories n).map vis ++ [vis (actual n)])    (hext : ∀ n ≥ N, rdhHiddenCompatible vis own hidden policy forced []      (histories n ++ [actual n]))    (hrecord : ∀ n ≥ N, rdhHiddenRecord vis own hidden [] (histories n ++ [actual n]) =      rdhHiddenRecord vis own hidden [] (histories n))    (hstep : ∀ n ≥ N, rdhHiddenRecord vis own hidden [] (histories (n+1)) ≤      rdhHiddenRecord vis own hidden [] (histories n)) :    ∃ K ≥ N, ∀ n ≥ K, histories (n+1) = histories n ++ [actual n] := by  classical  let rank : ℕ → List A := fun n => rdhHiddenRecord vis own hidden [] (histories n)  obtain ⟨K, hKN, hstable⟩ := op1385_eventually_antitone_well_order_stabilizes rank N hstep  refine ⟨K, hKN, ?_⟩  intro n hn  have hnN : N ≤ n := le_trans hKN hn  have hrec : rdhHiddenRecord vis own hidden [] (histories (n+1)) =      rdhHiddenRecord vis own hidden [] (histories n ++ [actual n]) := by    rw [hrecord n hnN]    exact (hstable (n+1) (by omega)).trans (hstable n hn).symm  apply rdh_hidden_record_injective vis own hidden policy forced []    (histories (n+1)) (histories n ++ [actual n]) (hcompat (n+1)) (hext n hnN)  · simpa using hdir n  · exact hrecdef rdhVis {Q : Type} {k : ℕ} (a : op1385Sig Q k) : Bool × Q := (a.1, a.2.1)noncomputable def rdhHidden {Q M : Type} {k : ℕ} (G : PrioritizedBorelGame Q k)    (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (h : List (op1385Sig Q k)) (b : Bool × Q) : Bool := by  classical  let st := op1385Eval G pl σ h  exact decide (∃ e ∈ G.edges, ∃ e' ∈ G.edges,    e.source_node = st.2.1 ∧ e.source_state = st.2.2 ∧ e.dir = b.1 ∧ e.target_state = b.2 ∧    e'.source_node = st.2.1 ∧ e'.source_state = st.2.2 ∧ e'.dir = b.1 ∧      e'.target_state = b.2 ∧ e ≠ e')noncomputable def rdhForced {Q M : Type} {k : ℕ} (G : PrioritizedBorelGame Q k)    (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (h : List (op1385Sig Q k)) (b : Bool × Q) : op1385Sig Q k := by  classical  let st := op1385Eval G pl σ h  exact if hex : ∃ e ∈ G.edges,      e.source_node = st.2.1 ∧ e.source_state = st.2.2 ∧ e.dir = b.1 ∧ e.target_state = b.2    then op1385EdgeSig (Classical.choose hex)    else op1385EdgeSig (σ.choice st.1 st.2.1 st.2.2)lemma rdh_hidden_false_unique {Q M : Type} {k : ℕ} (G : PrioritizedBorelGame Q k)    (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (h : List (op1385Sig Q k)) (b : Bool × Q)    (e e' : TreeGameEdge Q k) (he : e ∈ G.edges) (he' : e' ∈ G.edges)    (hv : e.source_node = (op1385Eval G pl σ h).2.1)    (hq : e.source_state = (op1385Eval G pl σ h).2.2) (hd : e.dir = b.1) (ht : e.target_state = b.2)    (hv' : e'.source_node = (op1385Eval G pl σ h).2.1)    (hq' : e'.source_state = (op1385Eval G pl σ h).2.2) (hd' : e'.dir = b.1)    (ht' : e'.target_state = b.2)    (hhidden : rdhHidden G pl σ h b = false) : e = e' := by  classical  have hn : ¬ ∃ a ∈ G.edges, ∃ a' ∈ G.edges,      a.source_node = (op1385Eval G pl σ h).2.1 ∧      a.source_state = (op1385Eval G pl σ h).2.2 ∧ a.dir = b.1 ∧ a.target_state = b.2 ∧      a'.source_node = (op1385Eval G pl σ h).2.1 ∧      a'.source_state = (op1385Eval G pl σ h).2.2 ∧ a'.dir = b.1 ∧        a'.target_state = b.2 ∧ a ≠ a' := by    simpa [rdhHidden] using hhidden  by_contra hne  exact hn ⟨e, he, e', he', hv, hq, hd, ht, hv', hq', hd', ht', hne⟩lemma rdh_forced_eq {Q M : Type} {k : ℕ} (G : PrioritizedBorelGame Q k)    (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (h : List (op1385Sig Q k)) (e : TreeGameEdge Q k) (he : e ∈ G.edges)    (hv : e.source_node = (op1385Eval G pl σ h).2.1)    (hq : e.source_state = (op1385Eval G pl σ h).2.2)    (hhidden : rdhHidden G pl σ h (e.dir, e.target_state) = false) :    rdhForced G pl σ h (e.dir, e.target_state) = op1385EdgeSig e := by  classical  have hex : ∃ a ∈ G.edges,      a.source_node = (op1385Eval G pl σ h).2.1 ∧      a.source_state = (op1385Eval G pl σ h).2.2 ∧ a.dir = (e.dir, e.target_state).1 ∧        a.target_state = (e.dir, e.target_state).2 :=    ⟨e, he, hv, hq, rfl, rfl⟩  have hs := Classical.choose_spec hex  have hsame : Classical.choose hex = e :=    rdh_hidden_false_unique G pl σ h (e.dir, e.target_state) (Classical.choose hex) e      hs.1 he hs.2.1 hs.2.2.1 hs.2.2.2.1 hs.2.2.2.2 hv hq rfl rfl hhidden  unfold rdhForced  simp only [dif_pos hex, hsame]theorem rdh_history_hidden_compatible {Q M : Type} {k : ℕ}    (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (h : List (op1385Sig Q k)) (m : M) (v : List Bool) (q : Q)    (hh : PrioritizedBorelStrategyHistory G pl σ h m v q) :    rdhHiddenCompatible rdhVis (op1385Own G pl σ) (rdhHidden G pl σ)      (op1385Policy G pl σ) (rdhForced G pl σ) [] h := by  classical  induction hh with  | root => trivial  | @step h m v q e hh he hnode hstate hchoice ih =>    apply (rdh_hidden_compatible_snoc rdhVis (op1385Own G pl σ)      (rdhHidden G pl σ) (op1385Policy G pl σ) (rdhForced G pl σ)      [] h (op1385EdgeSig e)).2    refine ⟨ih, ?_⟩    simp only [List.nil_append]    have heval := op1385_eval_history G pl σ h m v q hh    have hnode' : e.source_node = (op1385Eval G pl σ h).2.1 := by simpa [heval] using hnode    have hstate' : e.source_state = (op1385Eval G pl σ h).2.2 := by simpa [heval] using hstate    by_cases howner : G.owner (v, q) = pl    · have ho : op1385Own G pl σ h = true := by simp [op1385Own, heval, howner]      have hs : op1385EdgeSig e = op1385Policy G pl σ h := by        simp only [op1385Policy, heval]        rw [hchoice howner]      simp [rdhHiddenStep, ho, hs]    · have ho : op1385Own G pl σ h = false := by simp [op1385Own, heval, howner]      cases hhidden : rdhHidden G pl σ h (e.dir, e.target_state) with      | true => simp [rdhHiddenStep, ho, op1385EdgeSig, rdhVis, hhidden]      | false =>        have hf := rdh_forced_eq G pl σ h e he hnode' hstate' hhidden        simpa [rdhHiddenStep, ho, op1385EdgeSig, rdhVis, hhidden] using hf.symmdef rdhReachableRecords {Q M : Type} {k : ℕ} (G : PrioritizedBorelGame Q k)    (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (v : List Bool) (q : Q) : Set (List (op1385Sig Q k)) :=  {r | ∃ h m, PrioritizedBorelStrategyHistory G pl σ h m v q ∧    rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) [] h = r}noncomputable def rdhBestRecord {Q M : Type} {k : ℕ}    [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]    (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (v : List Bool) (q : Q) : List (op1385Sig Q k) := by  classical  let S := rdhReachableRecords G pl σ v q  exact if hs : S.Nonempty then Classical.choose (wellFounded_lt.has_min S hs) else []lemma rdh_best_record_spec {Q M : Type} {k : ℕ}    [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]    (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (v : List Bool) (q : Q) (hs : (rdhReachableRecords G pl σ v q).Nonempty) :    rdhBestRecord G pl σ v q ∈ rdhReachableRecords G pl σ v q ∧      ∀ r ∈ rdhReachableRecords G pl σ v q, rdhBestRecord G pl σ v q ≤ r := by  classical  have hmin := Classical.choose_spec (wellFounded_lt.has_min (rdhReachableRecords G pl σ v q) hs)  have hbest : rdhBestRecord G pl σ v q =      Classical.choose (wellFounded_lt.has_min (rdhReachableRecords G pl σ v q) hs) := by    simp [rdhBestRecord, hs]  rw [hbest]  refine ⟨hmin.1, ?_⟩  intro r hr  exact le_of_not_gt (hmin.2 r hr)noncomputable def rdhRepresentative {Q M : Type} {k : ℕ}    [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]    (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (v : List Bool) (q : Q) : List (op1385Sig Q k) := by  classical  let S := rdhReachableRecords G pl σ v q  exact if hs : S.Nonempty then    Classical.choose ((rdh_best_record_spec G pl σ v q hs).1) else []lemma rdh_representative_spec {Q M : Type} {k : ℕ}    [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]    (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (v : List Bool) (q : Q) (hs : (rdhReachableRecords G pl σ v q).Nonempty) :    ∃ m, PrioritizedBorelStrategyHistory G pl σ (rdhRepresentative G pl σ v q) m v q ∧      rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) []        (rdhRepresentative G pl σ v q) = rdhBestRecord G pl σ v q := by  classical  have hmem := (rdh_best_record_spec G pl σ v q hs).1  have hrep : rdhRepresentative G pl σ v q = Classical.choose hmem := by    simp [rdhRepresentative, hs]  rw [hrep]  exact Classical.choose_spec hmemnoncomputable def rdhPositional {Q M : Type} {k : ℕ}    [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]    (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M) :    FiniteMemoryStrategy G pl Unit where  init_mem := ()  update := fun _ _ => ()  choice := fun _ v q => by    classical    exact if (rdhReachableRecords G pl σ v q).Nonempty then      σ.choice (op1385Eval G pl σ (rdhRepresentative G pl σ v q)).1 v q    else op1385Fallback G v q  choice_edge := by    classical    intro _ v q howner    split    · exact σ.choice_edge _ v q howner    · exact op1385_fallback_spec G v qlemma rdh_representative_extend {Q M : Type} {k : ℕ}    [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]    (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (v : List Bool) (q : Q) (hs : (rdhReachableRecords G pl σ v q).Nonempty)    (e : TreeGameEdge Q k) (he : e ∈ G.edges) (hv : e.source_node = v) (hq : e.source_state = q)    (hchosen : G.owner (v, q) = pl →      e = σ.choice (op1385Eval G pl σ (rdhRepresentative G pl σ v q)).1 v q) :    ∃ m, PrioritizedBorelStrategyHistory G pl σ      (rdhRepresentative G pl σ v q ++ [op1385EdgeSig e]) m (v ++ [e.dir]) e.target_state := by  obtain ⟨m, hh, _⟩ := rdh_representative_spec G pl σ v q hs  have heval := op1385_eval_history G pl σ _ m v q hh  refine ⟨σ.update m e, PrioritizedBorelStrategyHistory.step e hh he hv hq ?_⟩  intro howner  simpa [heval] using hchosen hownerlemma rdh_next_record_bound {Q M : Type} {k : ℕ}    [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]    (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (v : List Bool) (q : Q) (hs : (rdhReachableRecords G pl σ v q).Nonempty)    (e : TreeGameEdge Q k) (he : e ∈ G.edges) (hv : e.source_node = v) (hq : e.source_state = q)    (hchosen : G.owner (v, q) = pl →      e = σ.choice (op1385Eval G pl σ (rdhRepresentative G pl σ v q)).1 v q) :    (rdhReachableRecords G pl σ (v ++ [e.dir]) e.target_state).Nonempty ∧    rdhBestRecord G pl σ (v ++ [e.dir]) e.target_state ≤      rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) []        (rdhRepresentative G pl σ v q ++ [op1385EdgeSig e]) := by  obtain ⟨m, hh⟩ := rdh_representative_extend G pl σ v q hs e he hv hq hchosen  let r := rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) []    (rdhRepresentative G pl σ v q ++ [op1385EdgeSig e])  have hr : r ∈ rdhReachableRecords G pl σ (v ++ [e.dir]) e.target_state := by    exact ⟨_, m, hh, rfl⟩  have hne : (rdhReachableRecords G pl σ (v ++ [e.dir]) e.target_state).Nonempty := ⟨r, hr⟩  exact ⟨hne, (rdh_best_record_spec G pl σ (v ++ [e.dir]) e.target_state hne).2 r hr⟩theorem rdh_positional_reachable {Q M : Type} {k : ℕ}    [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]    (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (π : ℕ → TreeGameEdge Q k) (hlegal : ∀ n, π n ∈ G.edges)    (hinit : (π 0).source_node = [] ∧ (π 0).source_state = G.init_state)    (hnext : ∀ n, (π (n+1)).source_node = (π n).source_node ++ [(π n).dir] ∧      (π (n+1)).source_state = (π n).target_state)    (hfollow : ∀ n, G.owner ((π n).source_node, (π n).source_state) = pl →      π n = (rdhPositional G pl σ).choice () (π n).source_node (π n).source_state) :    ∀ n, (rdhReachableRecords G pl σ (π n).source_node (π n).source_state).Nonempty := by  classical  intro n  induction n with  | zero =>    rw [hinit.1, hinit.2]    refine ⟨[], [], σ.init_mem, PrioritizedBorelStrategyHistory.root, ?_⟩    rfl  | succ n ih =>    have hc : G.owner ((π n).source_node, (π n).source_state) = pl →        π n = σ.choice (op1385Eval G pl σ          (rdhRepresentative G pl σ (π n).source_node (π n).source_state)).1          (π n).source_node (π n).source_state := by      intro howner      simpa [rdhPositional, ih] using hfollow n howner    have hbound := rdh_next_record_bound G pl σ (π n).source_node (π n).source_state      ih (π n) (hlegal n) rfl rfl hc    rw [(hnext n).1, (hnext n).2]    exact hbound.1lemma rdh_extension_record_unchanged {Q M : Type} {k : ℕ}    [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]    (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (v : List Bool) (q : Q) (hs : (rdhReachableRecords G pl σ v q).Nonempty)    (e : TreeGameEdge Q k) (he : e ∈ G.edges) (hv : e.source_node = v) (hq : e.source_state = q)    (hnonhidden : G.owner (v, q) = pl ∨ ∀ e' ∈ G.edges,      e'.source_node = v → e'.source_state = q → e'.dir = e.dir →        e'.target_state = e.target_state → e' = e) :    rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) []      (rdhRepresentative G pl σ v q ++ [op1385EdgeSig e]) =    rdhBestRecord G pl σ v q := by  classical  obtain ⟨m, hh, hrec⟩ := rdh_representative_spec G pl σ v q hs  have heval := op1385_eval_history G pl σ _ m v q hh  have hstore : (!op1385Own G pl σ (rdhRepresentative G pl σ v q) &&      rdhHidden G pl σ (rdhRepresentative G pl σ v q) (e.dir, e.target_state)) = false := by    rcases hnonhidden with howner | hunique    · simp [op1385Own, heval, howner]    · have hn : ¬ ∃ a ∈ G.edges, ∃ a' ∈ G.edges,          a.source_node = v ∧ a.source_state = q ∧ a.dir = e.dir ∧ a.target_state = e.target_state ∧          a'.source_node = v ∧ a'.source_state = q ∧ a'.dir = e.dir ∧            a'.target_state = e.target_state ∧ a ≠ a' := by        rintro ⟨a, ha, a', ha', hav, haq, had, hat, hav', haq', had', hat', hne⟩        exact hne ((hunique a ha hav haq had hat).trans (hunique a' ha' hav' haq' had' hat').symm)      have hhfalse : rdhHidden G pl σ (rdhRepresentative G pl σ v q)          (e.dir, e.target_state) = false := by        simpa [rdhHidden, heval] using hn      simp [hhfalse]  rw [rdh_hidden_record_snoc]  simpa [op1385EdgeSig, rdhVis, hstore] using hrectheorem rdh_history_vis_unique {Q M : Type} {k : ℕ} (G : PrioritizedBorelGame Q k)    (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (hreverse : ∀ e ∈ G.edges, ∀ e' ∈ G.edges, e.source_node = e'.source_node →      e.dir = e'.dir → e.target_state = e'.target_state → e.source_state = e'.source_state)    (h : List (op1385Sig Q k)) (m : M) (v : List Bool) (q : Q)    (hh : PrioritizedBorelStrategyHistory G pl σ h m v q) :    ∀ (h' : List (op1385Sig Q k)) (m' : M), PrioritizedBorelStrategyHistory G pl σ h' m' v q →      h.map rdhVis = h'.map rdhVis := by  induction hh with  | root =>    intro h' m' hh'    have hn := op1385_eval_node G pl σ h'    rw [op1385_eval_history G pl σ h' m' [] G.init_state hh'] at hn    have hl := congrArg List.length hn    simp only [List.length_nil, List.length_map] at hl    have : h' = [] := List.eq_nil_of_length_eq_zero hl.symm    subst this    rfl  | @step h m v q e hh he hv hq hc ih =>    intro h' m' hh'    have hn := op1385_eval_node G pl σ h'    rw [op1385_eval_history G pl σ h' m' _ _ hh'] at hn    obtain ⟨h0, a, rfl⟩ : ∃ h0 a, h' = h0 ++ [a] := by      rcases List.eq_nil_or_concat h' with h0 | ⟨L, b, hL⟩      · subst h0        simp at hn      · exact ⟨L, b, by simpa using hL⟩    obtain ⟨m₀, v₀, q₀, e', hh0, he', hv', hq', _, ha, _, hvv, hqq⟩ :=      op1385_history_snoc_inv G pl σ _ m' _ _ hh' h0 a rfl    obtain ⟨hv0, hd⟩ := List.append_inj' hvv rfl    have hd' : e.dir = e'.dir := by simpa using hd    have hs := hreverse e he e' he' (hv.trans (hv0.trans hv'.symm)) hd' hqq    have hq0 : q = q₀ := hq.symm.trans (hs.trans hq')    subst hv0    subst hq0    have hih := ih h0 m₀ hh0    rw [← ha]    simp [List.map_append, hih, rdhVis, op1385EdgeSig, hd', hqq]theorem rdh_positional_representatives_stabilize {Q M : Type} {k : ℕ}    [LinearOrder (List (op1385Sig Q k))] [WellFoundedLT (List (op1385Sig Q k))]    (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (σ : FiniteMemoryStrategy G pl M)    (π : ℕ → TreeGameEdge Q k) (hlegal : ∀ n, π n ∈ G.edges)    (hinit : (π 0).source_node = [] ∧ (π 0).source_state = G.init_state)    (hnext : ∀ n, (π (n+1)).source_node = (π n).source_node ++ [(π n).dir] ∧      (π (n+1)).source_state = (π n).target_state)    (hfollow : ∀ n, G.owner ((π n).source_node, (π n).source_state) = pl →      π n = (rdhPositional G pl σ).choice () (π n).source_node (π n).source_state)    (hreverse : ∀ e ∈ G.edges, ∀ e' ∈ G.edges, e.source_node = e'.source_node →      e.dir = e'.dir → e.target_state = e'.target_state → e.source_state = e'.source_state)    (N : ℕ) (hnonhidden : ∀ 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.target_state = (π n).target_state → e = π n) :    ∃ K ≥ N, ∀ n ≥ K,      rdhRepresentative G pl σ (π (n+1)).source_node (π (n+1)).source_state =      rdhRepresentative G pl σ (π n).source_node (π n).source_state ++ [op1385EdgeSig (π n)] := by  classical  let histories : ℕ → List (op1385Sig Q k) := fun n =>    rdhRepresentative G pl σ (π n).source_node (π n).source_state  let actual : ℕ → op1385Sig Q k := fun n => op1385EdgeSig (π n)  have hreach := rdh_positional_reachable G pl σ π hlegal hinit hnext hfollow  have hrep (n : ℕ) : ∃ m, PrioritizedBorelStrategyHistory G pl σ (histories n) m      (π n).source_node (π n).source_state ∧      rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) [] (histories n) =        rdhBestRecord G pl σ (π n).source_node (π n).source_state :=    rdh_representative_spec G pl σ (π n).source_node (π n).source_state (hreach n)  have hcompat (n : ℕ) : rdhHiddenCompatible rdhVis (op1385Own G pl σ)      (rdhHidden G pl σ) (op1385Policy G pl σ) (rdhForced G pl σ) [] (histories n) := by    obtain ⟨m, hh, _⟩ := hrep n    exact rdh_history_hidden_compatible G pl σ _ m _ _ hh  have hnode (n : ℕ) : (histories n).map Prod.fst = (π n).source_node := by    obtain ⟨m, hh, _⟩ := hrep n    have heval := op1385_eval_history G pl σ (histories n) m _ _ hh    simpa [heval] using (op1385_eval_node G pl σ (histories n)).symm  have hchosen (n : ℕ) : G.owner ((π n).source_node, (π n).source_state) = pl →      π n = σ.choice (op1385Eval G pl σ (histories n)).1        (π n).source_node (π n).source_state := by    intro howner    simpa [histories, rdhPositional, hreach n] using hfollow n howner  have hext (n : ℕ) : rdhHiddenCompatible rdhVis (op1385Own G pl σ)      (rdhHidden G pl σ) (op1385Policy G pl σ) (rdhForced G pl σ) []      (histories n ++ [actual n]) := by    obtain ⟨m, hh⟩ := rdh_representative_extend G pl σ (π n).source_node (π n).source_state      (hreach n) (π n) (hlegal n) rfl rfl (hchosen n)    exact rdh_history_hidden_compatible G pl σ _ m _ _ hh  have hdir (n : ℕ) : (histories (n+1)).map rdhVis =      (histories n).map rdhVis ++ [rdhVis (actual n)] := by    obtain ⟨m, hh⟩ := rdh_representative_extend G pl σ (π n).source_node (π n).source_state      (hreach n) (π n) (hlegal n) rfl rfl (hchosen n)    obtain ⟨m', hh', _⟩ := hrep (n+1)    rw [(hnext n).1, (hnext n).2] at hh'    have hu := rdh_history_vis_unique G pl σ hreverse _ _ _ _ hh' _ _ hh    rw [hu, List.map_append]    rfl  have hrecord (n : ℕ) (hn : N ≤ n) :      rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) []        (histories n ++ [actual n]) =      rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) [] (histories n) := by    have heq := rdh_extension_record_unchanged G pl σ (π n).source_node (π n).source_state      (hreach n) (π n) (hlegal n) rfl rfl (hnonhidden n hn)    exact heq.trans (hrep n).choose_spec.2.symm  have hstep (n : ℕ) (hn : N ≤ n) :      rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) [] (histories (n+1)) ≤      rdhHiddenRecord rdhVis (op1385Own G pl σ) (rdhHidden G pl σ) [] (histories n) := by    have hb := (rdh_next_record_bound G pl σ (π n).source_node (π n).source_state      (hreach n) (π n) (hlegal n) rfl rfl (hchosen n)).2    rw [← (hnext n).1, ← (hnext n).2, ← (hrep (n+1)).choose_spec.2, hrecord n hn] at hb    exact hb  exact rdh_eventual_hidden_shadow rdhVis (op1385Own G pl σ) (rdhHidden G pl σ)    (op1385Policy G pl σ) (rdhForced G pl σ) histories actual N hcompat hdir    (fun n _ => hext n) hrecord hsteptheorem prioritized_borel_reverse_deterministic_finite_hidden_priorities_positional {Q : Type} {k : ℕ} (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (M : Type) (σ : FiniteMemoryStrategy G pl M) (hwin : PrioritizedBorelStrategyWins G pl σ) (hreverse : ∀ e ∈ G.edges, ∀ e' ∈ G.edges, e.source_node = e'.source_node → e.dir = e'.dir → e.target_state = e'.target_state → e.source_state = e'.source_state) (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.target_state = (π n).target_state → e = π n) : ∃ τ : FiniteMemoryStrategy G pl Unit, PrioritizedBorelStrategyWins G pl τ := by  classical  obtain ⟨ord, hwf⟩ := exists_wellFoundedLT (List (op1385Sig Q k))  letI : LinearOrder (List (op1385Sig Q k)) := ord  letI : WellFoundedLT (List (op1385Sig Q k)) := hwf  let τ := rdhPositional G pl σ  refine ⟨τ, ?_⟩  unfold PrioritizedBorelStrategyWins  intro π hlegal hinit hnext hmem  obtain ⟨mem, hm0, hmu, hchoice⟩ := hmem  have hfollow : ∀ n, G.owner ((π n).source_node, (π n).source_state) = pl →      π n = (rdhPositional G pl σ).choice () (π n).source_node (π n).source_state := by    intro n hn    have hm : mem n = () := Subsingleton.elim _ _    simpa [hm, τ] using hchoice n hn  obtain ⟨N, hnonhidden⟩ := hfinite π hlegal hinit hnext  obtain ⟨K, hKN, hstable⟩ :=    rdh_positional_representatives_stabilize G pl σ π hlegal hinit hnext hfollow hreverse N hnonhidden  let histories : ℕ → List (op1385Sig Q k) := fun n =>    rdhRepresentative G pl σ (π n).source_node (π n).source_state  let actual : ℕ → op1385Sig Q k := fun n => op1385EdgeSig (π n)  have hreach := rdh_positional_reachable G pl σ π hlegal hinit hnext hfollow  have hrep (n : ℕ) : ∃ m, PrioritizedBorelStrategyHistory G pl σ (histories n) m      (π n).source_node (π n).source_state := by    obtain ⟨m, hh, _⟩ := rdh_representative_spec G pl σ _ _ (hreach n)    exact ⟨m, hh⟩  have hnode (n : ℕ) : (histories n).map Prod.fst = (π n).source_node := by    obtain ⟨m, hh⟩ := hrep n    have heval := op1385_eval_history G pl σ (histories n) m _ _ hh    simpa [heval] using (op1385_eval_node G pl σ (histories n)).symm  have hnodes := op1385_play_nodes π hinit.1 (fun n => (hnext n).1)  have hlen (n : ℕ) : (histories n).length = n := by    have h := congrArg List.length (hnode n)    simpa [hnodes, op1385FnPrefix] using h  have hvis (n : ℕ) : (histories n).map Prod.fst =      List.ofFn (fun i : Fin n => Prod.fst (actual i)) := by    simpa [actual, op1385EdgeSig, op1385FnPrefix] using (hnode n).trans (hnodes n)  obtain ⟨f, hprefix, htail, hvisall⟩ :=    op1385_nested_histories_visible_shadow Prod.fst histories actual K hlen hvis hstable  have hrepall (n : ℕ) : ∃ m v q, PrioritizedBorelStrategyHistory G pl σ (histories n) m v q := by    obtain ⟨m, hh⟩ := hrep n    exact ⟨m, _, _, hh⟩  have hall := op1385_all_shadow_prefixes G pl σ histories f K hrepall hprefix  have hshadow := op1385_shadow_play_of_histories G pl σ f (by simpa [op1385FnPrefix] using hall)  let ρ := op1385ShadowEdge G pl σ f  have hw := hwin ρ hshadow.1 hshadow.2.1 hshadow.2.2.1 hshadow.2.2.2  have hdir : ∀ n, (π n).dir = (ρ n).dir := by    intro n    simpa [ρ, op1385ShadowEdge, op1385MakeEdge, actual, op1385EdgeSig] using (hvisall n).symm  have hprio : ∀ᶠ n in Filter.atTop, (π n).prio = (ρ n).prio := by    apply Filter.eventually_atTop.mpr    refine ⟨K, ?_⟩    intro n hn    simpa [ρ, op1385ShadowEdge, op1385MakeEdge, actual, op1385EdgeSig] using      congrArg (fun a : op1385Sig Q k => a.2.2) (htail n hn).symm  have hequiv := prioritized_borel_payoff_tail_congr G π ρ hdir hprio  cases pl with  | Eve => exact hequiv.mpr hw  | Adam => exact fun h => hw (hequiv.mp h)
See it in the graphDiscuss this resultChallenge it