Lemma 8 — , for any sequence of deviations
ProvedWeightedCongestionBR.lemma_8algorithmic-game-theoryapproximate-equilibriacongestion-gamesp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a weighted polynomial congestion game of degree with weights . Start from any state and apply any finite sequence of unilateral deviations; let be the set of players that deviate, the final state, and the cost of immediately after its last deviation. Then
For the moves of phase of Algorithm 1 this is the paper's .
Differences from the source:
- generalization: the moves of a phase i of Algorithm 1 → any finite list of unilateral deviations from any state; reason: the proof uses only that the moves are unilateral; a phase of Algorithm 1 is such a list, with R_i its movers
- 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 import Definitions.Def_WeightedCongestionBR_runCosts set_option autoImplicit false open scoped NNReal open HarksKlimm.Consistency
Formal statement
namespace WeightedCongestionBR
/-- **Lemma 8** (Giannakopoulos, Noarov, Schulz, *Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses*, arXiv:1810.12806v6, p.15), for any finite sequence of unilateral deviations. For every phase `i`,
`Φ_{R_i}(s^i) ≤ α ∑_{u ∈ R_i} C_u(i)`, where `R_i` are the players that moved in phase `i` and `C_u(i)`
is the cost of `u` immediately after its last move in phase `i`.
**Formalization Note** The phase is replaced by an arbitrary list `mv` of unilateral deviations
applied to a state `s₀` (`runCosts`); `R` is the set of players that appear in `mv`, the final
state is `(runCosts G s₀ mv).1` and `C_u(i)` is `(runCosts G s₀ mv).2 u`. A phase of Algorithm 1 is
such a list. Weights satisfy `w_u ≥ 1` (p.6). -/
theorem lemma_8 {n r : ℕ} (G : Game n r) (d : ℕ) (hd : 1 ≤ d)
(hG : CongestionApproxPNE.IsPolyGame d G) (hw : ∀ u, 1 ≤ G.demand u)
(s₀ : G.Profile) (mv : List (Σ u : Fin n, G.Strategy u)) :
partialPot G (mv.map Sigma.fst).toFinset (runCosts G s₀ mv).1 ≤
alphaC d * ∑ u ∈ (mv.map Sigma.fst).toFinset, (runCosts G s₀ mv).2 u := by sorry
end WeightedCongestionBR
Source
Giannakopoulos, Noarov, Schulz, Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses, arXiv:1810.12806v6, Lemma 8, p.15
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.