ExtensiveGame
structureimported Lean
A state-payoff extensive game: a payoff-free controlled game together with a convenient endpoint-state payoff. * mover s = who controls state s (none = non-player-controlled) * payoff s i = payoff for player i at state s (meaningful at terminal states) General terminal-history, complete-path, and winning-condition semantics are separate objective layers; this field is not their authoritative definition. No isTerminal field — terminal states are detected by IsEmpty (Action s). No proof terms to carry around.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in structure ExtensiveGame (N : Type*) (U : Type*) extends ControlledGame N
- Defined in
- EconCSLib, `ExtensiveGame`
- Lean proof
- By xbei, 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.ExtensiveGame← ExtensiveGame (EconCSLib/GameTheory/ExtensiveGame/Basic.lean:43): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 2
- ArenaA game arena: the pure dynamics of an extensive-form game. States, actions, and transitions are stored without players, payoffs, or…
- ControlledGameA payoff-free controlled extensive-game skeleton.
ControlledGameadds only a distinguished initial state and a mover label to the pure…
- Used by 89
- 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.…
- 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.controlledGameForget only the state-payoff interpretation. This is a lossless projection for dynamics, the initial root, and mover data. It is the…
- ExtensiveGame.BehaviorStrategy.liftSubgame_eq_selfExtensiveGame.BehaviorStrategy.liftSubgame_eq_self
- ExtensiveGame.actionsAvailable actions at a 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
- ExtensiveGame.NoChanceNo chance nodes: every 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
- ExtensiveGame.noChance_iff_toControlledGameThe historical payoff-aware no-chance predicate is exactly the canonical controlled-game predicate.
- 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. - 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.
- 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… - 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.
- 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. - ExtensiveGame.reachProbFinite-fuel probability of reaching
targetfrom the initial state. - ExtensiveGame.BehaviorProfile.actionProb_nonnegA behavior profile assigns nonnegative probability to every action.
- ExtensiveGame.BehaviorProfileA behavior-strategy profile: one behavior strategy for every player.
- 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.StrategyProfileA strategy profile: a strategy for each player.
- ExtensiveGame.finalPayoffPayoff at the final state for player
i. - ExtensiveGame.BehaviorProfile.IsCompletelyMixedWithPositiveReach.reach_posThe positive-reach component of
IsCompletelyMixedWithPositiveReach. - 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.
- 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
- 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
- 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.isReachable_initThe initial state is always reachable.
- 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…
- ExtensiveGame.ofControlledGame_payoffExtensiveGame.ofControlledGame_payoff
- 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
- 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 state-payoff extensive game: a payoff-free controlled game together with a convenient endpoint-state payoff. * `mover s` = who controls state `s` (`none` = non-player-controlled) * `payoff s i` = payoff for player `i` at state `s` (meaningful at terminal states) General terminal-history, complete-path, and winning-condition semantics are separate objective layers; this field is not their authoritative definition. No `isTerminal` field — terminal states are detected by `IsEmpty (Action s)`. No proof terms to carry around. -/ structure ExtensiveGame (N : Type*) (U : Type*) extends ControlledGame N where /-- Payoff at each state for each player. Meaningful at terminal states; may be arbitrary elsewhere. -/ payoff : State → N → U