MatrixGame
structureimported Lean
A 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 (in the scalar field 𝕜); payoff to Player II is -g i j. The scalar field 𝕜 defaults to ℚ so that unannotated MatrixGame I J means a rational matrix game — keeping the data structure Bourbaki-minimal and forcing the choice of ℝ (or any other ordered field) to be explicit at the use site.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BigOperators Matrix in structure MatrixGame (I J : Type*) (𝕜 : Type := ℚ)
- Defined in
- EconCSLib, `MatrixGame`
- 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.MatrixGame← MatrixGame (EconCSLib/GameTheory/StrategicGame/ZeroSum/MatrixGame.lean:58): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Used by 79
- MatrixGame.optimal_pairs_iff_saddle_pointOptimal pairs ↔ saddle points. A pair of mixed strategies is in the product
X(A) × Y(A)of optimal strategy sets iff it is a saddle… - MatrixGame.E_eq_wsum_wsumHelper: writing
A.Eas an iteratedwsumexposes the structure that the saddle-point bounds rely on. - MatrixGame.IsMinimax
vis a minimax value ofA: some column strategy caps player I's payoff atv(existence), and no strictly smaller cap is… - MatrixGame.expectedPayoff_toStrategicGame_zeroBridge lemma:
expectedPayoff A.toStrategicGame p 0 = A.E (p 0) (p 1). Reduces both sides to the canonical double sum… - EconCSLib.StrategicGame.MatrixGame.disp_EjColumn-side payoff under
disp A:Ej x j = (xA)_j − x_j. - MatrixGame.optimalColumnStrategies_image_isPolytopeMatrixGame.optimalColumnStrategies_image_isPolytope
- MatrixGame.dualityGapPoint-wise duality gap at a strategy pair: the column player's realised loss-cap minus the row player's realised guarantee. Always…
- MatrixGame.AdmissibleSequence.muCumulative duality gap
μ(t) := max_i β^i(t) - min_j α^j(t). - MatrixGame.exists_strategic_game_nash_equilibriumThe strategic-game embedding of a finite matrix game admits a mixed Nash equilibrium. Combines…
- MatrixGame.IsPlayerIIGuarantee
wis a guarantee for player II when some mixed column strategy caps expected payoff≤ wagainst every pure row. Equivalent to… - MatrixGame.optimalColumnSet_isCompactMatrixGame.optimalColumnSet_isCompact
- MatrixGame.optimalRowStrategiesThe set of optimal row strategies: mixed strategies that achieve the maximin value.
- MatrixGame.EiExpected payoff when pure row
ifaces Player II's mixed strategyy. - MatrixGame.valueThe value of a matrix game (
sSup-based; needs order completeness). Equal to both maximin and minimax by the minimax theorem… - MatrixGame.image_optimalColumnStrategies_eqMatrixGame.image_optimalColumnStrategies_eq
- MatrixGame.AdmissibleSequence.IsRowUsefulInWindowA pure row
iis useful in the window[s, s + t*]if there is a step inside the window at whichiis among the row player's… - MatrixGame.isMixedNashEq_iff_isSaddlePointNash equilibrium ↔ saddle point for matrix games. Both sides unfold to the same saddle-point inequality system; the equivalence is…
- MatrixGame.optimalRowSet_isClosedMatrixGame.optimalRowSet_isClosed
- MatrixGame.optimalColumnStrategiesThe set of optimal column strategies: mixed strategies that achieve the minimax value.
- MatrixGame.toStrategicGame_isZeroSum
A.toStrategicGamesatisfies the abstract zero-sum predicate: by construction player 1's payoff is the negation of player 0's. - MatrixGame.guarantee_IIPlayer II's guaranteed loss using mixed strategy
y: the maximum expected payoff (for Player I) over all of Player I's pure responses. - MatrixGame.toStrategicGameThe two-player zero-sum strategic game associated with a matrix game. See
MatrixGame.toStrategicGame_isZeroSumfor the proof that this… - MatrixGame.instDecidableEqStrategyFinOfNatNatToStrategicGameMatrixGame.instDecidableEqStrategyFinOfNatNatToStrategicGame
- MatrixGame.AdmissibleSequenceAn admissible sequence on a matrix game
A(Robinson 1951 setup). Records cumulative counterfactual payoff vectorsα(t) : J → ℝ… - MatrixGame.value_eq_minimaxMatrixGame.value_eq_minimax
- MatrixGame.expectedPayoffExpected payoff when Player I uses mixed strategy
xand Player II usesy. - MatrixGame.maximin_le_minimaxMaximin ≤ minimax (always holds, for any matrix game). This is the finite weak-duality inequality.
- EconCSLib.StrategicGame.MatrixGame.disp_Ei_uniformUnder the uniform distribution, the column-side payoff under
disp Ais zero (whenAis stochastic). - MatrixGame.support_complementarity_columnSupport complementarity (column). For an optimal pair
(xx, yy), every columnjwith positive probability underyyis a best… - MatrixGame.EExpected payoff when Player I uses mixed strategy
xand Player II usesy. - MatrixGame.toMixedProfile_zeroMatrixGame.toMixedProfile_zero
- MatrixGame.optimalColumnSet_isClosedMatrixGame.optimalColumnSet_isClosed
- MatrixGame.IsPlayerIGuarantee
wis a guarantee for player I when some mixed row strategy achieves expected payoff≥ wagainst every pure column. Equivalent to… - MatrixGame.isMixedNashEq_of_purePure-strategy guarantees give a mixed Nash equilibrium. If
xxguarantees valuevagainst every pure column andyycaps the row… - MatrixGame.IsEpsilonOptimalColumnAn ε-optimal column strategy caps player I's payoff at
value + ε. - MatrixGame.optimalRowStrategies_image_isPolytopeThe row-optimal strategy set is a nonempty polytope: convex, closed, compact, and nonempty.
- MatrixGame.supportSupport of a mixed strategy: the indices with positive probability.
- MatrixGame.value_eq_maximinMatrixGame.value_eq_maximin
- MatrixGame.guarantee_IPlayer I's guaranteed payoff using mixed strategy
x: the minimum expected payoff over all of Player II's pure responses. A finite… - MatrixGame.exists_mixed_nash_equilibriumMatrix games have a mixed Nash equilibrium — over any linearly ordered field. Packages the field-generic saddle
Minimax.minimax… - MatrixGame.optimalColumnSetH-representation of the column-optimal strategy set in the ambient space
J → ℝ. - MatrixGame.IsValue
vis the value ofA(saddle-point form): there exist a row mixed strategyxand column mixed strategyysuch thatx… - MatrixGame.common_guarantee_eq_valueCommon guarantee gives the value. If both players guarantee the same scalar
w, thenwequals the game value. - MatrixGame.IsFictitiousPlayFictitious play realisation on a matrix game
A. At every stepn + 1, the row player picks a pure row best-responding to the column… - MatrixGame.payoffAgainstColumnExpected payoff when Player I uses mixed strategy
xagainst pure columnj. - MatrixGame.optimalRowSet_nonemptyMatrixGame.optimalRowSet_nonempty
- MatrixGame.IsSaddlePointA pair of mixed strategies is a saddle point when player I's payoff is maximised by the row strategy against the column strategy and…
- MatrixGame.maximinThe maximin value: the best guarantee Player I can achieve.
maximin = sup_x inf_j E(x, j) - MatrixGame.mem_optimalColumnStrategies_iff_E_leA column strategy is optimal iff against every mixed row it caps payoff at the value.
- EconCSLib.StrategicGame.MatrixGame.disp_Ei_argmin_nonnegFor any column-player strategy
y, picking the index whereyis minimal gives a non-negative row payoff underdisp A. - MatrixGame.expectedPayoff_toStrategicGame_oneMirror:
expectedPayoff A.toStrategicGame p 1 = -(A.E (p 0) (p 1)). - MatrixGame.AdmissibleSequence.IsColUsefulInWindowA pure column
jis useful in the window[s, s + t*]analogously. - MatrixGame.minimax_optimal_strategiesExistence of optimal mixed strategies: there exist mixed strategies
xxfor Player I andyyfor Player II and a valuevsuch that: -… - MatrixGame.realisedCumPayoffRealised cumulative payoff along a play sequence on
A. - MatrixGame.optimalRowSet_convexMatrixGame.optimalRowSet_convex
- 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.image_optimalRowStrategies_eqThe image of the row-optimal subtype set equals the H-representation polytope
A.optimalRowSet. - saddle_gap_gameGiven an n-by-n payoff matrix A, the saddle-gap game S has row player choosing a pair (i, j) in [n]² and column player choosing k in [n],…
- MatrixGame.EjExpected payoff when Player I uses
xagainst pure columnj. - EconCSLib.StrategicGame.MatrixGame.disp_EiRow-side payoff under
disp A:Ei i y = (Ay)_i − y_i. - MatrixGame.instNonemptyStrategyFinOfNatNatToStrategicGameMatrixGame.instNonemptyStrategyFinOfNatNatToStrategicGame
- MatrixGame.minimax_theoremVon Neumann's Minimax Theorem: For any finite matrix game, maximin = minimax. [MSZ 5.11, von Neumann 1928] Proof: the general…
- MatrixGame.IsMaximin
vis a maximin value ofA: some row strategy guarantees at leastv(existence), and no strictly larger value is achievable… - MatrixGame.toMixedProfileBuild a
MixedProfileoftoStrategicGamefrom a saddle-point pair. - MatrixGame.IsEpsilonOptimalRowAn ε-optimal row strategy guarantees at least
value - ε. - MatrixGame.optimalRowSetH-representation of the row-optimal strategy set in the ambient space
I → ℝ: the standard simplex intersected with the finitely many… - MatrixGame.optimalRowSet_isCompactMatrixGame.optimalRowSet_isCompact
- MatrixGame.E_eq_wsum_wsum_swapHelper: swap order of the iterated
wsuminA.E. - MatrixGame.mem_optimalRowStrategies_iff_E_geA row strategy is optimal iff against every mixed column it secures the value.
- MatrixGame.support_complementarity_rowSupport complementarity (row). For an optimal pair
(xx, yy), every rowiwith positive probability underxxis a best response… - MatrixGame.payoffAgainstRowExpected payoff when pure row
ifaces Player II's mixed strategyy. - MatrixGame.normMax
‖A‖ := max_{i,j} |A_{i,j}|, the entrywise sup norm of the payoff matrix. Field-generic in the abstract, but the Robinson analysis is… - MatrixGame.toMixedProfile_oneMatrixGame.toMixedProfile_one
- MatrixGame.minimaxThe minimax value: the best guarantee Player II can achieve.
minimax = inf_y sup_i E(i, y) - MatrixGame.optimalColumnSet_convexMatrixGame.optimalColumnSet_convex
- saddle_gap_marginal_payoff_boundsLet n be a positive natural number. For any matrix A : Matrix (Fin n) (Fin n) ℝ with non-negative entries and any optimal row strategy σ…
- MatrixGame.optimalColumnSet_nonemptyMatrixGame.optimalColumnSet_nonempty
- MatrixGame.instFintypeStrategyFinOfNatNatToStrategicGameMatrixGame.instFintypeStrategyFinOfNatNatToStrategicGame
- saddle_gap_guarantee_II_eq_sup_sub_infFor a positive natural number n with
[NeZero n], an n-by-n real matrix A : Matrix (Fin n) (Fin n) ℝ, and a strategy vector x :…
- MatrixGame.optimal_pairs_iff_saddle_pointOptimal pairs ↔ saddle points. A pair of mixed strategies is in the product
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BigOperators Matrix in /-- A 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` (in the scalar field `𝕜`); payoff to Player II is `-g i j`. The scalar field `𝕜` defaults to `ℚ` so that unannotated `MatrixGame I J` means a rational matrix game — keeping the data structure Bourbaki-minimal and forcing the choice of `ℝ` (or any other ordered field) to be explicit at the use site. -/ structure MatrixGame (I J : Type*) (𝕜 : Type := ℚ) where /-- The payoff matrix. -/ g : I → J → 𝕜