Lemma 1c), p. 13 — with M-Lipschitz costs, an ǫ-approximate WE flow costs within |A|·√(M·ǫ)·T(d) + ǫ of a WE flow
ProvedSensitivityPoA.Holder.lemma_1_capproximate-equilibriumcongestion-gameslipschitzp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a generalized nonatomic congestion game, , an -approximate WE flow and a WE flow of . Suppose every arc cost is Lipschitz continuous on with Lipschitz constant . Write for the user cost of pair (2.2). Then:
- for every arc ;
- for every O/D pair ;
This is the estimate that produces the exponent in the Hölder continuity of the price of anarchy (Lemma 10d), Theorem 9); Example 2 shows it is tight.
Formalization Note Network.Basic contains G1–G2 but does not impose the later Condition 1. The first bound is printed with ""; Example 2 () gives , as the paper notes on p. 14, so the statement uses . is the number of arcs, cast to a real number.
Preamble
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SensitivityPoA_Holder_Setting
Formal statement
namespace SensitivityPoA.Holder
open KellyStochasticNetworks
/-- Lemma 1c), p. 13 (the first printed `<` read `≤`, attained in Example 2). The user cost
`L_k(τ, d)` (2.2) is `minPathCost Γ ftil k` for the WE flow `ftil`. -/
theorem lemma_1_c (N : Network) (hN : N.Basic) (Γ : Game N) (hΓ : Γ.IsGeneralized)
(ε : ℝ) (hε : 0 < ε) (f ftil : Fin N.R → ℝ) (hf : IsApproxWE Γ ε f) (hftil : IsWE Γ ftil)
(M : ℝ) (hM0 : 0 < M) (hM : ∀ j, LipOnIcc (Γ.τ j) (totalDemand Γ.d) M) :
(∀ j, |Γ.τ j (linkFlow N.A f j) - Γ.τ j (linkFlow N.A ftil j)| ≤ Real.sqrt (M * ε)) ∧
(∀ k, |minPathCost Γ ftil k - minPathCost Γ f k| ≤ (N.J : ℝ) * Real.sqrt (M * ε)) ∧
|cost Γ f - cost Γ ftil| ≤ (N.J : ℝ) * Real.sqrt (M * ε) * totalDemand Γ.d + ε := by sorry
end SensitivityPoA.Holder
Source
Wu, Möhring, A sensitivity analysis of the PoA in non-atomic congestion games, arXiv:2007.13979v3 (2021), p. 13, Lemma 1c)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.