Lemma 1b), p. 13 — potential gap between an ǫ-approximate WE flow and a WE flow
ProvedSensitivityPoA.Holder.lemma_1_bapproximate-equilibriumcongestion-gamesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-function
Let be a generalized nonatomic congestion game, , an -approximate WE flow and a WE flow of , with arc flows and . Then
and consequently
The second estimate is what turns approximate equilibrium into closeness of arc costs in Lemma 1c).
Formalization Note Network.Basic contains G1–G2 but does not impose the later Condition 1. Both upper bounds are printed as ""; Example 2 attains equality in both, so the statement uses .
Preamble
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SensitivityPoA_Holder_Setting
Formal statement
namespace SensitivityPoA.Holder
open KellyStochasticNetworks
/-- Lemma 1b), p. 13 (both printed `< ǫ` read `≤ ǫ`, attained in Example 2). -/
theorem lemma_1_b (N : Network) (hN : N.Basic) (Γ : Game N) (hΓ : Γ.IsGeneralized)
(ε : ℝ) (hε : 0 < ε) (f ftil : Fin N.R → ℝ) (hf : IsApproxWE Γ ε f) (hftil : IsWE Γ ftil) :
(0 ≤ ∑ j, Γ.τ j (linkFlow N.A ftil j) * (linkFlow N.A f j - linkFlow N.A ftil j) ∧
∑ j, Γ.τ j (linkFlow N.A ftil j) * (linkFlow N.A f j - linkFlow N.A ftil j)
≤ potential Γ f - potential Γ ftil ∧
potential Γ f - potential Γ ftil
≤ ∑ j, Γ.τ j (linkFlow N.A f j) * (linkFlow N.A f j - linkFlow N.A ftil j) ∧
∑ j, Γ.τ j (linkFlow N.A f j) * (linkFlow N.A f j - linkFlow N.A ftil j) ≤ ε) ∧
(0 ≤ ∑ j, |Γ.τ j (linkFlow N.A f j) - Γ.τ j (linkFlow N.A ftil j)|
* |linkFlow N.A f j - linkFlow N.A ftil j| ∧
∑ j, |Γ.τ j (linkFlow N.A f j) - Γ.τ j (linkFlow N.A ftil j)|
* |linkFlow N.A f j - linkFlow N.A ftil j| ≤ ε) := 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 1b)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.