prioritized_borel_reverse_deterministic_finite_hidden_priorities_positional
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - 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 π.
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.
uses
rdhHiddenRecord,rdhHiddenReplay,rdhHiddenCompatible,rdhHiddenStepinduction 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
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.
uses
rdh_hidden_replay_recovers,List.append_cancel_lefttheorem 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))
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.
uses
rdhHiddenCompatible,rdhHiddenSteptheorem 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]
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.
uses
rdhHiddenRecordtheorem 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]
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].
uses
op1385_eventually_antitone_well_order_stabilizes,rdh_hidden_record_injectivetheorem 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
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.
uses
op1385Eval,Classical.choosedef 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)
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).
uses
rdh_hidden_false_unique,rdh_forced_eq,Classical.choose_spec,dif_poslemma 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]
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).
uses
rdh_hidden_compatible_snoc,op1385_eval_history,rdh_forced_eqtheorem 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
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).
uses
rdh_best_record_spec,rdh_representative_spec,le_of_not_gtdef 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
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.
uses
op1385Fallback,op1385_fallback_specnoncomputable 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
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.
uses
rdh_representative_spec,rdh_representative_extend,rdh_next_record_bound,rdh_best_record_speclemma 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⟩
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.
uses
PrioritizedBorelStrategyHistory.root,rdh_next_record_boundtheorem 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
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.
uses
rdh_representative_spec,op1385_eval_history,rdh_hidden_record_snoclemma 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
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.
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]
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)].
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_shadowtheorem 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
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.
uses
exists_wellFoundedLT,rdhPositional,Subsingleton.elim,rdh_positional_representatives_stabilize,rdh_positional_reachable,rdh_representative_spectheorem 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⟩
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 σ.
uses
op1385_eval_node,op1385_play_nodes,op1385_nested_histories_visible_shadow,op1385_all_shadow_prefixes,op1385_shadow_play_of_historieshave 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
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.
uses
op1385ShadowEdge,Filter.eventually_atTop.mpr,prioritized_borel_payoff_tail_congrhave 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.
- The proof relies on noncomputable classical choice and the well-ordering theorem (`exists_wellFoundedLT`) to choose a well-founded linear order on the set of history lists and select minimal representative histories.
- Several intermediate constructions (`rdhHidden`, `rdhForced`, `rdhBestRecord`, `rdhRepresentative`, `rdhPositional`) are marked noncomputable because they use classical case splits and existential quantification over game edges.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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)