Arena
structureimported Lean
A game arena: the pure dynamics of an extensive-form game. States, actions, and transitions are stored without players, payoffs, or probability. A state is terminal iff Action s is empty.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in structure Arena
- Defined in
- EconCSLib, `Arena`
- Lean proof
- By Lazyfill (from the file's git history), from github.com/gametheoryinlean/EconCSLib at
1a88f809b538(Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.Arena← Arena (EconCSLib/GameTheory/ExtensiveGame/Structural/Basic.lean:35): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Used by 110
- ExtensiveGame.BehaviorProfile.restrictSubgame_eq_selfExtensiveGame.BehaviorProfile.restrictSubgame_eq_self
- ExtensiveGame.finalStateThe final state reached from
initafter at mostfuelsteps. - ExtensiveGame.expectedPayoffFinite-fuel expected payoff from the initial state under a behavior profile.
- ExtensiveGame.reachableSubgameAt_nextExtensiveGame.reachableSubgameAt_next
- ExtensiveGame.BehaviorStrategy.IsCompletelyMixedA behavior strategy is completely mixed if every available action at every state controlled by the player receives positive probability.…
- Arena.Reachable.transReachability is transitive.
- ExtensiveGame.BehaviorStrategy.restrictReachableSubgameRestrict a behavior strategy to the subtype subgame consisting only of states reachable from
root. - ExtensiveGame.BehaviorProfile.deviate_sameExtensiveGame.BehaviorProfile.deviate_same
- ExtensiveGame.BehaviorStrategy.liftSubgame_eq_selfExtensiveGame.BehaviorStrategy.liftSubgame_eq_self
- ExtensiveGame.actionsAvailable actions at a state.
- Arena.finalState_zeroArena.finalState_zero
- ControlledGame.IsReachableA state is reachable in a controlled game if it is reachable from its distinguished initial state.
- ExtensiveGame.ofControlledGame_toControlledGameExtensiveGame.ofControlledGame_toControlledGame
- ExtensiveGame.isNonPlayerState_iff_toControlledGameThe historical payoff-aware non-player-state predicate is exactly the canonical controlled-game predicate.
- ExtensiveGame.ofArena_payoffExtensiveGame.ofArena_payoff
- ExtensiveGame.reachableSubgameAt_action_fintypeExtensiveGame.reachableSubgameAt_action_fintype
- ControlledGame.NoChanceEvery nonterminal state has a strategic mover.
- ExtensiveGame.arenaThe arena of a game.
- ExtensiveGame.subgameAt_isEmpty_decidableExtensiveGame.subgameAt_isEmpty_decidable
- ExtensiveGame.BehaviorStrategy.restrictSubgame_liftSubgameExtensiveGame.BehaviorStrategy.restrictSubgame_liftSubgame
- ExtensiveGame.subgameAt_initExtensiveGame.subgameAt_init
- ControlledGame.ofArena_toArenaControlledGame.ofArena_toArena
- ControlledGame.IsReachable.nextA legal successor of a reachable state is reachable.
- Arena.IsTerminalA state is terminal if there are no available actions.
- ExtensiveGame.StrategyA strategy for player
i: at each nonterminal state whereiis the mover, specify which action to take. The nonterminal premise is… - ExtensiveGame.subgameAt_nextExtensiveGame.subgameAt_next
- ExtensiveGame.isPlayerStateA state is controlled by player
i. - ExtensiveGame.BehaviorProfile.probAtThe probability that a behavior profile assigns to action
aat a state controlled by playeri. - ControlledGame.ofArena_moverControlledGame.ofArena_mover
- ControlledGame.arenaThe arena of a payoff-free controlled game.
- ControlledGame.isTerminalA state is terminal.
- ControlledGame.ofArena_initControlledGame.ofArena_init
- ExtensiveGame.reachableSubgameAt_moverExtensiveGame.reachableSubgameAt_mover
- ExtensiveGame.BehaviorProfile.deviateUnilateral deviation of a behavior profile: player
whoswitches tobeta', while every other player keeps the original behavior strategy. - ExtensiveGame.ofControlledGame_toControlledGame_selfForgetting an existing payoff-aware game and then reattaching its payoff recovers the original game definitionally.
- ControlledGame.isNonPlayerStateA nonterminal state carrying the non-player-control label. This predicate deliberately supplies no probability law.
- ExtensiveGame.BehaviorStrategy.liftReachableSubgameLift a reachable-subgame behavior strategy to the original game, preserving the baseline strategy outside the reachable subgame.
- ExtensiveGame.BehaviorProfile.actionProbThe action probability induced by a behavior profile at a state. At a player-controlled state this reads the controlling player's behavior…
- ExtensiveGame.ofArena_moverExtensiveGame.ofArena_mover
- ExtensiveGame.BehaviorStrategy.liftSubgameView a behavior strategy for a subgame as a behavior strategy for the original game. This is well-typed because
subgameAtkeeps the same… - ExtensiveGame.reachProbFromFinite-fuel probability of reaching
targetfromstartunder a behavior profile. The definition records the probability of hitting… - Arena.IsDecisionA state is a decision point if it has at least one available action.
- ExtensiveGame.subgameAtThe subgame starting at state
s: same arena, different starting point. - ExtensiveGame.subgameAt_action_fintypeExtensiveGame.subgameAt_action_fintype
- ExtensiveGame.ofArenaAdd an initial state, mover assignment, and payoff function to an ordinary arena. All game-semantic data are explicit arguments; in…
- ExtensiveGame.extractTerminalGameTreeTerminal states extract to one-leaf
GameTrees. - ExtensiveGame.isPlayerState_iff_toControlledGameThe historical payoff-aware player-state predicate is exactly the canonical controlled-game predicate.
- ControlledGame.ofArenaAdd an initial state and mover assignment to an ordinary arena.
- ExtensiveGame.isChanceStateCompatibility name for
isNonPlayerState. No chance law is implied by this predicate alone. - ExtensiveGame.BehaviorProfile.restrictSubgame_liftSubgameExtensiveGame.BehaviorProfile.restrictSubgame_liftSubgame
- ExtensiveGame.BehaviorProfile.IsCompletelyMixedWithPositiveReach.mixedThe complete-mixing component of
IsCompletelyMixedWithPositiveReach. - Arena.ReachableA state
tis reachable fromsif a finite legal path leads fromstot. - ExtensiveGame.reachProbFinite-fuel probability of reaching
targetfrom the initial state. - ExtensiveGame.BehaviorProfile.actionProb_nonnegA behavior profile assigns nonnegative probability to every action.
- Arena.Reachable.step'Taking one legal action extends a reachable path.
- ExtensiveGame.BehaviorProfileA behavior-strategy profile: one behavior strategy for every player.
- ControlledGame.actionsAvailable actions at a state.
- ExtensiveGame.ofArena_toArenaExtensiveGame.ofArena_toArena
- ExtensiveGame.reachableSubgameAtThe subgame whose state space is restricted to states reachable from
root. The oldersubgameAtview changes only the initial state.… - ExtensiveGame.subgameAt_arenaThe arena of a subgame is the same arena.
- ExtensiveGame.ExtractsGameTree.spe_on_to_nash_atOn any extracted tree, root-scoped subgame perfection implies root Nash equilibrium through the ordinary
GameTreeequilibrium API. - ExtensiveGame.finalPayoffPayoff at the final state for player
i. - ExtensiveGame.BehaviorProfile.IsCompletelyMixedWithPositiveReach.reach_posThe positive-reach component of
IsCompletelyMixedWithPositiveReach. - ControlledGameA payoff-free controlled extensive-game skeleton.
ControlledGameadds only a distinguished initial state and a mover label to the pure… - ExtensiveGame.BehaviorProfile.actionProb_restrictSubgameExtensiveGame.BehaviorProfile.actionProb_restrictSubgame
- ExtensiveGame.BehaviorStrategyA behavior strategy for player
i: at every nonterminal state controlled byi, choose a probability distribution over the actions… - ExtensiveGame.extractTerminal_extractsThe certified terminal-state extractor satisfies the relational extraction interface.
- Arena.ofFinBuild an arena from a
Fin-indexed state space with finite action types. Terminal states havenActions s = 0. - ExtensiveGame.BehaviorProfile.IsCompletelyMixedA behavior profile is completely mixed if each player's behavior strategy is completely mixed.
- ExtensiveGame.isReachable_iff_toControlledGameThe historical payoff-aware reachability predicate is exactly the canonical controlled-game predicate.
- ExtensiveGame.extractTerminal_payoffExtensiveGame.extractTerminal_payoff
- ExtensiveGame.BehaviorProfile.restrictReachableSubgame_liftReachableSubgameExtensiveGame.BehaviorProfile.restrictReachableSubgame_liftReachableSubgame
- ControlledGame.isChanceStateCompatibility name for a non-player-controlled nonterminal state. This structural predicate does not assert that a chance law exists.…
- Arena.finalState_succArena.finalState_succ
- ExtensiveGame.playPlay the game from
initfor at mostfuelsteps. Requires a default action chooser for all states (including chance). - ExtensiveGame.BehaviorProfile.restrictReachableSubgameRestrict a behavior profile to the subtype subgame of states reachable from
root. - ExtensiveGame.isNonPlayerStateA nonterminal state carrying the non-player-control label. This predicate supplies no probability law.
- ExtensiveGame.ExtractsGameTree.node_head_reachableAt an extracted decision node, the head child is reached by one Arena transition and itself has an extracted subtree.
- ExtensiveGame.ofArena_initExtensiveGame.ofArena_init
- ExtensiveGame.BehaviorStrategy.restrictSubgame_eq_selfExtensiveGame.BehaviorStrategy.restrictSubgame_eq_self
- Arena.finalStateThe final state after at most
fuelsteps. - ExtensiveGame.BehaviorStrategy.restrictReachableSubgame_liftReachableSubgameExtensiveGame.BehaviorStrategy.restrictReachableSubgame_liftReachableSubgame
- ExtensiveGame.BehaviorProfile.restrictSubgameRestrict a behavior profile to the subgame rooted at
root. - ExtensiveGame.isTerminalA state is terminal.
- ExtensiveGame.FiniteExtractableAssumptions under which an Arena-style game can be extracted to a finite no-chance
GameTree. The actual recursive extraction is… - ExtensiveGame.BehaviorProfile.IsCompletelyMixed.actionProb_posAt player-controlled states, a completely mixed behavior profile gives positive probability to every available action.
- ExtensiveGame.reachableSubgameAt_isEmpty_decidableExtensiveGame.reachableSubgameAt_isEmpty_decidable
- ExtensiveGame.TreeShapedFromA weak tree-shapedness condition: any two paths from the root to the same state are equal as reachability proofs. This is intentionally…
- ExtensiveGame.subgameAt_moverExtensiveGame.subgameAt_mover
- ExtensiveGame.BehaviorStrategy.restrictSubgameRestrict a behavior strategy to the subgame rooted at
root. SincesubgameAtkeeps the same state space, actions, and movers, this is… - ExtensiveGame.BehaviorProfile.IsCompletelyMixed.playerA completely mixed behavior profile gives a completely mixed behavior strategy for each player.
- ExtensiveGame.IsReachableA state is reachable in the game if it is reachable from
init. - ExtensiveGame.BehaviorProfile.liftSubgameView a behavior profile for a subgame as a behavior profile for the original game.
- ExtensiveGame.IsReachable.nextIf
sis reachable and we take actiona, thennext s ais reachable. - ExtensiveGame.BehaviorProfile.IsCompletelyMixedWithPositiveReachCompletely mixed behavior together with the current positive-reach interface for every subgame root at a fixed fuel. In finite games with…
- ControlledGame.isPlayerStateA state is controlled by player
i. - ExtensiveGame.ofControlledGame_payoffExtensiveGame.ofControlledGame_payoff
- Arena.playPlay the game for at most
fuelsteps, usingchooseto pick actions. Returns the sequence of states visited. - Arena.isTerminal_iff_not_isDecisionTerminal and decision states are complementary.
- ExtensiveGame.reachableSubgameAt_initExtensiveGame.reachableSubgameAt_init
- ExtensiveGame.ExtractsGameTreeExtensiveGame.ExtractsGameTree
- ExtensiveGame.StrategyProfile.actionAtGiven a strategy profile, extract the action at a nonterminal player-controlled state. Returns
nonewhen the state is… - ExtensiveGame.ExtractsGameTree.leaf_payoffIf an Arena state extracts to a leaf, the leaf payoff is exactly the Arena payoff at that state.
- ExtensiveGame.ofControlledGameAdd a state-based payoff interpretation to a payoff-free controlled game. Forgetting the result with
ExtensiveGame.toControlledGame… - ExtensiveGame.reachableSubgameAt_payoffExtensiveGame.reachableSubgameAt_payoff
- ExtensiveGameA state-payoff extensive game: a payoff-free controlled game together with a convenient endpoint-state payoff. *
mover s= who controls… - ExtensiveGame.subgameAt_payoffExtensiveGame.subgameAt_payoff
- ExtensiveGame.ActionListCompleteA nonempty action list
head :: tailcontains every available action at states. The list is an explicit finite enumeration supplied by… - ExtensiveGame.BehaviorProfile.liftReachableSubgameLift a reachable-subgame behavior profile to the original game, preserving the baseline profile outside the reachable subgame.
- ExtensiveGame.expectedPayoffFromFinite-fuel expected payoff from
startunder a behavior profile. If the fuel runs out, or if a terminal state is reached, the current…
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in /-- A game arena: the pure dynamics of an extensive-form game. States, actions, and transitions are stored without players, payoffs, or probability. A state is terminal iff `Action s` is empty. -/ structure Arena where /-- The state space. -/ State : Type* /-- Available actions at each state. Empty means terminal. -/ Action : State → Type* /-- Transition function from a state and one legal action. -/ next : (s : State) → Action s → State