Theorem 2 — singleton games with -PoA at least
ProvedWeightedCongestionBR.theorem_2algorithmic-game-theoryapproximate-equilibriacongestion-gamesp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a positive integer and . For every there is a singleton weighted polynomial congestion game of degree (every strategy consists of exactly one resource) whose -approximate Price of Anarchy is at least : it has a -equilibrium and a minimizer of the social cost with and
It shows that Theorem 1 is tight, so .
Differences from the source:
- encoding: the game's ρ-approximate PoA is at least Φ^{d+1} − ε → a ρ-equilibrium s and a social-cost minimizer s* with C(s*) > 0 and C(s)/C(s*) ≥ Φ^{d+1} − ε; reason: the PoA of a game is the maximum of these ratios over its ρ-equilibria
- 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
/-- **Theorem 2** (Giannakopoulos, Noarov, Schulz, *Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses*, arXiv:1810.12806v6, p.9). Let `d` be a positive integer and `ρ ≥ 1`. For every `ε > 0` there is a
singleton weighted polynomial congestion game of degree `d` whose `ρ`-approximate PoA is at least
`Φ_{d,ρ}^{d+1} − ε`.
**Formalization Note** "Singleton" (footnote 11): every strategy has exactly one resource. "PoA at
least `B − ε`" is stated by a `ρ`-equilibrium `s` and a social-cost minimizer `s*` with `C(s*) > 0` and
`C(s)/C(s*) ≥ B − ε`. -/
theorem theorem_2 (d : ℕ) (ρ : ℝ) (hd : 1 ≤ d) (hρ : 1 ≤ ρ) (ε : ℝ) (hε : 0 < ε) :
∃ (n r : ℕ) (G : Game n r), CongestionApproxPNE.IsPolyGame d G ∧
(∀ u : Fin n, ∀ t ∈ G.strategies u, t.card = 1) ∧
∃ s sStar : G.Profile, IsGroupEq G ρ Finset.univ s ∧
(∀ s' : G.Profile, groupCost G Finset.univ sStar ≤ groupCost G Finset.univ s') ∧
0 < groupCost G Finset.univ sStar ∧
genGolden d ρ ^ (d + 1) - ε ≤ groupCost G Finset.univ s / groupCost G Finset.univ sStar := by sorry
end WeightedCongestionBR
Source
Giannakopoulos, Noarov, Schulz, Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses, arXiv:1810.12806v6, Theorem 2, p.9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.