EconCSLib.StrategicGame
structureimported Lean
A strategic game (normal-form game) with players N and utilities in U. The structure records only the bare data: strategy spaces and a payoff function. All assumptions (finiteness, ordering, computability) are added at usage sites.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in structure EconCSLib.StrategicGame (N : Type*) (U : Type*)
- Defined in
- EconCSLib, `StrategicGame`
- Lean proof
- By xbei, Claude (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.EconCSLib.StrategicGame← StrategicGame (EconCSLib/GameTheory/StrategicGame/Basic.lean:33): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Used by 110
- EconCSLib.StrategicGame.pureToMixed_not_isCompletelyMixed_of_neA point-mass mixed strategy is not completely mixed when there is another pure strategy available.
- EconCSLib.StrategicGame.MixedStrategyA mixed strategy for player
i: a probability distribution over pure strategies. Requires[Fintype (G.strategy i)]but NOT[Fintype N]. - IsBestResponsePlayer
iis playing a best response to profileσin gameGif no unilateral deviation to any strategys'yields a higher payoff. - EconCSLib.StrategicGame.nash_map_cont
nash_map Gis a continuous self-map of the product simplex. - EconCSLib.StrategicGame.IsCompletelyMixedProfile.playerA completely mixed profile gives a completely mixed strategy for each player.
- IsWeaklyDominant.isBestResponseT2: A weakly dominant strategy is a best response to any profile where player
iplays it. - 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.uniformMixedProfile_isCompletelyMixedThe uniform mixed profile is completely mixed.
- Auction.FirstPrice.gameFirst-price auction as a strategic game. This is also the game induced by
mechanismviaMechanismWithTransfers.toStrategicGame; see… - SingleParameterMechanism.withMyersonPayment_isDSIC_of_isMonotoneMyerson Lemma, Property 2: a monotone allocation rule is DSIC when paired with the canonical Myerson payment rule.
- Auction.ReserveSecondPrice.game_eq_toStrategicGame
game reserve vequals the strategic game induced bymechanism reserve. - EconCSLib.StrategicGame.IsZeroSum.nash_payoff_eqIn a zero-sum game, all Nash equilibria yield the same payoff for player 0. [MSZ Theorem 4.44-4.45]
- EconCSLib.StrategicGame.IsDominanceSolvableA game is dominance-solvable if IESDS yields a unique surviving profile.
- EconCSLib.StrategicGame.g_function_nonnegThe augmented weight is nonnegative.
- MatrixGame.exists_strategic_game_nash_equilibriumThe strategic-game embedding of a finite matrix game admits a mixed Nash equilibrium. Combines…
- EconCSLib.StrategicGame.MixedSType abbreviation for the product of standard simplices (one per player), used throughout this file. Defined as an
abbrevso Lean… - EconCSLib.StrategicGame.wsum_magic_ineqHelper: weighted-average inequality on the simplex. If
∑_i σ_i * f_i = c, then there existsiwith0 < σ_iandf i ≤ c. - EconCSLib.StrategicGame.IsZeroSum.negIn a zero-sum game, player 1's payoff is the negation of player 0's. Purely algebraic: holds in any additive group, no order or field…
- EconCSLib.StrategicGame.IsZeroSum.neg'In a zero-sum game, player 0's payoff is the negation of player 1's.
- EconCSLib.StrategicGame.pureToMixedEmbed a pure strategy as a mixed strategy (point mass).
- EconCSLib.StrategicGame.deviateMixedDeviate player
whoto pure strategys', keeping others' mixed strategies. - Auction.FirstPrice.game_eq_toStrategicGame
game vequals the strategic game induced bymechanism. The payoffs agree becausepaymentRule b i = if i = winner b then b i else 0,… - EconCSLib.StrategicGame.IsZeroSumA two-player game is zero-sum if payoffs sum to zero at every profile. [MSZ 4.39]
- EconCSLib.StrategicGame.ProfileThe type of strategy profiles for game
G: each player picks a strategy. This is a dependent function∀ i, G.strategy i. The profile… - EconCSLib.StrategicGame.uniformMixedProfileThe profile where every player uses the uniform mixed strategy.
- MatrixGame.toStrategicGame_isZeroSum
A.toStrategicGamesatisfies the abstract zero-sum predicate: by construction player 1's payoff is the negation of player 0's. - EconCSLib.StrategicGame.welfareThe social welfare of a profile: the sum of all players' payoffs. Requires
[Fintype N]and[AddCommMonoid U]. - MatrixGame.toStrategicGameThe two-player zero-sum strategic game associated with a matrix game. See
MatrixGame.toStrategicGame_isZeroSumfor the proof that this… - EconCSLib.StrategicGame.nash_mapThe Nash best-response map: sends a mixed profile
σto the profile where each playeriplays proportional tog_function i σ. A fixed… - MatrixGame.instDecidableEqStrategyFinOfNatNatToStrategicGameMatrixGame.instDecidableEqStrategyFinOfNatNatToStrategicGame
- EconCSLib.StrategicGame.IsZeroSum.decidableStrategicGame.IsZeroSum.decidable
- EconCSLib.StrategicGame.uniformMixed_posEvery pure strategy has positive probability under the uniform mixed strategy.
- EconCSLib.StrategicGame.Survives.prevSurvival at round n+1 implies survival at round n.
- EconCSLib.StrategicGame.IsConstantSum.welfare_eqTwo-player constant-sum games have constant social welfare at every profile.
- EconCSLib.StrategicGame.IsConstantSum.nash_payoff_eq_p1In a constant-sum game, all Nash equilibria yield the same payoff for player 1.
- MechanismWithTransfers.toStrategicGameThe strategic game induced by a transfer mechanism and an external utility rule. Utility is supplied as a function of: - allocation -…
- EconCSLib.StrategicGame.IsConstantSumA two-player game is constant-sum if payoffs sum to
cat every profile. - EconCSLib.StrategicGame.IsZeroSum.expectedPayoff_negIn a zero-sum game, player 1's expected payoff is the negation of player 0's.
- GameTree.toStrategicGameThe strategic-form extraction of a finite perfect-information tree.
- EconCSLib.StrategicGame.IsCompletelyMixedProfileA mixed profile is completely mixed if every player's mixed strategy is completely mixed.
- EconCSLib.StrategicGame.Survives.monoSurvival is monotone: later rounds ⊆ earlier rounds.
- MatrixGame.toMixedProfile_zeroMatrixGame.toMixedProfile_zero
- EconCSLib.StrategicGame.evaluate_at_mixed_cont
evaluate_at_mixed G iis continuous in the mixed profile. - IsBestResponse.congr_payoffT1: Best response depends only on player
i's payoff column. - EconCSLib.StrategicGame.IsZeroSum.expectedPayoff_add_zeroMixed-strategy version of the zero-sum axiom: expected payoffs sum to
0. - StrictlyDominates.weaklyStrict dominance implies weak dominance.
- EconCSLib.StrategicGame.IsOrdinalPotential.isNash_iff_localMaxNash ↔ local maximizer of ordinal potential.
- SingleParameterMechanism.isMonotone_of_isDSICMyerson Lemma, Property 1: every DSIC single-parameter mechanism has a monotone allocation rule.
- EconCSLib.StrategicGame.Profile.deviate_of_neAt every other player, the updated profile is unchanged.
- Auction.SecondPrice.gameSecond-price auction as a strategic game. This is also the game induced by
mechanismviaMechanismWithTransfers.toStrategicGame; see… - EconCSLib.StrategicGame.Profile.deviate_selfDeviating to the same strategy is the identity.
- Auction.ReserveSecondPrice.gameReserve second-price auction as a strategic game.
- EconCSLib.StrategicGame.nash_map_auxThe normalized augmented weight:
g_function i σ a / ∑_b g_function i σ b. Private auxiliary used to constructnash_map. - EconCSLib.StrategicGame.IsZeroSum.expectedPayoff_neg'In a zero-sum game, player 0's expected payoff is the negation of player 1's.
- BayesianSingleItemAuction.interimQuasiLinearUtilityIntegrand_le_of_isDSICPointwise DSIC inequality for the interim utility integrand.
- EconCSLib.StrategicGame.IsRationalizableA strategy is rationalizable if it survives all rounds.
- EconCSLib.StrategicGame.IsZeroSum.nash_payoff_eq_p1In a zero-sum game, all Nash equilibria yield the same payoff for player 1.
- isNashEq_iffT6: The checker correctly decides Nash equilibrium (soundness and completeness).
- EconCSLib.StrategicGame.Profile.deviate_sameAt the deviated player, the updated profile returns the new strategy.
- IsNashEquilibriumA profile
σis a pure Nash equilibrium of gameGif every player is playing a best response: no player can profitably deviate. - EconCSLib.StrategicGame.IsExactPotentialAn exact potential function: the change in
Φequals the change in the deviating player's payoff. - EconCSLib.StrategicGame.evaluate_at_mixed_eq_mixed_g
evaluate_at_mixedis the restriction ofmixed_gto simplex weights. - EconCSLib.StrategicGame.IsOrdinalPotentialAn ordinal potential function: a unilateral deviation improves payoff iff it increases Φ.
- EconCSLib.StrategicGame.evaluate_at_mixedExpected payoff of player
iunder mixed profileσ. Sums over all pure profiles, weighting by the product of each player's probability. - WeaklyDominatesStrategy
sweakly dominates strategys'for playeri. - EconCSLib.StrategicGame.evaluate_at_mixed_linear
evaluate_at_mixed G iis linear in thei-th mixed strategy: for anyτ : stdSimplex ℝ (G.strategy i),… - IsStrictlyDominant.isWeaklyDominantA strictly dominant strategy is weakly dominant.
- EconCSLib.StrategicGame.uniformMixed_applyThe uniform mixed strategy assigns
1 / cardto every pure strategy. - MatrixGame.expectedPayoff_toStrategicGame_oneMirror:
expectedPayoff A.toStrategicGame p 1 = -(A.E (p 0) (p 1)). - EconCSLib.StrategicGame.uniformMixed_isCompletelyMixedThe uniform mixed strategy is completely mixed on any finite nonempty strategy set.
- EconCSLib.StrategicGame.nash_map_certThe normalized augmented weights form a valid probability distribution on
G.strategy i. - EconCSLib.StrategicGame.mixed_gMultilinear payoff functional on raw weight vectors
m : ∀ i, G.strategy i → ℝ. Same asevaluate_at_mixedbut with arbitrary (not… - EconCSLib.StrategicGame.uniformMixedThe uniform mixed strategy over a finite nonempty strategy set.
- EconCSLib.StrategicGame.IsNashEquilibrium.isRationalizableNash strategies are rationalizable.
- EconCSLib.StrategicGame.SurvivesA strategy survives round
nof iterated strict dominance elimination. Round 0: all strategies survive. Round n+1:ssurvives if it… - EconCSLib.StrategicGame.IsMixedNashEqA mixed profile is a mixed Nash equilibrium if no player can improve their expected payoff by deviating to any pure strategy. By linearity…
- EconCSLib.StrategicGame.g_functionAugmented weight for pure strategy
aof playeriat mixed profileσ: the original probabilityσ_i(a)plus the positive part of the… - IsNashEquilibrium.of_dominantT3: If every player has a weakly dominant strategy and
σassigns each player their dominant strategy, thenσis a Nash equilibrium. - StrictlyDominatesStrategy
sstrictly dominates strategys'for playeri. - EconCSLib.StrategicGame.g_function_cont
g_function G i (· ) ais continuous in the mixed profile (fixedi,a). - EconCSLib.StrategicGame.IsDegenerateCorrelatedEqA degenerate correlated equilibrium supported on a single profile. This is the only honest correlated-equilibrium notion currently…
- EconCSLib.StrategicGame.isZeroSum_iff_isConstantSum_zero
IsZeroSum GandIsConstantSum G 0are the same proposition. - EconCSLib.StrategicGame.sigma_le_g_functionThe augmented weight is at least
σ_i(a). - MatrixGame.instNonemptyStrategyFinOfNatNatToStrategicGameMatrixGame.instNonemptyStrategyFinOfNatNatToStrategicGame
- EconCSLib.StrategicGame.IsZeroSum.welfare_eq_zeroTwo-player zero-sum games have zero social welfare at every profile.
- EconCSLib.StrategicGame.IsCompletelyMixedA player's mixed strategy is completely mixed if every pure strategy is assigned positive probability. This is the strategic-form…
- isNashEqExecutable Nash equilibrium checker. Returns
trueiffσis a pure Nash equilibrium ofG. - MatrixGame.toMixedProfileBuild a
MixedProfileoftoStrategicGamefrom a saddle-point pair. - IsStrictlyDominantStrategy
sis strictly dominant for playeri. - EconCSLib.StrategicGame.expectedPayoffExpected payoff for player
whounder mixed profilep.EU(p, who) = ∑_{σ : Profile} (∏_i p_i(σ_i)) · payoff(σ, who)Requires… - MechanismWithTransfers.toQuasiLinearGameThe standard quasi-linear specialization of
toStrategicGame. - EconCSLib.StrategicGame.deviateUnilateral deviation in a game-bound profile: player
iswitches tos', while all other players keep their current strategies. - EconCSLib.StrategicGame.pureProfileToMixedEmbed a pure profile as a mixed profile.
- Auction.FirstPrice.no_dominant_strategyNo dominant strategy exists in first-price auctions. For any bidder
iand any bidbi, there exists a profile where biddingbiis… - EconCSLib.StrategicGame.IsExactPotential.maximizer_is_nashA profile maximizing an exact potential is a Nash equilibrium.
- EconCSLib.StrategicGame.mixedNashEquilibriumNash equilibrium predicate at the mixed-profile level:
σis a Nash equilibrium ofGif no playerican improve by unilaterally… - EconCSLib.StrategicGame.IsConstantSum.negIn a constant-sum game, player 1's payoff is
cminus player 0's.AddCommGroupis needed (not justAddGroup): the RHS usesSub,… - EconCSLib.StrategicGame.IsZeroSum.toIsConstantSumA zero-sum game is a constant-sum game with constant
0. - EconCSLib.StrategicGame.IsNashEquilibrium.survivesNash equilibrium strategies survive all rounds. [MSZ 4.31]
- MatrixGame.toMixedProfile_oneMatrixGame.toMixedProfile_one
- IsWeaklyDominantStrategy
sis weakly dominant for playeri. - EconCSLib.StrategicGame.IsConstantSum.nash_payoff_eqIn a constant-sum game, all Nash equilibria yield the same payoff for player 0. [MSZ Theorem 4.44–4.45]
- EconCSLib.StrategicGame.evaluate_at_mixed_update_cont
σ ↦ evaluate_at_mixed G i (update σ i (stdSimplex.pure a))is continuous. - EconCSLib.StrategicGame.MixedProfileA mixed profile: each player has a mixed strategy. No finiteness constraint on
N(player set can be arbitrary). - EconCSLib.StrategicGame.IsConstantSum.zero_isZeroSumA constant-sum game whose constant is
0is zero-sum. - Mechanism.toStrategicGameThe strategic game induced by a mechanism and a utility function. Each agent's strategy space is their type space
T i(they choose what… - EconCSLib.StrategicGame.one_le_sum_gThe sum of augmented weights is at least 1.
- SingleParameterMechanism.payment_sandwichFor a DSIC single-parameter mechanism, fixing all other bids yields the standard two-sided bound on payment differences.
- MatrixGame.instFintypeStrategyFinOfNatNatToStrategicGameMatrixGame.instFintypeStrategyFinOfNatNatToStrategicGame
- EconCSLib.StrategicGame.nash_iff_degenerate_ceA profile is a "degenerate" correlated equilibrium (point mass on one profile) if and only if it is a Nash equilibrium.
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in /-- A strategic game (normal-form game) with players `N` and utilities in `U`. The structure records only the bare data: strategy spaces and a payoff function. All assumptions (finiteness, ordering, computability) are added at usage sites. -/ structure EconCSLib.StrategicGame (N : Type*) (U : Type*) where /-- The strategy space of each player. -/ strategy : N → Type* /-- The payoff function: maps a strategy profile to each player's utility. -/ payoff : (∀ i, strategy i) → N → U