p. 43, first display — ‖Γ′ − Λ_{T(d)}(Γ)‖ = max_{a,x∈[0,1]} |τ_a(T(d)x) − τ_a(0)| = max_a |τ_a(T(d)) − τ_a(0)| ≤ M_τ·T(d)
DisprovedSensitivityPoA.SmallDemand.dist_const_ledemand-normalizationgame-distancep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchy
Let be cost functions (continuous, non-decreasing and non-negative on ), each Lipschitz on with constant . Let be a demand vector with , and put . Let be the constant costs and the auxiliary game of total demand . Then
It says that, after normalization to total demand , a game of small total demand is close to the constant-cost game , at distance linear in .
Formalization Note Each is a real supremum of the image of the indicated set (the first) or Mathlib's sup norm on (the second); both are when there are no arcs. The paper writes in the middle term; here it is written . Strict positivity of is not needed and not assumed.
Preamble
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SensitivityPoA_SmallDemand_Setting
Formal statement
namespace SensitivityPoA.SmallDemand
open KellyStochasticNetworks
/-- p. 43, first display: for `Γ = (τ, d)`, the auxiliary game `Γ' = (σ, d/T(d))` with constant
costs `σ_a ≡ τ_a(0)` and the normalized game `Λ_{T(d)}(Γ)` satisfy
`‖Γ' − Λ_{T(d)}(Γ)‖ = max_{a, x ∈ [0,1]} |τ_a(T(d)·x) − σ_a(x)| = max_a |τ_a(T(d)) − τ_a(0)| ≤ M_τ·T(d)`
when `T(d) ≤ b`. -/
theorem dist_const_le {N : Network} (τ : Fin N.J → ℝ → ℝ) (hτ : ∀ j, IsCostFn (τ j))
(b Mτ : ℝ) (hLip : ∀ j, LipOnIcc (τ j) b Mτ)
(d : Fin N.Sd → ℝ) (hd : ∀ k, 0 ≤ d k) (hT : 0 < totalDemand d) (hTb : totalDemand d ≤ b) :
gameDist (⟨fun j _ => τ j 0, fun k => d k / totalDemand d⟩ : Game N)
(demandNormalize (totalDemand d) (⟨τ, d⟩ : Game N)) =
sSup ((fun p : Fin N.J × ℝ => |τ p.1 (totalDemand d * p.2) - τ p.1 0|) ''
(Set.univ ×ˢ Set.Icc 0 1)) ∧
sSup ((fun p : Fin N.J × ℝ => |τ p.1 (totalDemand d * p.2) - τ p.1 0|) ''
(Set.univ ×ˢ Set.Icc 0 1)) = ‖fun j => τ j (totalDemand d) - τ j 0‖ ∧
‖fun j => τ j (totalDemand d) - τ j 0‖ ≤ Mτ * totalDemand d := 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, first display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.