Lemma 10b), p. 27 — on a demand slice the potential values of WE flows differ by O(|A|·T(w)·‖Γ1 − Γ2‖)
ProvedSensitivityPoA.Holder.lemma_10_bp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-functionprice-of-anarchysensitivity-analysis
Let and be two games of the game space with the same demand vector , and let and be WE flows of and . Then
- for every flow ;
- ;
- ;
- .
The WE flow of each game is thus an almost-minimizer of the other game's potential.
Formalization Note "Every flow" is a flow of the common demand vector .
Preamble
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SensitivityPoA_Holder_Setting
Formal statement
namespace SensitivityPoA.Holder
open KellyStochasticNetworks
/-- Lemma 10b), p. 27: potential values on a demand slice. -/
theorem lemma_10_b (N : Network) (hN : N.Standing) (Γ1 Γ2 : Game N)
(h1 : Γ1 ∈ gameSpace N) (h2 : Γ2 ∈ gameSpace N) (hd : Γ1.d = Γ2.d)
(ftil gtil : Fin N.R → ℝ) (hftil : IsWE Γ1 ftil) (hgtil : IsWE Γ2 gtil) :
(∀ f, IsFlow Γ1 f →
|potential Γ1 f - potential Γ2 f| ≤ (N.J : ℝ) * totalDemand Γ1.d * gameDist Γ1 Γ2) ∧
|potential Γ1 ftil - potential Γ2 gtil| ≤ (N.J : ℝ) * totalDemand Γ1.d * gameDist Γ1 Γ2 ∧
(0 ≤ potential Γ1 gtil - potential Γ1 ftil ∧
potential Γ1 gtil - potential Γ1 ftil ≤ 2 * (N.J : ℝ) * totalDemand Γ1.d * gameDist Γ1 Γ2) ∧
(0 ≤ potential Γ2 ftil - potential Γ2 gtil ∧
potential Γ2 ftil - potential Γ2 gtil ≤ 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 10b)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.