Lemma 1 — group social cost ratio at most
ProvedWeightedCongestionBR.lemma_1algorithmic-game-theoryapproximate-equilibriacongestion-gamesp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a weighted polynomial congestion game of degree and . For any group of players , let and be states such that is a -equilibrium for and every player in uses the same strategy in and . Then
With it gives the upper bound of Theorem 1; for groups it is used through Lemma 9 in the proof of the Key Property (Theorem 3).
Differences from the source:
- generalization: ratio C_R(s)/C_R(s*) ≤ Φ^{d+1} → C_R(s) ≤ Φ^{d+1} C_R(s*); reason: equivalent to the ratio when C_R(s*) > 0; it also covers C_R(s*) = 0, where the ratio is undefined
- encoding: finite player and resource sets N, E → Fin n, Fin r with n, r ≥ 1 (HarksKlimm.Consistency.Game); reason: excludes only games without players or resources, where every cost is 0 and the statement is empty
Preamble
import Mathlib import Definitions.Def_HarksKlimm_Consistency_privateCost import Definitions.Def_CongestionApproxPNE_IsPolyGame import Definitions.Def_WeightedCongestionBR_groupCost import Definitions.Def_WeightedCongestionBR_IsGroupEq import Definitions.Def_WeightedCongestionBR_genGolden set_option autoImplicit false open scoped NNReal open HarksKlimm.Consistency
Formal statement
namespace WeightedCongestionBR
/-- **Lemma 1** (Giannakopoulos, Noarov, Schulz, *Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses*, arXiv:1810.12806v6, p.7). For any group of players `R ⊆ N`, if `s` is a `ρ`-equilibrium for `R`
and every player of `N ∖ R` uses the same strategy in `s` and `s*`, then
`C_R(s)/C_R(s*) ≤ Φ_{d,ρ}^{d+1}`.
**Formalization Note** Stated multiplicatively, `C_R(s) ≤ Φ_{d,ρ}^{d+1} C_R(s*)`, which is the
ratio bound when `C_R(s*) > 0` and also covers `C_R(s*) = 0`. Weights are only assumed positive. -/
theorem lemma_1 {n r : ℕ} (G : Game n r) (d : ℕ) (ρ : ℝ) (hd : 1 ≤ d) (hρ : 1 ≤ ρ)
(hG : CongestionApproxPNE.IsPolyGame d G) (R : Finset (Fin n)) (s sStar : G.Profile)
(hs : IsGroupEq G ρ R s) (hout : ∀ u ∉ R, s u = sStar u) :
groupCost G R s ≤ genGolden d ρ ^ (d + 1) * groupCost G R sStar := by sorry
end WeightedCongestionBR
Source
Giannakopoulos, Noarov, Schulz, Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses, arXiv:1810.12806v6, Lemma 1, p.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.