AFTD Auto-Formalizing Theoretical Domains

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

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