AFTD Auto-Formalizing Theoretical Domains

ZeroSumChance.GameTree.value_prop

theoremverifiedformalizationimported Lean

Soundness of DStrategy: the backward-induction value is a lower bound on the outcome A achieves by following DStrategy, regardless of how B plays. Formally: for every B-strategy SB and game tree t, t.value ≤ t.outcome DStrategy SB.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
theorem ZeroSumChance.GameTree.value_prop (SB : Strategy) {t : GameTree} : t.value ≤ t.outcome DStrategy SB
Formalizes
EconCSLib, `ZeroSumChance.GameTree.value_prop`
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 8

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true in/-- **Soundness of `DStrategy`**: the backward-induction value is a lower bound on the outcome A achieves by following `DStrategy`, regardless of how B plays. Formally: for every B-strategy `SB` and game tree `t`, `t.value ≤ t.outcome DStrategy SB`. -/theorem ZeroSumChance.GameTree.value_prop (SB : Strategy) {t : GameTree} : t.value ≤ t.outcome DStrategy SB := by  induction t with  | Leaf r =>    simp [outcome, value]  | Pnode p L R HL HR =>    match p with    | Player.A =>      rw [value, outcome, DStrategy]      split_ifs with h      · -- DStrategy picked R (L.value < R.value); goal: max L.value R.value ≤ outcome … R        exact (max_le (le_of_lt h |>.trans HR) HR)      · -- DStrategy picked L (¬ L.value < R.value, i.e. R.value ≤ L.value)        -- goal: max L.value R.value ≤ outcome … L        exact (max_le HL (not_lt.mp h |>.trans HL))    | Player.B =>      rw [value, outcome]      cases SB L R      · -- B chose L        exact min_le_left L.value R.value |>.trans HL      · -- B chose R        exact min_le_right L.value R.value |>.trans HR  | Nnode prob L R HL HR =>    rw [outcome, value]    have hpL : (prob : ℚ) * L.value ≤ prob * outcome DStrategy SB L :=      mul_le_mul_of_nonneg_left HL prob.2.1    have hpR : (1 - prob) * R.value ≤ (1 - prob) * outcome DStrategy SB R :=      mul_le_mul_of_nonneg_left HR (by linarith [prob.2.2])    linarith
See it in the graphDiscuss this resultChallenge it