Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A minimizer of ∑j∫0yjDj\sum_j \int_0^{y_j} D_j∑j​∫0yj​​Dj​ is a Wardrop equilibrium

Proved
KellyStochasticNetworks.wardrop_from_minimizer

by naimengye · Sep 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmic-game-theoryconvex-optimizationoperations-researchstochastic-networks

Consider the convex program in the proof of Theorem 4.3:

minimize∑j∫0yjDj(u) duover feasible route flows x≥0 with Hx=f,y=Ax.\text{minimize}\quad \sum_j \int_0^{y_j} D_j(u)\,du \qquad\text{over feasible route flows } x \ge 0 \text{ with } Hx = f, \quad y = Ax .minimizej∑​∫0yj​​Dj​(u)duover feasible route flows x≥0 with Hx=f,y=Ax.

If xxx is feasible and minimizes this objective over the feasible set, then xxx is a Wardrop equilibrium: every route carrying positive traffic has minimal delay among the routes serving the same source–destination pair.

This is the half of the book's one-to-one correspondence that delivers Theorem 4.3, since the feasible region is convex and compact and the objective is continuous, so a minimizer exists. The mechanism is the first-order conditions: differentiating in yjy_jyj​ identifies the multiplier μj\mu_jμj​ with the link delay Dj(yj)D_j(y_j)Dj​(yj​), and differentiating in xrx_rxr​ gives that the multiplier λs(r)\lambda_{s(r)}λs(r)​ equals the route delay ∑jμjAjr\sum_j \mu_j A_{jr}∑j​μj​Ajr​ on routes carrying traffic and is a lower bound on the others. Read back, λs(r)\lambda_{s(r)}λs(r)​ is the minimal delay available to the source–destination pair, which is Definition 4.2.

It is worth being clear about what is not being minimized. The objective is ∑j∫0yjDj\sum_j\int_0^{y_j}D_j∑j​∫0yj​​Dj​, not the total delay ∑jyjDj(yj)\sum_j y_jD_j(y_j)∑j​yj​Dj​(yj​) that a planner would want to minimize. Braess's paradox is exactly the gap between the two.

Formalization Note Minimality is stated directly as the defining inequality over the feasible set, so no optimization API is presupposed. The incidence matrix is constrained to have entries 000 or 111, as in the book's definition for this chapter, and the delay functions are continuous and increasing in the weak sense.

Preamble
import Mathlib
import Definitions.Def_KellyStochasticNetworks_Wardrop
Formal statement
namespace KellyStochasticNetworks

theorem wardrop_from_minimizer {J R Sd : ℕ} (A : Fin J → Fin R → ℝ) (s : Fin R → Fin Sd)
    (D : Fin J → ℝ → ℝ) (f : Fin Sd → ℝ)
    (hA : ∀ j r, A j r = 0 ∨ A j r = 1)
    (hD : ∀ j, Continuous (D j)) (hmono : ∀ j, Monotone (D j))
    (x : Fin R → ℝ) (hx : x ∈ wardropFeasible s f)
    (hmin : ∀ z ∈ wardropFeasible s f, wardropObjective A D x ≤ wardropObjective A D z) :
    IsWardropEquilibrium A s D f x := by sorry

end KellyStochasticNetworks
Source
Kelly & Yudovina, Stochastic Networks, CUP 2014, p. 97 (PDF p. 105), the proof of Theorem 4.3: 'Consider the optimization problem minimize sum_{j} int_0^{y_j} D_j(u) du subject to Hx = f, Ax = y, over x >= 0, y. ... at the minimum the derivative with respect to y_j is equal to 0, i.e. we can identify mu_j = D_j(y_j) as the delay on link j. The derivative with respect to x_r must be non-negative, and 0 if x_r > 0, so lambda_{s(r)} = sum_j mu_j A_{jr} if x_r > 0, <= sum_j mu_j A_{jr} if x_r = 0. Therefore, we can interpret lambda_{s(r)} as the minimal delay available to the source-destination pair s(r). Consequently, solutions of this optimization problem are in one-to-one correspondence with Wardrop equilibria.' sha256 ec271d555059aee58613e5e9a98b8346214b16185c527314f5d94c1ac8b17b6a
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 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