Claim 8.2, p. 50 — trimming moves each player's mixed strategy by at most 2/(k − 1) in L1
ProvedRubinsteinNash.WeakNash.claim_8_2approximate-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 the trimmed profile of the proof of Lemma 8.1 (each -optimal player drops the actions more than below and renormalises; every other player keeps ). Then for every player ,
So when is large the trimmed profile is close to in every coordinate, which is what keeps the expected payoffs of all players nearly unchanged.
Formalization Note. The page states the claim for the players of the bipartite polymatrix game; it uses no polymatrix structure, so it is stated for an arbitrary finite game. For a player that is not -optimal, and the left side is .
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 claim_8_2 {ι : 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 : ι, ∑ s : S v, |weakTrim u x ε k v s - x v s| ≤ 2 / (k - 1) := by sorry
end RubinsteinNash.WeakNash
Source
Rubinstein, arXiv:1606.04550 (version dated August 26, 2016), Claim 8.2 (= [32, Claim 6]), §8.1, p. 50
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.