p. 43 — the constant-cost game Γ′ = (σ, d/T(d)), σ_a ≡ τ_a(0), has SO cost C∗(Γ′) ≥ τmin(0)
ProvedSensitivityPoA.SmallDemand.SOCost_const_gecongestion-gamesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchysocial-optimum
Fix a structure satisfying the standing assumptions. Let be functions with for every arc, and let
Let be a demand vector with , let , and let . Then
The lower bound does not depend on , because always has total demand ; this uniformity is what makes the constant of Corollary 5.1 independent of the demand.
Formalization Note is passed as a real number that is the least element of .
Preamble
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SensitivityPoA_SmallDemand_Setting
Formal statement
namespace SensitivityPoA.SmallDemand
open KellyStochasticNetworks
/-- p. 43: with `σ_a ≡ τ_a(0) > 0` and `τmin(0) = min_a τ_a(0)`, the SO cost of the auxiliary game
`Γ' = (σ, d/T(d))` is at least `τmin(0)` for every demand vector `d`, since `T(d/T(d)) = 1`. -/
theorem SOCost_const_ge (N : Network) (hN : N.Standing) (τ : Fin N.J → ℝ → ℝ)
(hpos : ∀ j, 0 < τ j 0) (τmin : ℝ) (hτmin : IsLeast (Set.range fun j => τ j 0) τmin)
(d : Fin N.Sd → ℝ) (hd : ∀ k, 0 ≤ d k) (hT : 0 < totalDemand d) :
τmin ≤ SOCost (⟨fun j _ => τ j 0, fun k => d k / totalDemand d⟩ : Game N) := by sorry
end SensitivityPoA.SmallDemand
Source
Wu, Möhring, A sensitivity analysis of the PoA in non-atomic congestion games, arXiv:2007.13979v3 (2021), p. 43, §5.2, "C∗(Γ′) ≥ τmin(0)"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.