MixedStrategy
structureimported Lean
A mixed strategy over $n$ actions is a record consisting of a weight function $w : \mathrm{Fin}\,n \to \mathbb{R}$ together with proofs that every weight is non-negative and that the weights sum to $1$, i.e.\ $w$ is a probability distribution over $\mathrm{Fin}\,n$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in structure MixedStrategy (n : ℕ)
- Defined in
- TCSlib, `MixedStrategy`
- Lean proof
- By Karim Abdel Sadek, Mark Bedaywi, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Karim Abdel Sadek and Mark Bedaywi. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.MixedStrategy← MixedStrategy (TCSlib/LearningTheory/Minimax/ZeroSumGame.lean:57): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 33
- OnlineLearning.pureVsPayoff_nonnegNonnegativity of a pure row's expected payoff. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column actions,…
- empiricalJointGiven $T > 0$ rounds of play in which the row player uses mixed strategy $p_t$ and the column player uses $q_t$, the empirical joint…
- pureVsPayoffGiven a game $G$, a pure row $i$, and a mixed column strategy $q$, the expected payoff of row $i$ against $q$ is…
- empiricalJoint_isApproxCCENo-regret play yields an approximate coarse correlated equilibrium. Let $G$ be a finite two-player game with row utility $u_r$ and column…
- minimax_approx_theoremApproximate minimax theorem for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with payoff matrix $A$, having at…
- weak_dualityWeak duality for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with $M \ge 1$ row actions and $N \ge 1$ column…
- OnlineLearning.finiteLowerValueFor a finite zero-sum game $G$ with $M$ row actions and $N$ column actions, the lower value is…
- OnlineLearning.finiteLowerValue_bddAboveRow player's guaranteed payoffs are bounded above. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N \ge 1$ column…
- bestColumnGiven a game $G$ and a mixed row strategy $p$,
bestColumnis the pure column $j^* \in \mathrm{Fin}\,N$ that minimises… - empiricalJoint_colMarginalColumn marginal of the empirical joint distribution. Consider $T > 0$ rounds of play between a row player with $M$ actions and a column…
- OnlineLearning.finiteUpperValueThe upper value of $G$ is \[ v^+(G) \;=\; \inf_{q \in \Delta_N}\; \sup_{i \in [M]}\; \mathrm{pureVsPayoff}(G,i,q), \] where the…
- prefixHedgeMixedStrategy_weight_eq_hedgeDistPrefix Hedge strategy agrees with the abstract Hedge distribution. Let $G$ be a finite two-player zero-sum game with $M \ge 1$ row actions…
- bestColumn_specOptimality of the column best response. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N \ge 1$ column actions,…
- OnlineLearning.mixedStrategyNonemptyThe mixed-strategy space is nonempty whenever the underlying action set is nonempty.
- empiricalJoint_row_deviation_leRow regret bound gives row deviation bound. Let $G$ be a finite two-player game with row utility $u_r$ over $M$ row actions and $N$ column…
- OnlineLearning.payoffVsPure_nonnegNonnegativity of the mixed payoff against a pure column. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column…
- empiricalJoint_sum_prob_mulAveraging a payoff against the empirical joint distribution. Fix $T > 0$ rounds of play in which, in round $t$, the row player uses a…
- OnlineLearning.pureVsPayoff_le_onePure row payoff against a mixed column is at most one. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column…
- OnlineLearning.arbitraryMixedStrategyA concrete mixed strategy used only to prove that the type of mixed strategies is nonempty. It puts all mass on one arbitrary action.
- OnlineLearning.finiteUpperValue_bddBelowLower boundedness of the row-supremum values. Let $G$ be a finite two-player zero-sum game with $M \ge 1$ row actions and $N$ column…
- averageStrategyGiven $T$ distributions $p_0, \dots, p_{T-1}$ over $\mathrm{Fin}\,n$ (each presented as non-negative weights summing to $1$) and $T > 0$,…
- hedge_constructionHedge yields an approximate minimax pair. Let $G$ be a finite two-player zero-sum game with $M \ge 2$ row actions and $N \ge 1$ column…
- empiricalJoint_rowDeviationUtilityEmpirical row deviation utility as a time average. Let $G$ be a finite two-player game with $M$ row actions and $N$ column actions, and…
- prefixHedgeMixedStrategyThe normalised Hedge distribution after a prefix of $t$ column actions is the mixed row strategy with weights…
- empiricalJoint_rowExpectedUtilityRow expected utility of the empirical joint distribution. Fix a finite two-player game with $M$ row actions and $N$ column actions, and…
- empiricalJoint_rowMarginalRow marginal of the empirical joint distribution. Fix $T \ge 1$ rounds of play in which the row player uses mixed strategies…
- empiricalJoint_colExpectedUtilityColumn utility of the empirical joint distribution. Consider a finite two-player game with $M$ row actions and $N$ column actions, whose…
- empiricalJoint_colDeviationUtilityColumn deviation utility of the empirical joint distribution. Let $G$ be a finite two-player game with $M$ row actions and $N$ column…
- empiricalStrategyGiven $T > 0$ pure actions $a_0, \dots, a_{T-1} \in \mathrm{Fin}\,n$, the empirical strategy is the mixed strategy assigning to…
- OnlineLearning.payoffVsPure_le_oneExpected payoff against a pure column is at most one. Let $G$ be a finite two-player zero-sum game whose payoff matrix $A$ has every entry…
- empiricalJoint_col_deviation_leColumn regret bound gives column deviation bound. Let $G$ be a finite two-player game with column utility $u_c$ over $M$ row actions and…
- payoffVsPureGiven a game $G$, a mixed row strategy $p$, and a pure column $j$, the expected payoff against column $j$ is…
- approx_minimaxApproximate minimax for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with payoff matrix $A$, having $M \ge 2$ row…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in /-- A mixed strategy over `n` pure actions: a probability distribution on `Fin n`, kept as an explicit weight vector together with nonnegativity and the sum-to-one law. [CBL06, §7.1]; [FS99, §2]. This is enough for finite games and avoids extra simplex infrastructure. -/ structure MixedStrategy (n : ℕ) where weights : Fin n → ℝ nonneg : ∀ i, 0 ≤ weights i sum_one : ∑ i : Fin n, weights i = 1