Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.4 — a flow feasible for (1+δ)r(1+\delta)r(1+δ)r costs at least C(f∗)+δ∑iLi∗(f∗) riC(f^*)+\delta\sum_i L^*_i(f^*)\,r_iC(f∗)+δ∑i​Li∗​(f∗)ri​

Proved
SelfishRouting.Linear.lemma_4_4

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

linear-latencymarginal-costoptimal-flowp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1selfish-routing

Let every edge have a linear latency ℓe(x)=aex+be\ell_e(x)=a_ex+b_eℓe​(x)=ae​x+be​ with ae,be≥0a_e,b_e\ge 0ae​,be​≥0, let the rates rir_iri​ be positive and the route incidences 0/10/10/1, and let f∗f^*f∗ be an optimal flow for the rates rrr. Let Li∗(f∗)=min⁡P∈PiℓP∗(f∗)L^*_i(f^*)=\min_{P\in\mathcal P_i}\ell^*_P(f^*)Li∗​(f∗)=minP∈Pi​​ℓP∗​(f∗) be the minimum marginal cost of increasing flow on an sis_isi​-tit_iti​ path with respect to f∗f^*f∗. Then for every δ>0\delta>0δ>0, every flow fff feasible for the rates (1+δ)r(1+\delta)r(1+δ)r satisfies

C(f) ≥ C(f∗)+δ∑i=1kLi∗(f∗) ri.C(f)\ \ge\ C(f^*)+\delta\sum_{i=1}^{k}L^*_i(f^*)\,r_i .C(f) ≥ C(f∗)+δi=1∑k​Li∗​(f∗)ri​.

The per-unit cost of pushing additional traffic through the network is at least the current minimum marginal path cost; this is what bounds the cost of augmenting the optimal flow for r/2r/2r/2 to a flow for rrr in Theorem 4.5.

Formalization Note The rates (1+δ)r(1+\delta)r(1+δ)r are i↦(1+δ)rii\mapsto(1+\delta)r_ii↦(1+δ)ri​. Li∗L^*_iLi∗​ is the minimum of the marginal path costs over the routes serving iii (see the definition item; the routes form a nonempty finite set because ri>0r_i>0ri​>0 and f∗f^*f∗ is feasible). The hypothesis δ>0\delta>0δ>0 is kept as printed. Routes are 0/10/10/1 incidence columns (a disclosed generalization).

Preamble
import Mathlib
import Definitions.Def_KellyStochasticNetworks_Wardrop
import Definitions.Def_SelfishRouting_Linear_Model
import Definitions.Def_SelfishRouting_Linear_LinearLatency
Formal statement
namespace SelfishRouting.Linear

open KellyStochasticNetworks

/-- Lemma 4.4 (p. 16): with linear latencies, if `f*` is optimal for the rates `r` and
`δ > 0`, then every flow feasible for the rates `(1 + δ) r` has cost at least
`C(f*) + δ ∑ᵢ L*ᵢ(f*) rᵢ`. -/
theorem lemma_4_4 {J R Sd : ℕ} (A : Fin J → Fin R → ℝ) (hA : ∀ j r, A j r = 0 ∨ A j r = 1)
    (s : Fin R → Fin Sd) (rate : Fin Sd → ℝ) (hrate : ∀ i, 0 < rate i)
    (a b : Fin J → ℝ) (ha : ∀ j, 0 ≤ a j) (hb : ∀ j, 0 ≤ b j)
    (xstar : Fin R → ℝ) (hxstar : IsOptimalFlow A s (linLatency a b) rate xstar)
    (δ : ℝ) (hδ : 0 < δ)
    (y : Fin R → ℝ) (hy : y ∈ wardropFeasible s (fun i => (1 + δ) * rate i)) :
    SelfishRouting.Bicriteria.cost A (linLatency a b) xstar +
        δ * ∑ i, minMarginalPathCost A s a b xstar i * rate i ≤
      SelfishRouting.Bicriteria.cost A (linLatency a b) y := by sorry

end SelfishRouting.Linear
Source
Roughgarden & Tardos, How Bad is Selfish Routing?, J. ACM 49(2) (2002), author's manuscript of 5 Dec 2001, p. 16, Lemma 4.4
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 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