Braess's paradox: adding a road raises the equilibrium delay from 83 to 92
ProvedKellyStochasticNetworks.braess_paradoxCars 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: and , each with delay when carrying flow , and and , each with delay . Two routes are available, and .
- Before. Splitting the traffic evenly, three cars per unit time on each route, is a Wardrop equilibrium, and every route has total delay
- After. Add one more road, , with delay . A third route 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
Adding road capacity raised every driver's delay, from to . 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 rather than all equal, which is why the delay rises: the two roads each carry four cars instead of three.
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop
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 KellyStochasticNetworksConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.