Lemma 10a), p. 27 — on a demand slice the SO cost is Lipschitz with constant |A|·T(w)
ProvedSensitivityPoA.Holder.lemma_10_ap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchysensitivity-analysissocial-optimum
Let be a demand vector with , and let and be two games of the game space with the same demand vector (the demand slice ). Then
On a demand slice the optimal cost therefore moves at most linearly in the distance of the cost functions.
Formalization Note is the distance (3.3); on a demand slice it is the largest difference of the cost functions on .
Preamble
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SensitivityPoA_Holder_Setting
Formal statement
namespace SensitivityPoA.Holder
open KellyStochasticNetworks
/-- Lemma 10a), p. 27: on a demand slice the SO cost is Lipschitz with constant `|A|·T(w)`. -/
theorem lemma_10_a (N : Network) (hN : N.Standing) (Γ1 Γ2 : Game N)
(h1 : Γ1 ∈ gameSpace N) (h2 : Γ2 ∈ gameSpace N) (hd : Γ1.d = Γ2.d) :
|SOCost Γ1 - SOCost Γ2| ≤ (N.J : ℝ) * totalDemand Γ1.d * gameDist Γ1 Γ2 := 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. 27, Lemma 10a)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.