prioritized_borel_eventual_hidden_shadow
Compatible finite histories whose hidden-choice records eventually do not increase and whose extensions add no hidden choices eventually form one nested history.
Statement
theorem prioritized_borel_eventual_hidden_shadow {A : Type} [LinearOrder (List A)] [WellFoundedLT (List A)] (vis : A → Bool) (own : List A → Bool) (hidden : List A → Bool → Bool) (policy : List A → A) (forced : List A → Bool → A) (histories : ℕ → List A) (actual : ℕ → A) (N : ℕ) (hcompat : ∀ n, op1385HiddenCompatible vis own hidden policy forced [] (histories n)) (hdir : ∀ n, (histories (n+1)).map vis = (histories n).map vis ++ [vis (actual n)]) (hext : ∀ n ≥ N, op1385HiddenCompatible vis own hidden policy forced [] (histories n ++ [actual n])) (hrecord : ∀ n ≥ N, op1385HiddenRecord vis own hidden [] (histories n ++ [actual n]) = op1385HiddenRecord vis own hidden [] (histories n)) (hstep : ∀ n ≥ N, op1385HiddenRecord vis own hidden [] (histories (n+1)) ≤ op1385HiddenRecord vis own hidden [] (histories n)) : ∃ K ≥ N, ∀ n ≥ K, histories (n+1) = histories n ++ [actual n]
- Source
- Hidden-choice strategy compression related to arXiv:2611.10136, Conjecture 19.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- Used by 2
- 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…
- prioritized_borel_reverse_deterministic_finite_hidden_priorities_positionalConsider a prioritized tree game. Assume that any two legal edges at the same source node with the same direction and target state have…
The proof, explained
The theorem shows that an eventually non-increasing sequence of compatible histories whose extensions add no hidden choices eventually becomes a nested history chain. To prove this, each history is assigned a rank given by its record of hidden choices; because the order on records is well-founded and the ranks are eventually non-increasing, the rank sequence stabilizes past some index K ≥ N. For all n ≥ K, the next history histories(n + 1) and the candidate extension histories(n) ++ [actual n] have the exact same visible observations and the exact same hidden record. Since execution replay uniquely reconstructs compatible histories from visible observations and hidden choices, this commonality forces the two histories to coincide.
The empty execution is correctly replayed from the empty observation and empty hidden record. automation
For the base case xs = [], the hidden record and visible observation sequences are both empty. Replaying on an empty visible sequence immediately returns the initial history and empty record, matching the claim by definition.
uses
op1385HiddenRecord,op1385HiddenReplayinduction xs generalizing hist with | nil => simp [op1385HiddenRecord, op1385HiddenReplay]
Any compatible execution step is correctly replayed, inductively recovering the full history.
In the inductive step for a :: xs, we analyze whether the history is owned (own hist) and whether the visible signal is hidden (hidden hist (vis a)). If owned, the single-step rule forces a = policy hist, and replay follows the policy without consuming from the record. If not owned and hidden, a is pushed to the hidden record, and replay consumes a from the head of the record. If not owned and unhidden, the step forces a = forced hist (vis a), which replay reproduces from the visible observation alone. In all branches, applying the induction hypothesis to hist ++ [a] recovers the remaining history.
uses
op1385HiddenCompatible,op1385HiddenStep,op1385HiddenRecord,op1385HiddenReplay,List.append_assoc| cons a xs ih => simp only [op1385HiddenCompatible] at h cases ho : own hist <;> cases hb : hidden hist (vis a) · have ha' : a = forced hist (vis a) := by simpa [op1385HiddenStep, ho, hb] using h.1 have ha : forced hist (vis a) = a := ha'.symm simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, ha, List.append_assoc] using ih (hist ++ [a]) h.2 · simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, List.append_assoc] using ih (hist ++ [a]) h.2 · have ha : a = policy hist := by simpa [op1385HiddenStep, ho, hb] using h.1 subst a simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, List.append_assoc] using ih (hist ++ [policy hist]) h.2 · have ha : a = policy hist := by simpa [op1385HiddenStep, ho, hb] using h.1 subst a simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, List.append_assoc] using ih (hist ++ [policy hist]) h.2Compatible executions with identical visible observations and identical hidden records are equal.
Replaying both compatible sequences xs and ys with their common visible traces and hidden records yields some (hist ++ xs, []) and some (hist ++ ys, []). Equating these two outputs gives hist ++ xs = hist ++ ys, from which left cancellation of hist gives xs = ys.
uses
op1385_hidden_replay_recovers,congrArg,Prod.fst,Option.some.inj,List.append_cancel_lefthave hx' := op1385_hidden_replay_recovers vis own hidden policy forced hist xs hx have hy' := op1385_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 an extended sequence xs ++ [a] is equivalent to compatibility of xs followed by a valid step for a. automation
Proved by induction on xs. The base case follows directly from the definition of op1385HiddenCompatible. For the inductive step x :: xs, expanding the definition, rewriting with the inductive hypothesis, and reassociating conjunctions closes the equivalence.
uses
op1385HiddenCompatible,List.append_assoc,and_associnduction xs generalizing hist with | nil => simp [op1385HiddenCompatible] | cons x xs ih => simp [op1385HiddenCompatible, ih, List.append_assoc, and_assoc]
The hidden record of an extended sequence xs ++ [a] appends [a] if and only if the final step was an unforced hidden choice. automation
Proved by induction on xs. The base case holds by definition. For the inductive step x :: xs, case analysis on whether the head step was an unforced hidden choice followed by simplification and associativity of list append closes the goal.
uses
op1385HiddenRecord,List.append_associnduction xs generalizing hist with | nil => simp [op1385HiddenRecord] | cons x xs ih => cases hb : (!own hist && hidden hist (vis x)) <;> simp [op1385HiddenRecord, hb, ih, List.append_assoc]
The shifted sequence f(n) = r(N + n) is antitone on all of ℕ.
Because r is non-increasing past N, we have r(N + n + 1) ≤ r(N + n) for all n ≥ 0. By antitone_nat_of_succ_le, an ordering between every consecutive pair implies that the shifted sequence f is antitone.
uses
antitone_nat_of_succ_le,Nat.add_assoclet f : ℕ → α := fun n => r (N+n) have hmono : Antitone f := by apply antitone_nat_of_succ_le intro n have h := hstep (N+n) (by omega) simpa [f, Nat.add_assoc] using h
An eventually antitone sequence in a well-founded partial order eventually stabilizes.
By the antitone chain condition for well-founded orders (WellFoundedLT.antitone_chain_condition), the antitone sequence f stabilizes at some K, meaning f(m) = f(K) for all m ≥ K. Setting the cutoff to N + K ≥ N, for any n ≥ N + K we have n - N ≥ K, so r(n) = f(n - N) = f(K) = r(N + K).
uses
WellFoundedLT.antitone_chain_condition,Nat.add_sub_of_leobtain ⟨K, hK⟩ := WellFoundedLT.antitone_chain_condition hmono refine ⟨N+K, by omega, ?_⟩ intro n hn have hstart : N ≤ n := by omega have hi : K ≤ n-N := by omega have h := hK (n-N) hi change r (N+K) = r (N+(n-N)) at h simpa only [Nat.add_sub_of_le hstart] using h.symm
The hidden records rank n = op1385HiddenRecord [] (histories n) eventually stabilize at some K ≥ N.
The rank sequence is non-increasing for n ≥ N by hypothesis hstep. Since the order on List A is well-founded, the stabilization lemma op1385_eventually_antitone_well_order_stabilizes yields an index K ≥ N such that rank n = rank K for all n ≥ K.
uses
op1385_eventually_antitone_well_order_stabilizes,le_translet rank : ℕ → List A := fun n => op1385HiddenRecord 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
For all n ≥ K, histories (n + 1) and histories n ++ [actual n] have identical hidden records.
By hypothesis hrecord, appending actual n does not change the hidden record of histories n for n ≥ N. Since n ≥ K ≥ N, stabilization gives rank (n + 1) = rank K = rank n, so the hidden record of histories (n + 1) equals that of histories n ++ [actual n].
have hrec : op1385HiddenRecord vis own hidden [] (histories (n+1)) = op1385HiddenRecord vis own hidden [] (histories n ++ [actual n]) := by rw [hrecord n hnN] exact (hstable (n+1) (by omega)).trans (hstable n hn).symm
For all n ≥ K, histories (n + 1) = histories n ++ [actual n].
Both histories (n + 1) and histories n ++ [actual n] are compatible executions extending the empty history. Their visible traces coincide by hdir, and their hidden records coincide by the previous step. Injectivity of the hidden record (op1385_hidden_record_injective) implies they are identical.
uses
op1385_hidden_record_injectiveapply op1385_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
op1385HiddenRecord- Extracts the list of actions corresponding to unowned, hidden choice steps in an execution sequence.
op1385HiddenReplay- Deterministically reconstructs an execution from an initial history, a sequence of visible observations, and a record of hidden choices.
op1385HiddenCompatible- States that a sequence of actions is valid starting from a given history, with each action satisfying the single-step rules.
op1385HiddenStep- Defines a valid single action from a history: governed by policy if owned, unconstrained if hidden, or forced by the visible signal otherwise.
List.append_assoc- List concatenation is associative: (as ++ bs) ++ cs = as ++ (bs ++ cs).
op1385_hidden_replay_recovers- Replaying a compatible execution using its visible trace and hidden record successfully reconstructs the complete history and completely consumes the record.
Option.some.inj- The some constructor of Option is injective: some x = some y implies x = y.
congrArg- Applying a function to equal arguments yields equal values: x = y implies f(x) = f(y).
Prod.fst- The first projection of a pair: Prod.fst (a, b) = a.
List.append_cancel_left- Left cancellation for list concatenation: as ++ bs = as ++ cs implies bs = cs.
and_assoc- Conjunction is associative: (a ∧ b) ∧ c ↔ a ∧ b ∧ c.
antitone_nat_of_succ_le- A function on ℕ is antitone (order-reversing) if f(n + 1) ≤ f(n) for every n.
Nat.add_assoc- Addition of natural numbers is associative: (n + m) + k = n + (m + k).
WellFoundedLT.antitone_chain_condition- Every antitone sequence in a well-founded partially ordered set eventually stabilizes.
Nat.add_sub_of_le- For natural numbers with a ≤ b, a + (b - a) = b.
op1385_eventually_antitone_well_order_stabilizes- Any sequence in a well-founded partial order that is non-increasing beyond an index N eventually becomes constant at some K ≥ N.
le_trans- Transitivity of the order relation: a ≤ b and b ≤ c imply a ≤ c.
op1385_hidden_record_injective- Two compatible executions that produce identical visible sequences and identical hidden records are equal.
- The proof relies on several helper lemmas established in the file: correctness of execution replay, injectivity of the hidden choice record, and stabilization of eventually antitone sequences in well-founded orders.
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 op1385HiddenStep {A : Type} (vis : A → Bool) (own : List A → Bool) (hidden : List A → Bool → Bool) (policy : List A → A) (forced : List A → Bool → 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 op1385HiddenCompatible {A : Type} (vis : A → Bool) (own : List A → Bool) (hidden : List A → Bool → Bool) (policy : List A → A) (forced : List A → Bool → A) : List A → List A → Prop | _, [] => True | hist, a :: rest => op1385HiddenStep vis own hidden policy forced hist a ∧ op1385HiddenCompatible vis own hidden policy forced (hist ++ [a]) restdef op1385HiddenRecord {A : Type} (vis : A → Bool) (own : List A → Bool) (hidden : List A → Bool → Bool) : List A → List A → List A | _, [] => [] | hist, a :: rest => if !own hist && hidden hist (vis a) then a :: op1385HiddenRecord vis own hidden (hist ++ [a]) rest else op1385HiddenRecord vis own hidden (hist ++ [a]) restdef op1385HiddenReplay {A : Type} (vis : A → Bool) (own : List A → Bool) (hidden : List A → Bool → Bool) (policy : List A → A) (forced : List A → Bool → A) : List A → List Bool → 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 op1385HiddenReplay 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 op1385HiddenReplay vis own hidden policy forced (hist ++ [a]) bs tail else none else let a := forced hist b if vis a = b then op1385HiddenReplay vis own hidden policy forced (hist ++ [a]) bs record else nonetheorem op1385_hidden_replay_recovers {A : Type} (vis : A → Bool) (own : List A → Bool) (hidden : List A → Bool → Bool) (policy : List A → A) (forced : List A → Bool → A) (hist xs : List A) (h : op1385HiddenCompatible vis own hidden policy forced hist xs) : op1385HiddenReplay vis own hidden policy forced hist (xs.map vis) (op1385HiddenRecord vis own hidden hist xs) = some (hist ++ xs, []) := by induction xs generalizing hist with | nil => simp [op1385HiddenRecord, op1385HiddenReplay] | cons a xs ih => simp only [op1385HiddenCompatible] at h cases ho : own hist <;> cases hb : hidden hist (vis a) · have ha' : a = forced hist (vis a) := by simpa [op1385HiddenStep, ho, hb] using h.1 have ha : forced hist (vis a) = a := ha'.symm simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, ha, List.append_assoc] using ih (hist ++ [a]) h.2 · simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, List.append_assoc] using ih (hist ++ [a]) h.2 · have ha : a = policy hist := by simpa [op1385HiddenStep, ho, hb] using h.1 subst a simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, List.append_assoc] using ih (hist ++ [policy hist]) h.2 · have ha : a = policy hist := by simpa [op1385HiddenStep, ho, hb] using h.1 subst a simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, List.append_assoc] using ih (hist ++ [policy hist]) h.2theorem op1385_hidden_record_injective {A : Type} (vis : A → Bool) (own : List A → Bool) (hidden : List A → Bool → Bool) (policy : List A → A) (forced : List A → Bool → A) (hist xs ys : List A) (hx : op1385HiddenCompatible vis own hidden policy forced hist xs) (hy : op1385HiddenCompatible vis own hidden policy forced hist ys) (hvis : xs.map vis = ys.map vis) (hrecord : op1385HiddenRecord vis own hidden hist xs = op1385HiddenRecord vis own hidden hist ys) : xs = ys := by have hx' := op1385_hidden_replay_recovers vis own hidden policy forced hist xs hx have hy' := op1385_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 op1385_hidden_compatible_snoc {A : Type} (vis : A → Bool) (own : List A → Bool) (hidden : List A → Bool → Bool) (policy : List A → A) (forced : List A → Bool → A) (hist xs : List A) (a : A) : op1385HiddenCompatible vis own hidden policy forced hist (xs ++ [a]) ↔ op1385HiddenCompatible vis own hidden policy forced hist xs ∧ op1385HiddenStep vis own hidden policy forced (hist ++ xs) a := by induction xs generalizing hist with | nil => simp [op1385HiddenCompatible] | cons x xs ih => simp [op1385HiddenCompatible, ih, List.append_assoc, and_assoc]theorem op1385_hidden_record_snoc {A : Type} (vis : A → Bool) (own : List A → Bool) (hidden : List A → Bool → Bool) (hist xs : List A) (a : A) : op1385HiddenRecord vis own hidden hist (xs ++ [a]) = op1385HiddenRecord 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 [op1385HiddenRecord] | cons x xs ih => cases hb : (!own hist && hidden hist (vis x)) <;> simp [op1385HiddenRecord, hb, ih, List.append_assoc]theorem op1385_eventually_antitone_well_order_stabilizes {α : Type} [PartialOrder α] [WellFoundedLT α] (r : ℕ → α) (N : ℕ) (hstep : ∀ n ≥ N, r (n+1) ≤ r n) : ∃ K ≥ N, ∀ n ≥ K, r n = r K := by let f : ℕ → α := fun n => r (N+n) have hmono : Antitone f := by apply antitone_nat_of_succ_le intro n have h := hstep (N+n) (by omega) simpa [f, Nat.add_assoc] using h obtain ⟨K, hK⟩ := WellFoundedLT.antitone_chain_condition hmono refine ⟨N+K, by omega, ?_⟩ intro n hn have hstart : N ≤ n := by omega have hi : K ≤ n-N := by omega have h := hK (n-N) hi change r (N+K) = r (N+(n-N)) at h simpa only [Nat.add_sub_of_le hstart] using h.symmtheorem prioritized_borel_eventual_hidden_shadow {A : Type} [LinearOrder (List A)] [WellFoundedLT (List A)] (vis : A → Bool) (own : List A → Bool) (hidden : List A → Bool → Bool) (policy : List A → A) (forced : List A → Bool → A) (histories : ℕ → List A) (actual : ℕ → A) (N : ℕ) (hcompat : ∀ n, op1385HiddenCompatible vis own hidden policy forced [] (histories n)) (hdir : ∀ n, (histories (n+1)).map vis = (histories n).map vis ++ [vis (actual n)]) (hext : ∀ n ≥ N, op1385HiddenCompatible vis own hidden policy forced [] (histories n ++ [actual n])) (hrecord : ∀ n ≥ N, op1385HiddenRecord vis own hidden [] (histories n ++ [actual n]) = op1385HiddenRecord vis own hidden [] (histories n)) (hstep : ∀ n ≥ N, op1385HiddenRecord vis own hidden [] (histories (n+1)) ≤ op1385HiddenRecord vis own hidden [] (histories n)) : ∃ K ≥ N, ∀ n ≥ K, histories (n+1) = histories n ++ [actual n] := by let rank : ℕ → List A := fun n => op1385HiddenRecord 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 : op1385HiddenRecord vis own hidden [] (histories (n+1)) = op1385HiddenRecord vis own hidden [] (histories n ++ [actual n]) := by rw [hrecord n hnN] exact (hstable (n+1) (by omega)).trans (hstable n hn).symm apply op1385_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