AFTD Auto-Formalizing Theoretical Domains

MatrixGame.isMixedNashEq_of_pure

theoremverifiedformalizationimported Lean

Pure-strategy guarantees give a mixed Nash equilibrium. If xx guarantees value v against every pure column and yy caps the row player's payoff at v against every pure row, then (xx, yy) is a saddle-point mixed Nash equilibrium. Field-generic — only the saddle inequalities are used (no order-completeness).

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Finset BigOperators in
set_option linter.unusedSectionVars false in
universe u in
variable {I J : Type u} [Fintype I] [Fintype J] [Nonempty I] [Nonempty J] in
variable (A : MatrixGame I J ℝ) in
theorem MatrixGame.isMixedNashEq_of_pure {𝕜 : Type} [Field 𝕜] [LinearOrder 𝕜]
    [IsStrictOrderedRing 𝕜] (A : MatrixGame I J 𝕜)
    {xx : stdSimplex 𝕜 I} {yy : stdSimplex 𝕜 J} {v : 𝕜}
    (Hxx : ∀ j, v ≤ wsum xx (fun i => A.g i j))
    (Hyy : ∀ i, wsum yy (A.g i) ≤ v) :
    A.IsMixedNashEq xx yy
Formalizes
EconCSLib, `MatrixGame.isMixedNashEq_of_pure`
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 9
  • MatrixGame.E_eq_wsum_wsumHelper: writing A.E as an iterated wsum exposes the structure that the saddle-point bounds rely on.
  • wsumWeighted sum of f with weights from a simplex element x. Thin abbrev over Mathlib's finite dot product ⬝ᵥ: definitionally equal,…
  • wsum_le_wsumWeighted sum is monotone: pointwise ≤ implies wsum ≤.
  • MatrixGame.EExpected payoff when Player I uses mixed strategy x and Player II uses y.
  • MatrixGameA finite two-player zero-sum matrix game. Player I chooses row i : I, Player II chooses column j : J. Payoff to Player I is g i j…
  • wsum_pure_applyWeighted sum at a point mass evaluates the chosen coordinate.
  • MatrixGame.IsMixedNashEqSaddle-point form of a mixed Nash equilibrium for a matrix game. For zero-sum two-player games, the standard mixed-strategy Nash…
  • MatrixGame.E_eq_wsum_wsum_swapHelper: swap order of the iterated wsum in A.E.
  • wsum_constWeighted sum of a constant equals the constant.
Used by 1

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Finset BigOperators inset_option linter.unusedSectionVars false inuniverse u invariable {I J : Type u} [Fintype I] [Fintype J] [Nonempty I] [Nonempty J] invariable (A : MatrixGame I J ℝ) in/-- **Pure-strategy guarantees give a mixed Nash equilibrium.** If `xx` guarantees value `v` against every pure column and `yy` caps the row player's payoff at `v` against every pure row, then `(xx, yy)` is a saddle-point mixed Nash equilibrium. Field-generic — only the saddle inequalities are used (no order-completeness). -/theorem MatrixGame.isMixedNashEq_of_pure {𝕜 : Type} [Field 𝕜] [LinearOrder 𝕜]    [IsStrictOrderedRing 𝕜] (A : MatrixGame I J 𝕜)    {xx : stdSimplex 𝕜 I} {yy : stdSimplex 𝕜 J} {v : 𝕜}    (Hxx : ∀ j, v ≤ wsum xx (fun i => A.g i j))    (Hyy : ∀ i, wsum yy (A.g i) ≤ v) :    A.IsMixedNashEq xx yy := by  refine ⟨?_, ?_⟩  · -- Row player cannot improve: `A.E x' yy ≤ v ≤ A.E xx yy`.    intro x'    have hE_x'_le : A.E x' yy ≤ v := by      rw [E_eq_wsum_wsum]      calc wsum x' (fun i => wsum yy (A.g i))          ≤ wsum x' (fun _ => v) := wsum_le_wsum x' Hyy        _ = v := wsum_const x' v    have hE_xx_ge : v ≤ A.E xx yy := by      rw [E_eq_wsum_wsum_swap]      calc v = wsum yy (fun _ => v) := (wsum_const yy v).symm        _ ≤ wsum yy (fun j => wsum xx (fun i => A.g i j)) := wsum_le_wsum yy Hxx    linarith  · -- Column player cannot improve: `A.E xx yy ≤ v ≤ A.E xx y'`.    intro y'    have hE_xx_le : A.E xx yy ≤ v := by      rw [E_eq_wsum_wsum]      calc wsum xx (fun i => wsum yy (A.g i))          ≤ wsum xx (fun _ => v) := wsum_le_wsum xx Hyy        _ = v := wsum_const xx v    have hE_xx_y'_ge : v ≤ A.E xx y' := by      rw [E_eq_wsum_wsum_swap]      calc v = wsum y' (fun _ => v) := (wsum_const y' v).symm        _ ≤ wsum y' (fun j => wsum xx (fun i => A.g i j)) := wsum_le_wsum y' Hxx    linarith
See it in the graphDiscuss this resultChallenge it