Proof of Lemma 8.1, p. 50 — for an ε-optimal player and k > 1, the trimmed mass z^v is at most 1/k
ProvedRubinsteinNash.WeakNash.trimMass_le_invapproximate-nash-equilibriump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1weak-nash
Let be a mixed-strategy profile of a finite game, let and , and let be a player whose mixed strategy is an -best mixed response to . Let be the total probability that assigns to actions more than away from the optimum, i.e. with . Then
This is what makes the normalisation in the trimmed profile well defined for the -optimal players.
Formalization Note. The page says only that " is bounded away from 1"; the formalization states the quantitative bound , which for is the bound away from 1. The statement uses no polymatrix structure, so it is stated for an arbitrary finite game, which contains the bipartite polymatrix games of Lemma 8.1.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_DGPNash_NashMap_nashMap import Definitions.Def_DGPNash_WellSupported_Equilibria import Definitions.Def_RubinsteinNash_WeakNash_ApproxEquilibria
Formal statement
namespace RubinsteinNash.WeakNash
theorem trimMass_le_inv {ι : Type*} [Fintype ι] [DecidableEq ι]
{S : ι → Type*} [∀ i, Fintype (S i)] [∀ i, DecidableEq (S i)]
(u : ι → (∀ i, S i) → ℝ) (x : ∀ i, S i → ℝ) (hx : AGT.IsMixedProfile x)
(ε k : ℝ) (hε : 0 < ε) (hk : 1 < k) (v : ι) (hv : IsEpsBestResponse u x ε v) :
DGPNash.WellSupported.trimMass u x ε k v ≤ 1 / k := by sorry
end RubinsteinNash.WeakNash
Source
Rubinstein, arXiv:1606.04550 (version dated August 26, 2016), proof of Lemma 8.1, §8.1, p. 50 (sentence after the definition of x̂: 'for k > 1 and v who plays ϵ-optimally, z^v is bounded away from 1')
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.