MatrixGame.AdmissibleSequence
An admissible sequence on a matrix game A (Robinson 1951 setup). Records cumulative counterfactual payoff vectors α(t) : J → ℝ (payoff to playing column j against the actual row sequence) and β(t) : I → ℝ (payoff to playing row i against the actual column sequence), together with the row/column choice sequences and the admissibility conditions: * init_bracket — min_j α^j(0) = max_i β^i(0) (the bracket-start condition, MFoGT (i)). * iSeq_best, jSeq_best — at each step the chosen row is in argmax β(t) and the chosen column is in argmin α(t). * α_step, β_step — the cumulative-payoff update by the chosen pure actions, MFoGT (ii). This is the cumulative-payoff encoding of a fictitious-play realisation; see MatrixGame.IsFictitiousPlay for the empirical-frequency formulation, and the blueprint node for the correspondence α(t)/t = x(t) A, β(t)/t = A y(t) (plus the negligible boundary).
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BigOperators in set_option linter.unusedSectionVars false in variable {I J : Type*} [Fintype I] [Fintype J] [Nonempty I] [Nonempty J] in structure MatrixGame.AdmissibleSequence (A : MatrixGame I J ℝ)
- Defined in
- EconCSLib, `MatrixGame.AdmissibleSequence`
- 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.AdmissibleSequence← MatrixGame.AdmissibleSequence (EconCSLib/GameTheory/StrategicGame/ZeroSum/Learning/Robinson.lean:61): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 5
- MatrixGame.instDecidableEqStrategyFinOfNatNatToStrategicGameMatrixGame.instDecidableEqStrategyFinOfNatNatToStrategicGame
- MatrixGameA finite two-player zero-sum matrix game. Player I chooses row
i : I, Player II chooses columnj : J. Payoff to Player I isg i j… - MatrixGame.instNonemptyStrategyFinOfNatNatToStrategicGameMatrixGame.instNonemptyStrategyFinOfNatNatToStrategicGame
- MatrixGame.instFintypeStrategyFinOfNatNatToStrategicGameMatrixGame.instFintypeStrategyFinOfNatNatToStrategicGame
- 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…
- Used by 3
- MatrixGame.AdmissibleSequence.muCumulative duality gap
μ(t) := max_i β^i(t) - min_j α^j(t). - 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.AdmissibleSequence.IsColUsefulInWindowA pure column
jis useful in the window[s, s + t*]analogously.
- MatrixGame.AdmissibleSequence.muCumulative duality gap
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BigOperators in set_option linter.unusedSectionVars false in variable {I J : Type*} [Fintype I] [Fintype J] [Nonempty I] [Nonempty J] in /-- An **admissible sequence** on a matrix game `A` (Robinson 1951 setup). Records cumulative counterfactual payoff vectors `α(t) : J → ℝ` (payoff to playing column `j` against the actual row sequence) and `β(t) : I → ℝ` (payoff to playing row `i` against the actual column sequence), together with the row/column choice sequences and the admissibility conditions: * `init_bracket` — `min_j α^j(0) = max_i β^i(0)` (the bracket-start condition, MFoGT (i)). * `iSeq_best`, `jSeq_best` — at each step the chosen row is in `argmax β(t)` and the chosen column is in `argmin α(t)`. * `α_step`, `β_step` — the cumulative-payoff update by the chosen pure actions, MFoGT (ii). This is the cumulative-payoff encoding of a fictitious-play realisation; see `MatrixGame.IsFictitiousPlay` for the empirical-frequency formulation, and the blueprint node for the correspondence `α(t)/t = x(t) A`, `β(t)/t = A y(t)` (plus the negligible boundary). -/ structure MatrixGame.AdmissibleSequence (A : MatrixGame I J ℝ) where α : ℕ → J → ℝ β : ℕ → I → ℝ iSeq : ℕ → I jSeq : ℕ → J init_bracket : Finset.univ.inf' Finset.univ_nonempty (α 0) = Finset.univ.sup' Finset.univ_nonempty (β 0) iSeq_best : ∀ t i', β t i' ≤ β t (iSeq t) jSeq_best : ∀ t j', α t (jSeq t) ≤ α t j' α_step : ∀ t j, α (t + 1) j = α t j + A.g (iSeq t) j β_step : ∀ t i, β (t + 1) i = β t i + A.g i (jSeq t)