Proof of Theorem 1 — nonnegative minimax criterion
ProvedHartSchmeidler.Finite.minimax_nonneg_criterionfinite-gamesminimaxp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1zero-sum-games
Let and be finite, nonempty pure-strategy sets and a payoff matrix. Suppose that against every lottery on , the maximizing player has some lottery on whose expected payoff is nonnegative:
Then one lottery guarantees nonnegative expected payoff against every lottery on . This is the criterion for the auxiliary game that Hart and Schmeidler draw from the finite minimax theorem.
Formalization Note Both pure-strategy sets are nonempty so that their lottery sets exist. The paper's auxiliary game has this property when there is at least one player; the playerless boundary of the goal requires its own immediate case.
Preamble
import Definitions.Def_agt_games import Mathlib
Formal statement
namespace HartSchmeidler.Finite
open Finset
/-- Proof of Theorem 1, p. 19: the finite minimax theorem turns a response
to each column lottery into one row lottery guaranteeing nonnegative payoff. -/
theorem minimax_nonneg_criterion {X Y : Type*} [Fintype X] [Fintype Y]
[Nonempty X] [Nonempty Y] (A : X → Y → ℝ)
(hA : ∀ y : Y → ℝ, AGT.IsLottery y →
∃ x : X → ℝ, AGT.IsLottery x ∧
0 ≤ ∑ a, ∑ b, x a * y b * A a b) :
∃ x : X → ℝ, AGT.IsLottery x ∧
∀ y : Y → ℝ, AGT.IsLottery y →
0 ≤ ∑ a, ∑ b, x a * y b * A a b := by sorry
end HartSchmeidler.Finite
Source
Hart and Schmeidler, Existence of Correlated Equilibria, Math. Oper. Res. 14 (1989), p. 19, proof of Theorem 1 (‘By the Minimax Theorem’); https://doi.org/10.1287/moor.14.1.18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.