Figure 3 — Pigou's example: Nash cost , optimal cost , so
ProvedSelfishRouting.Linear.figure_3_pigoup2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pigou-exampleprice-of-anarchyselfish-routing
The network of Figure 3 has one source–destination pair joined by two parallel links: the upper link has latency and the lower link has latency ; the rate is . Then
- the flow , which puts the entire unit on the lower link, is at Nash equilibrium, and its cost is ;
- the flow , which spreads the flow evenly over the two links, is optimal, and its cost is .
Hence in this instance, so the constant of Theorem 4.5 cannot be lowered.
Formalization Note Route is the upper link and route the lower link; the incidence is the identity, there is one commodity, and the latencies are the linear latencies with , .
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
/-- Figure 3 (pp. 11–12): two parallel links with latencies `ℓ(x) = 1` (route 0) and
`ℓ(x) = x` (route 1), one commodity, rate 1. The flow `(0, 1)` is at Nash equilibrium with
cost 1, and the flow `(1/2, 1/2)` is optimal with cost 3/4, so `ρ = 4/3`. -/
theorem figure_3_pigou :
SelfishRouting.Bicriteria.IsNashFlow (fun j r : Fin 2 => if j = r then (1 : ℝ) else 0) (fun _ : Fin 2 => (0 : Fin 1))
(linLatency ![0, 1] ![1, 0]) (fun _ => 1) ![0, 1] ∧
SelfishRouting.Bicriteria.cost (fun j r : Fin 2 => if j = r then (1 : ℝ) else 0) (linLatency ![0, 1] ![1, 0])
![0, 1] = 1 ∧
IsOptimalFlow (fun j r : Fin 2 => if j = r then (1 : ℝ) else 0)
(fun _ : Fin 2 => (0 : Fin 1)) (linLatency ![0, 1] ![1, 0]) (fun _ => 1) ![1 / 2, 1 / 2] ∧
SelfishRouting.Bicriteria.cost (fun j r : Fin 2 => if j = r then (1 : ℝ) else 0) (linLatency ![0, 1] ![1, 0])
![1 / 2, 1 / 2] = 3 / 4 := 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, pp. 11–12, Figure 3 and the paragraph introducing it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.