AFTD Auto-Formalizing Theoretical Domains

bestColumn_spec

theoremverifiedimported Lean

Optimality of the column best response. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N \ge 1$ column actions, given by a payoff matrix $A_{ij} \in [0,1]$, and let $p$ be a mixed strategy for the row player, with weights $p_i$. Write $v(j) = \sum_i p_i A_{ij}$ for the expected payoff of $p$ against the pure column $j$, and let $j^*$ be a column that minimises $v$ over all $N$ columns. Then $v(j^*) \le v(j)$ for every column $j$; that is, $j^*$ is indeed a minimiser of the expected payoff against $p$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
lemma bestColumn_spec {M N : ℕ} [NeZero N] (G : ZeroSumGame M N)
    (p : MixedStrategy M) (j : Fin N) :
    payoffVsPure G p (bestColumn G p) ≤ payoffVsPure G p j
Source
TCSlib, `bestColumn_spec`
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
  • MixedStrategyA mixed strategy over $n$ actions is a record consisting of a weight function $w : \mathrm{Fin}\,n \to \mathbb{R}$ together with…
  • bestColumnGiven a game $G$ and a mixed row strategy $p$, bestColumn is the pure column $j^* \in \mathrm{Fin}\,N$ that minimises…
  • 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
  • hedgeResponseNat_isBestResponseOnline column response is a best response. Let $G$ be a finite zero-sum game with $M \ge 1$ row actions and $N \ge 1$ column actions, let…

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Real Finset BigOperators in/-- The best-response column `bestColumn G p` does no worse for the column player than any other column: its payoff against `p` is at most the payoff of any column `j`. [FS99, §2 (best response)]. -/lemma bestColumn_spec {M N : ℕ} [NeZero N] (G : ZeroSumGame M N)    (p : MixedStrategy M) (j : Fin N) :    payoffVsPure G p (bestColumn G p) ≤ payoffVsPure G p j := by  exact (Classical.choose_spec (Finite.exists_min (payoffVsPure G p))) j
See it in the graphDiscuss this resultChallenge it