Theorem 1 —
ProvedWeightedCongestionBR.theorem_1algorithmic-game-theoryapproximate-equilibriacongestion-gamesp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a positive integer and . The Price of Anarchy of -approximate equilibria in weighted polynomial congestion games of degree satisfies
Together with Theorem 2 it identifies , which Lemma 7 uses at .
Differences from the source:
- encoding: PoA_d(ρ) = sup over games of max over ρ-equilibria of C(s)/C(s*) → every ratio C(s)/C(s*) with s a ρ-equilibrium and s* a social-cost minimizer, C(s*) > 0, is at most the bound; reason: an upper bound on a supremum is an upper bound on each element; games with C(s*) = 0 have the undefined ratio 0/0
- 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_WeightedCongestionBR_genGolden import Definitions.Def_DirectTradeCoffee_lambertW import Definitions.Def_WeightedCongestionBR_PoASet set_option autoImplicit false open scoped NNReal
Formal statement
namespace WeightedCongestionBR
/-- **Theorem 1** (Giannakopoulos, Noarov, Schulz, *Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses*, arXiv:1810.12806v6, p.7). The Price of Anarchy of `ρ`-approximate equilibria in weighted
polynomial congestion games of degree `d` is at most `Φ_{d,ρ}^{d+1}`; in particular
`PoA_d(ρ) ≤ [d / W(d/ρ)]^{d+1}`.
**Formalization Note** `PoA_d(ρ) ≤ B` is stated as: every element of `PoASet d ρ` is at most `B`. -/
theorem theorem_1 (d : ℕ) (ρ : ℝ) (hd : 1 ≤ d) (hρ : 1 ≤ ρ) :
∀ q ∈ PoASet d ρ, q ≤ genGolden d ρ ^ (d + 1) ∧
q ≤ ((d : ℝ) / DirectTradeCoffee.lambertW ((d : ℝ) / ρ)) ^ (d + 1) := by sorry
end WeightedCongestionBR
Source
Giannakopoulos, Noarov, Schulz, Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses, arXiv:1810.12806v6, Theorem 1, p.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.