Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Braess's paradox: adding a road raises the equilibrium delay from 83 to 92

Proved
KellyStochasticNetworks.braess_paradox

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

algorithmic-game-theoryoperations-researchstochastic-networks

Cars travel from south to north through the network of Figure 4.3, at a total rate of six per unit time. There are four one-way roads: S→WS\to WS→W and E→NE\to NE→N, each with delay 10y10y10y when carrying flow yyy, and W→NW\to NW→N and S→ES\to ES→E, each with delay y+50y+50y+50. Two routes are available, S→W→NS\to W\to NS→W→N and S→E→NS\to E\to NS→E→N.

  1. Before. Splitting the traffic evenly, three cars per unit time on each route, is a Wardrop equilibrium, and every route has total delay
10⋅3+(3+50)=83.10\cdot 3 + (3+50) = 83 .10⋅3+(3+50)=83.
  1. After. Add one more road, W→EW\to EW→E, with delay y+10y+10y+10. A third route S→W→E→NS\to W\to E\to NS→W→E→N becomes available. Splitting the traffic evenly three ways, two cars per unit time on each route, is a Wardrop equilibrium of the enlarged network, and every route now has total delay
10⋅4+(2+50)=(2+50)+10⋅4=10⋅4+(2+10)+10⋅4=92.10\cdot 4 + (2+50) = (2+50) + 10\cdot 4 = 10\cdot 4 + (2+10) + 10\cdot 4 = 92 .10⋅4+(2+50)=(2+50)+10⋅4=10⋅4+(2+10)+10⋅4=92.

Adding road capacity raised every driver's delay, from 838383 to 929292. This is Braess's paradox. It is not a failure of the equilibrium concept: in both networks no individual driver can improve by switching, which is precisely the point. It is a failure of the selfish objective to coincide with the social one, and it is in sharp contrast to an electrical network, where adding a link can only make the network easier to traverse.

Formalization Note The two networks are given as explicit incidence matrices and explicit delay functions, so the statement is a concrete arithmetic claim about named data rather than a claim about a class of networks. In the second network the link flows are 4,2,2,4,24, 2, 2, 4, 24,2,2,4,2 rather than all equal, which is why the delay rises: the two 10y10y10y roads each carry four cars instead of three.

Preamble
import Mathlib
import Definitions.Def_KellyStochasticNetworks_Wardrop
Formal statement
namespace KellyStochasticNetworks

theorem braess_paradox :
    (IsWardropEquilibrium braessIncidenceA (fun _ => (0 : Fin 1)) braessDelayA
        (fun _ => 6) ![3, 3]
      ∧ ∀ r : Fin 2, (∑ j, braessDelayA j (linkFlow braessIncidenceA ![3, 3] j)
            * braessIncidenceA j r) = 83)
  ∧ (IsWardropEquilibrium braessIncidenceB (fun _ => (0 : Fin 1)) braessDelayB
        (fun _ => 6) ![2, 2, 2]
      ∧ ∀ r : Fin 3, (∑ j, braessDelayB j (linkFlow braessIncidenceB ![2, 2, 2] j)
            * braessIncidenceB j r) = 92) := by sorry

end KellyStochasticNetworks
Source
Kelly & Yudovina, Stochastic Networks, CUP 2014, pp. 92-94 (PDF pp. 100-102), section 4.2.1 and Figures 4.3, 4.4a, 4.4b: 'Let us fix the total flow from S to N at six cars per unit time. Figure 4.4a shows how the cars will distribute themselves. Note that all routes from S to N have the same total delay of 83 time units, so no driver has an incentive to switch route. In Figure 4.4b, we have introduced an extra road with its own delay function, and found the new distribution of traffic such that no driver has an incentive to switch route. Note that all routes again have the same total delay, but it is now 92 time units! That is, adding extra road capacity has increased everyone's delay.' 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