§3.5, p. 22 — demand normalizations Λ_υ preserve the game space, WE and SO flows (scaled by 1/υ), and the price of anarchy
ProvedSensitivityPoA.SmallDemand.poa_demandNormalizecongestion-gamesdemand-normalizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchy
Let be a game of the game space and let . Let be its demand normalization, with . Then:
- belongs to the game space;
- for every path vector , is a WE flow of if and only if is a WE flow of ;
- for every path vector , is an SO flow of if and only if is an SO flow of ;
- for every flow of , ;
- the price of anarchy is invariant:
Rescaling the demand to total demand in this way is what lets the small-demand regime be compared with a fixed reference game of total demand .
Preamble
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SensitivityPoA_SmallDemand_Setting
Formal statement
namespace SensitivityPoA.SmallDemand
open KellyStochasticNetworks
/-- §3.5, p. 22: a demand normalization `Λ_υ` maps the game space into itself; `˜f` and `f∗`
are a WE flow and an SO flow of `Γ` iff `˜f/υ` and `f∗/υ` are a WE flow and an SO flow of
`Λ_υ(Γ)`; `C(Γ, f) = υ · C(Λ_υ(Γ), f/υ)` for every flow `f` of `Γ`; hence `ρ(Λ_υ(Γ)) = ρ(Γ)`. -/
theorem poa_demandNormalize {N : Network} (Γ : Game N) (hΓ : Γ ∈ gameSpace N) (υ : ℝ)
(hυ : 0 < υ) :
demandNormalize υ Γ ∈ gameSpace N ∧
(∀ f : Fin N.R → ℝ, IsWE Γ f ↔ IsWE (demandNormalize υ Γ) (fun r => f r / υ)) ∧
(∀ f : Fin N.R → ℝ, IsSO Γ f ↔ IsSO (demandNormalize υ Γ) (fun r => f r / υ)) ∧
(∀ f : Fin N.R → ℝ, IsFlow Γ f →
cost Γ f = υ * cost (demandNormalize υ Γ) (fun r => f r / υ)) ∧
PoA (demandNormalize υ Γ) = PoA Γ := 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. 22, §3.5 (demand normalizations)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.