AFTD Auto-Formalizing Theoretical Domains

weak_duality

theoremverifiedimported Lean

Weak duality for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with $M \ge 1$ row actions and $N \ge 1$ column actions, given by a payoff matrix $A$ whose entries satisfy $A_{ij} \in [0,1]$, where the row player maximises and the column player minimises. Let $p = (p_i)$ be a mixed strategy for the row player and $q = (q_j)$ a mixed strategy for the column player. Then the row player's guaranteed payoff under $p$ never exceeds the payoff the column player can be forced above under $q$: \[ \min_{j} \sum_{i} p_i\, A_{ij} \;\le\; \max_{i} \sum_{j} A_{ij}\, q_j . \]

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
theorem weak_duality {M N : ℕ} [NeZero M] [NeZero N] (G : ZeroSumGame M N)
    (p : MixedStrategy M) (q : MixedStrategy N) :
    (⨅ j : Fin N, payoffVsPure G p j) ≤ ⨆ i : Fin M, pureVsPayoff G i q
Source
TCSlib, `weak_duality`
Lean proof
By Karim Abdel Sadek, Mark Bedaywi, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Karim Abdel Sadek and Mark Bedaywi. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • pureVsPayoffGiven a game $G$, a pure row $i$, and a mixed column strategy $q$, the expected payoff of row $i$ against $q$ is…
  • MixedStrategyA mixed strategy over $n$ actions is a record consisting of a weight function $w : \mathrm{Fin}\,n \to \mathbb{R}$ together with…
  • ZeroSumGameA finite two-player zero-sum game with $M$ row actions and $N$ column actions is a record consisting of a payoff matrix…
  • payoffVsPureGiven a game $G$, a mixed row strategy $p$, and a pure column $j$, the expected payoff against column $j$ is…
Used by 1

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Real Finset BigOperators in/-- Weak duality: for any row mixed strategy `p` and column mixed strategy `q`, the infimum over pure columns `j` of the payoff of `p` against `j` is at most the supremum over pure rows `i` of the payoff of `i` against `q`. [CBL06, §7.2 (the trivial direction `max min ≤ min max`)]; [FS99, §2]. **Proof sketch.** Let `v := Σᵢ Σⱼ pᵢ A(i, j) qⱼ` be the bilinear expected payoff of `(p, q)`. Step 1: writing `v = Σⱼ payoff(p, j) · qⱼ` as a `q`-average over columns and bounding each term below by the column infimum (which is bounded below by `0`) gives `inf_j payoff(p, j) ≤ v`. Step 2: writing `v = Σᵢ payoff(i, q) · pᵢ` as a `p`-average over rows and bounding each term above by the row supremum (bounded above by `1`) gives `v ≤ sup_i payoff(i, q)`. Chain the two. -/theorem weak_duality {M N : ℕ} [NeZero M] [NeZero N] (G : ZeroSumGame M N)    (p : MixedStrategy M) (q : MixedStrategy N) :    (⨅ j : Fin N, payoffVsPure G p j) ≤ ⨆ i : Fin M, pureVsPayoff G i q := by  -- Put the bilinear expected payoff in the middle.  It is at least the worst  -- pure-column payoff against `p`, and at most the best pure-row payoff  -- against `q`.  set v := ∑ i : Fin M, ∑ j : Fin N, p.weights i * G.payoff i j * q.weights j  -- Step 1: the column infimum is at most `v` (average of `v` over columns).  have hv_lb : ⨅ j, payoffVsPure G p j ≤ v := by    -- Rewrite `v` as an average over columns and compare each term to the    -- column infimum.    have hv_eq : v = ∑ j : Fin N, payoffVsPure G p j * q.weights j := by      simp only [v, payoffVsPure]; rw [Finset.sum_comm]; simp_rw [Finset.sum_mul]    rw [hv_eq]    have hbdd : BddBelow (Set.range (payoffVsPure G p)) :=      ⟨0, by rintro _ ⟨j, rfl⟩; exact Finset.sum_nonneg fun i _ =>        mul_nonneg (p.nonneg i) (G.payoff_nonneg i j)⟩    calc ⨅ j, payoffVsPure G p j        = (⨅ j, payoffVsPure G p j) * ∑ j, q.weights j := by rw [q.sum_one, mul_one]      _ = ∑ j, (⨅ j, payoffVsPure G p j) * q.weights j := Finset.mul_sum ..      _ ≤ ∑ j, payoffVsPure G p j * q.weights j :=          Finset.sum_le_sum fun j _ =>            mul_le_mul_of_nonneg_right (ciInf_le hbdd j) (q.nonneg j)  -- Step 2: `v` is at most the row supremum (average of `v` over rows).  have hv_ub : v ≤ ⨆ i, pureVsPayoff G i q := by    -- Rewrite `v` as an average over rows and compare each term to the row    -- supremum.    have hv_eq : v = ∑ i : Fin M, pureVsPayoff G i q * p.weights i := by      simp only [v, pureVsPayoff]; simp_rw [Finset.sum_mul]      congr 1; ext i; congr 1; ext j; ring    rw [hv_eq]    have hbdd : BddAbove (Set.range (pureVsPayoff G · q)) :=      ⟨1, by rintro _ ⟨i, rfl⟩             calc ∑ j : Fin N, G.payoff i j * q.weights j                 ≤ ∑ j : Fin N, 1 * q.weights j :=                   Finset.sum_le_sum fun j _ =>                     mul_le_mul_of_nonneg_right (G.payoff_le_one i j) (q.nonneg j)               _ = 1 := by simp [q.sum_one]⟩    calc ∑ i, pureVsPayoff G i q * p.weights i        ≤ ∑ i, (⨆ i, pureVsPayoff G i q) * p.weights i :=          Finset.sum_le_sum fun i _ =>            mul_le_mul_of_nonneg_right (le_ciSup hbdd i) (p.nonneg i)      _ = (⨆ i, pureVsPayoff G i q) := by          rw [← Finset.mul_sum]; rw [p.sum_one, mul_one]  linarith
See it in the graphDiscuss this resultChallenge it