(1) — min_j Σ_i a_ij x_i ≤ max_i Σ_j a_ij y_j for all mixed strategies
ProvedRobinsonFP.Convergence.ineq1fictitious-playgame-theorymatrix-gamep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real pay-off matrix with . For every probability vector of the first player (, ) and every probability vector of the second player (, ),
The left side is the payoff the first player guarantees with , the right side the loss the second player concedes at most with . This weak duality inequality is used in Lemma 1, in Lemma 3 (for the transpose of ), and at the end of the proof of the Theorem.
Formalization Note Probability vectors are elements of Mathlib's stdSimplex. Rows and columns are indexed by finite nonempty types.
Preamble
import Mathlib import Definitions.Def_RobinsonFP_Convergence_VectorSystem
Formal statement
namespace RobinsonFP.Convergence
variable {ι κ : Type*} [Fintype ι] [Fintype κ]
/-- Robinson (1951), p. 296, inequality (1): for all probability vectors `x` (over rows) and `y`
(over columns), `min_j Σ_i a_ij x_i ≤ max_i Σ_j a_ij y_j`. -/
theorem ineq1 [Nonempty ι] [Nonempty κ] (A : Matrix ι κ ℝ) :
∀ x ∈ stdSimplex ℝ ι, ∀ y ∈ stdSimplex ℝ κ,
vmin (fun j => ∑ i, A i j * x i) ≤ vmax (fun i => ∑ j, A i j * y j) := by sorry
end RobinsonFP.Convergence
Source
Robinson, An Iterative Method of Solving a Game, Ann. of Math. 54(2) (1951), p. 296, inequality (1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.