Lemma 6 — potential change under one deviation
ProvedWeightedCongestionBR.lemma_6algorithmic-game-theoryapproximate-equilibriacongestion-gamesp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a weighted polynomial congestion game of degree with weights . Let be a player, a set of players with , and two states that differ only in the strategy of player . Then
So a move that improves the mover's cost by more than a factor decreases the partial potential of every group containing the mover.
Differences from the source:
- 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_partialPot import Definitions.Def_WeightedCongestionBR_alphaC set_option autoImplicit false open scoped NNReal open HarksKlimm.Consistency
Formal statement
namespace WeightedCongestionBR
/-- **Lemma 6** (Giannakopoulos, Noarov, Schulz, *Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses*, arXiv:1810.12806v6, p.12). Let `u` be a player, `R` a set of players with `u ∈ R`, and `s`, `s'`
states that differ only in the strategy of `u`. Then `Φ_R(s) − Φ_R(s') ≥ C_u(s) − α C_u(s')`.
**Formalization Note** Weights satisfy `w_u ≥ 1` (p.6). -/
theorem lemma_6 {n r : ℕ} (G : Game n r) (d : ℕ) (hd : 1 ≤ d)
(hG : CongestionApproxPNE.IsPolyGame d G) (hw : ∀ u, 1 ≤ G.demand u)
(u : Fin n) (R : Finset (Fin n)) (hu : u ∈ R) (s s' : G.Profile) (hss' : ∀ v, v ≠ u → s v = s' v) :
privateCost G s u - alphaC d * privateCost G s' u ≤ partialPot G R s - partialPot G R s' := by sorry
end WeightedCongestionBR
Source
Giannakopoulos, Noarov, Schulz, Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses, arXiv:1810.12806v6, Lemma 6, p.12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.