AFTD Auto-Formalizing Theoretical Domains

GameTree.optStrategy_isSubgamePerfect

theoremverifiedformalizationimported Lean

Optimality of optStrategy: for every subtree g, every player i, and every i-variant deviation σ', the deviating outcome is no better than optStrategy's outcome at coordinate i. This is the SPE property spelled out before bundling into existence form.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open GameTree in
variable {N U : Type*} [TotalPreorder U] in
theorem GameTree.optStrategy_isSubgamePerfect [DecidableLE U] :
    IsSubgamePerfect (optStrategy : Strategy N U)
Formalizes
EconCSLib, `GameTree.optStrategy_isSubgamePerfect`
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.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 19
  • GameTree.outcome_LeafGameTree.outcome_Leaf
  • GameTree.outcome_NodeGameTree.outcome_Node
  • 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.IVariantTwo strategies are i-variants if they agree on all nodes NOT owned by i. I.e., σ' is obtained from σ by changing only player i's…
  • GameTree.strong_inductionStrong induction: to prove motive g, it suffices to handle Leaf and, for each Node, to prove the motive given the motive for…
  • 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 tree g. Walks down the tree, using σ to pick a child…
  • GameTree.value_optStrategy_eqAt a node, the optStrategy picks a child whose value equals the node's value.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • GameTreeA finite extensive-form game of perfect information, without chance. * Leaf payoff — a terminal state with a payoff vector N → U. *…
  • GameTree.StrategyA pure strategy for the entire game tree: at every possible node context (mover, head, tail), specify one child (bundled with its…
  • GameTree.valueGameTree.value
  • GameTree.value_Node_geKey optimality lemma: at a Node m h t, the mover m's coordinate of the backward-induction value dominates every child's.
  • GameTree.childrenThe full child list at a Node, as a guaranteed non-empty list.
  • GameTree.value_LeafGameTree.value_Leaf
  • GameTree.value_NodeGameTree.value_Node
  • GameTree.valueList_nilGameTree.valueList_nil
  • GameTree.valueList_consGameTree.valueList_cons
Used by 3

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen GameTree invariable {N U : Type*} [TotalPreorder U] in/-- **Optimality of `optStrategy`**: for every subtree `g`, every player `i`, and every `i`-variant deviation `σ'`, the deviating outcome is no better than `optStrategy`'s outcome at coordinate `i`. This is the SPE property spelled out before bundling into existence form. -/theorem GameTree.optStrategy_isSubgamePerfect [DecidableLE U] :    IsSubgamePerfect (optStrategy : Strategy N U) := by  intro g i σ' hiv  induction g using GameTree.strong_induction with  | base p =>      -- Both outcomes equal `p`; `≤` holds by reflexivity.      simp [outcome_Leaf]  | step m h t ih =>      -- Two subcases depending on whether the mover is the deviating player.      rw [outcome_Node, outcome_Node]      by_cases hmi : m = i      · -- Mover = deviating player. σ' can pick any child c'; optStrategy picks argmax.        -- Use IH on c' to compare σ' vs optStrategy there, then value_Node_ge.        have hmem' : (σ' m h t).val ∈ h :: t := (σ' m h t).property        -- IH on c' gives: outcome σ' c' i ≤ outcome optStrategy c' i        have h_ih := ih _ hmem'        -- Bridge: outcome optStrategy c' = value c'        rw [outcome_optStrategy_eq_value] at h_ih        -- value c' i ≤ value (Node m h t) i by value_Node_ge        have h_max : (value (σ' m h t).val) i ≤ (value (Node m h t)) i := by          subst hmi          exact value_Node_ge m h t _ hmem'        -- Right side: outcome optStrategy (optStrategy m h t).val i = value (Node m h t) i        have h_rhs : outcome optStrategy (optStrategy m h t).val i =                       (value (Node m h t)) i := by          rw [outcome_optStrategy_eq_value]          exact congrArg (· i) (value_optStrategy_eq m h t)        calc outcome σ' (σ' m h t).val i            ≤ (value (σ' m h t).val) i := h_ih          _ ≤ (value (Node m h t)) i := h_max          _ = outcome optStrategy (optStrategy m h t).val i := h_rhs.symm      · -- Mover ≠ deviating player: σ' and optStrategy pick the same child.        have hsame : σ' m h t = optStrategy m h t := (hiv m h t hmi).symm        rw [hsame]        -- Apply IH on the shared child        have hmem : (optStrategy m h t).val ∈ h :: t := (optStrategy m h t).property        exact ih _ hmem
See it in the graphDiscuss this resultChallenge it