PrioritizedBorelStrategyHistory
inductive
An encoded finite history follows legal edges from the initial position and agrees with the chosen strategy at its player's positions. Each code entry records the direction, target state, and priority, while the indices record the current memory, public node, and game state.
Statement
inductive PrioritizedBorelStrategyHistory {Q : Type} {k : ℕ} (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) {M : Type} (σ : FiniteMemoryStrategy G pl M) : List (Bool × Q × Fin k) → M → List Bool → Q → Prop | root : PrioritizedBorelStrategyHistory G pl σ [] σ.init_mem [] G.init_state | step {h m v q} (e : TreeGameEdge Q k) : PrioritizedBorelStrategyHistory G pl σ h m v q → e ∈ G.edges → e.source_node = v → e.source_state = q → (G.owner (v, q) = pl → e = σ.choice m v q) → PrioritizedBorelStrategyHistory G pl σ (h ++ [(e.dir, e.target_state, e.prio)]) (σ.update m e) (v ++ [e.dir]) e.target_state
- Source
- arXiv:2611.10136, Definitions 18 and 19; finite histories consistent with a given strategy
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Built on 4
- 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…
- 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.
- 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…
Lean source view module on GitHub
inductive PrioritizedBorelStrategyHistory {Q : Type} {k : ℕ} (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) {M : Type} (σ : FiniteMemoryStrategy G pl M) : List (Bool × Q × Fin k) → M → List Bool → Q → Prop | root : PrioritizedBorelStrategyHistory G pl σ [] σ.init_mem [] G.init_state | step {h m v q} (e : TreeGameEdge Q k) : PrioritizedBorelStrategyHistory G pl σ h m v q → e ∈ G.edges → e.source_node = v → e.source_state = q → (G.owner (v, q) = pl → e = σ.choice m v q) → PrioritizedBorelStrategyHistory G pl σ (h ++ [(e.dir, e.target_state, e.prio)]) (σ.update m e) (v ++ [e.dir]) e.target_state