Lemma 1a), p. 13 — an ǫ-approximate WE flow is within ǫ of the per-pair minimum path cost
ProvedSensitivityPoA.Holder.lemma_1_aLet be a generalized nonatomic congestion game (continuous, non-decreasing, non-negative arc costs on , non-negative demands), let and let be an -approximate Wardrop equilibrium flow of . Then for every O/D pair ,
and moreover
The total cost of an approximate equilibrium is thus within of what each user would pay on a cheapest path; this is the basic estimate behind Lemma 1c).
Formalization Note Network.Basic contains G1–G2 but does not impose the later Condition 1. The paper prints the first upper bound as "". Only "" follows from (2.7), and Example 2 (p. 13: Pigou's game with ) attains equality, so the statement uses . The lemma's preamble also names a WE flow , which part a) does not use; it is omitted.
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SensitivityPoA_Holder_Setting
namespace SensitivityPoA.Holder
open KellyStochasticNetworks
/-- Lemma 1a), p. 13 (printed `< ǫ` read `≤ ǫ`, attained in Example 2). -/
theorem lemma_1_a (N : Network) (hN : N.Basic) (Γ : Game N) (hΓ : Γ.IsGeneralized)
(ε : ℝ) (hε : 0 < ε) (f : Fin N.R → ℝ) (hf : IsApproxWE Γ ε f) :
(∀ k : Fin N.Sd,
0 ≤ (∑ r ∈ Finset.univ.filter (fun r => N.s r = k), f r * pathCost Γ f r)
- Γ.d k * minPathCost Γ f k ∧
(∑ r ∈ Finset.univ.filter (fun r => N.s r = k), f r * pathCost Γ f r)
- Γ.d k * minPathCost Γ f k ≤ ε) ∧
(∑ k, Γ.d k * minPathCost Γ f k ≤ cost Γ f ∧
cost Γ f ≤ (∑ k, Γ.d k * minPathCost Γ f k) + ε) := by sorry
end SensitivityPoA.Holder
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.