GameTree.children
defimported Lean
The full child list at a Node, as a guaranteed non-empty list.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in variable {N U : Type*} in @[simp] def GameTree.children : GameTree N U → List (GameTree N U)
- Defined in
- EconCSLib, `GameTree.children`
- Lean proof
- By xbei (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.GameTree.children← GameTree.children (EconCSLib/GameTheory/ExtensiveGame/GameTree.lean:64): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 1
- GameTreeA finite extensive-form game of perfect information, without chance. *
Leaf payoff— a terminal state with a payoff vectorN → U. *…
- GameTreeA finite extensive-form game of perfect information, without chance. *
- Used by 29
- GameTree.size_mem_tail_ltAny tail child is structurally smaller.
- GameTree.Kuhn_exists_SPE_onKuhn's theorem, root-scoped SPE form: every finite perfect-information game without chance has a pure strategy that is subgame-perfect…
- GameTree.IsSubgamePerfectOnRoot-scoped subgame perfection on the subtrees of a fixed root.
IsSubgamePerfect σis global over everyGameTree N U. This predicate… - GameTree.size_posSize is always positive.
- GameTree.outcome_LeafGameTree.outcome_Leaf
- GameTree.IVariant.refl
IVariantis reflexive: any strategy is ani-variant of itself. - GameTree.profileStrategyCombine a normal-form profile into the global
GameTree.Strategyused by the game-tree evaluator. At each node, the mover's contingent… - GameTree.Kuhn_exists_NEKuhn's theorem, NE form: every finite perfect-information game without chance has a pure-strategy Nash equilibrium.
- GameTree.size_mem_children_ltAny child (head or in tail) is structurally smaller than the node.
- GameTree.optStrategy_isSubgamePerfectOptimality of
optStrategy: for every subtreeg, every playeri, and everyi-variant deviationσ', the deviating outcome is… - GameTree.IsNashAtRoot-scoped Nash equilibrium predicate for a fixed
GameTreeroot. This is definitionally the existingIsNashEquilibrium, with the… - GameTree.IsNashAt.toSubgamePerfectOn_of_hasOnlyRootSubgamesIf a tree has no proper subgames, root Nash equilibrium already implies subgame perfection on that tree. This is the pure finite-tree form…
- GameTree.outcome_NodeGameTree.outcome_Node
- GameTree.toStrategicGameThe strategic-form extraction of a finite perfect-information tree.
- GameTree.IsSubgamePerfectA strategy is subgame-perfect (SPE) if, at every subtree, no player can strictly improve their payoff by a unilateral deviation —…
- GameTree.outcome_optStrategy_eq_valueKey lemma: the outcome of the backward-induction strategy equals the backward-induction value vector at every game tree. This is the…
- GameTree.IsSubgamePerfectOn.toNashAtRoot-scoped subgame perfection implies Nash equilibrium at the same root.
- GameTree.children_node_ne_nilChildren of a
Nodeare never empty. - GameTree.IVariantTwo strategies are
i-variants if they agree on all nodes NOT owned byi. I.e.,σ'is obtained fromσby changing only playeri's… - GameTree.IsSubgamePerfect.toSubgamePerfectOnA global subgame-perfect equilibrium is subgame-perfect on every fixed root.
- GameTree.strong_inductionStrong induction: to prove
motive g, it suffices to handleLeafand, for eachNode, to prove the motive given the motive for… - GameTree.IsNashEquilibriumNash equilibrium: no single player can improve their outcome at the root game by unilateral deviation. Weaker than
IsSubgamePerfect,… - GameTree.profileStrategy_deviate_variantReplacing player
i's normal-form contingent plan produces ani-variant global tree strategy. - GameTree.optStrategyThe canonical backward-induction strategy: at each node, pick a child whose backward-induction value equals the node's value (i.e., a…
- GameTree.outcomeThe outcome (terminal payoff vector) of playing strategy
σstarting from game treeg. Walks down the tree, usingσto pick a child… - GameTree.value_optStrategy_eqAt a node, the
optStrategypicks a child whose value equals the node's value. - GameTree.Kuhn_exists_SPEKuhn's theorem (existence form): every finite perfect-information game without chance admits a subgame-perfect equilibrium. The…
- GameTree.IsSubgamePerfect.toNESPE ⇒ NE: every subgame-perfect equilibrium is a Nash equilibrium (at any fixed root game).
- GameTree.isSubgamePerfectOn_iff_forall_subtree_isNashAtRoot-scoped subgame perfection is equivalent to Nash equilibrium at every subtree of the root. This is the pure finite-tree form of MSZ…
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in variable {N U : Type*} in /-- The full child list at a `Node`, as a guaranteed non-empty list. -/ @[simp] def GameTree.children : GameTree N U → List (GameTree N U) | Leaf _ => [] | Node _ h t => h :: t