AFTD Auto-Formalizing Theoretical Domains

OnlineLearning.pureVsPayoff_le_one

theoremverifiedimported Lean

Pure row payoff against a mixed column is at most one. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column actions, whose payoff matrix $A$ satisfies $0 \le A_{ij} \le 1$ for all entries, and let $q$ be a mixed column strategy, that is, a probability distribution $q_1, \dots, q_N$ over the columns. Then for every pure row action $i$, the expected payoff of row $i$ against $q$ satisfies \[ \sum_{j} A_{ij}\, q_j \;\le\; 1. \]

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
lemma OnlineLearning.pureVsPayoff_le_one {M N : ℕ} (G : ZeroSumGame M N)
    (i : Fin M) (q : MixedStrategy N) :
    pureVsPayoff G i q ≤ 1
Source
TCSlib, `OnlineLearning.pureVsPayoff_le_one`
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 3
  • 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…
Used by 2

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Real Finset BigOperators in/-- Expected payoff of a pure row against a mixed column is at most one. -/lemma OnlineLearning.pureVsPayoff_le_one {M N : ℕ} (G : ZeroSumGame M N)    (i : Fin M) (q : MixedStrategy N) :    pureVsPayoff G i q ≤ 1 := by  calc pureVsPayoff G i q      ≤ ∑ 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]
See it in the graphDiscuss this resultChallenge it