Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

p. 43, first display — ‖Γ′ − Λ_{T(d)}(Γ)‖ = max_{a,x∈[0,1]} |τ_a(T(d)x) − τ_a(0)| = max_a |τ_a(T(d)) − τ_a(0)| ≤ M_τ·T(d)

Disproved
SensitivityPoA.SmallDemand.dist_const_le

by mikedeng1 · Oct 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

demand-normalizationgame-distancep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchy

Let τ=(τa)a∈A\tau = (\tau_a)_{a \in A}τ=(τa​)a∈A​ be cost functions (continuous, non-decreasing and non-negative on [0,∞)[0,\infty)[0,∞)), each Lipschitz on [0,b][0, b][0,b] with constant MτM_\tauMτ​. Let d≥0d \ge 0d≥0 be a demand vector with 0<T(d)≤b0 < T(d) \le b0<T(d)≤b, and put Γ=(τ,d)\Gamma = (\tau, d)Γ=(τ,d). Let σa(x)≡τa(0)\sigma_a(x) \equiv \tau_a(0)σa​(x)≡τa​(0) be the constant costs and Γ′=(σ,d/T(d))\Gamma' = (\sigma, d/T(d))Γ′=(σ,d/T(d)) the auxiliary game of total demand 111. Then

∥Γ′−ΛT(d)(Γ)∥=max⁡a∈A, x∈[0,1]∣τa(T(d)⋅x)−τa(0)∣=max⁡a∈A∣τa(T(d))−τa(0)∣≤Mτ⋅T(d).\|\Gamma' - \Lambda_{T(d)}(\Gamma)\| = \max_{a \in A,\ x \in [0,1]} |\tau_a(T(d)\cdot x) - \tau_a(0)| = \max_{a \in A} |\tau_a(T(d)) - \tau_a(0)| \le M_\tau \cdot T(d).∥Γ′−ΛT(d)​(Γ)∥=a∈A, x∈[0,1]max​∣τa​(T(d)⋅x)−τa​(0)∣=a∈Amax​∣τa​(T(d))−τa​(0)∣≤Mτ​⋅T(d).

It says that, after normalization to total demand 111, a game of small total demand is close to the constant-cost game Γ′\Gamma'Γ′, at distance linear in T(d)T(d)T(d).

Formalization Note Each max⁡\maxmax is a real supremum of the image of the indicated set (the first) or Mathlib's sup norm on RA\mathbb R^ARA (the second); both are 000 when there are no arcs. The paper writes σa(x)\sigma_a(x)σa​(x) in the middle term; here it is written τa(0)\tau_a(0)τa​(0). Strict positivity of τ\tauτ is not needed and not assumed.

Preamble
import Mathlib
import Definitions.Def_KellyStochasticNetworks_Wardrop
import Definitions.Def_SensitivityPoA_SmallDemand_Setting
Formal statement
namespace SensitivityPoA.SmallDemand

open KellyStochasticNetworks

/-- p. 43, first display: for `Γ = (τ, d)`, the auxiliary game `Γ' = (σ, d/T(d))` with constant
costs `σ_a ≡ τ_a(0)` and the normalized game `Λ_{T(d)}(Γ)` satisfy
`‖Γ' − Λ_{T(d)}(Γ)‖ = max_{a, x ∈ [0,1]} |τ_a(T(d)·x) − σ_a(x)| = max_a |τ_a(T(d)) − τ_a(0)| ≤ M_τ·T(d)`
when `T(d) ≤ b`. -/
theorem dist_const_le {N : Network} (τ : Fin N.J → ℝ → ℝ) (hτ : ∀ j, IsCostFn (τ j))
    (b Mτ : ℝ) (hLip : ∀ j, LipOnIcc (τ j) b Mτ)
    (d : Fin N.Sd → ℝ) (hd : ∀ k, 0 ≤ d k) (hT : 0 < totalDemand d) (hTb : totalDemand d ≤ b) :
    gameDist (⟨fun j _ => τ j 0, fun k => d k / totalDemand d⟩ : Game N)
        (demandNormalize (totalDemand d) (⟨τ, d⟩ : Game N)) =
      sSup ((fun p : Fin N.J × ℝ => |τ p.1 (totalDemand d * p.2) - τ p.1 0|) ''
        (Set.univ ×ˢ Set.Icc 0 1)) ∧
    sSup ((fun p : Fin N.J × ℝ => |τ p.1 (totalDemand d * p.2) - τ p.1 0|) ''
        (Set.univ ×ˢ Set.Icc 0 1)) = ‖fun j => τ j (totalDemand d) - τ j 0‖ ∧
    ‖fun j => τ j (totalDemand d) - τ j 0‖ ≤ Mτ * totalDemand d := 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. 43, §5.2, first display
Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 15, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me