Theorem 4, PDF p. 6 — the price of anarchy for two links with speeds s₁ ≤ s₂ ≤ φs₁ is at least R = 1 + s₂/(s₁ + s₂), and R ≤ φ with equality at s₂/s₁ = φ
ProvedWorstCaseEq.Speeds.theorem4_two_speeds_lower_boundConsider load balancing on two parallel links with speeds : each agent sends its traffic over one link, an agent on link carrying total traffic experiences delay , the social cost of a mixed profile is the expected maximum over the links of load divided by speed, and is the least such maximum over pure assignments. Let and suppose
Then:
- (Lower bound.) The price of anarchy is at least : there are finitely many agents with positive traffic and a Nash equilibrium of this game with and
- (Maximum value.) on this range.
- (Attained.) If then .
With identical links () the bound is , the lower bound of Theorem 1 for two links; the theorem shows that unequal speeds push the worst-case ratio up to the golden ratio.
Formalization Note "The price of anarchy is at least " is stated as the existence of an instance and an equilibrium whose social cost equals times a positive optimum, rather than through a supremum or a quotient (a quotient would take the junk value when ). The speed vector is ![s₁, s₂] (the paper's links 1, 2 are 0, 1). The ratio conditions are written and , equivalent because . Positive traffic is part of the model and is required of the witness. The social cost with speeds is not printed in the paper; the definition used (expected maximum of load divided by speed) is the one its cost computation uses.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_agt_games import Definitions.Def_WorstCaseEq_Speeds_Model
namespace WorstCaseEq.Speeds
theorem theorem4_two_speeds_lower_bound (s₁ s₂ : ℝ) (h₁ : 0 < s₁) (h₁₂ : s₁ ≤ s₂)
(hφ : s₂ ≤ Real.goldenRatio * s₁) :
(∃ (n : ℕ) (w : Fin n → ℝ) (p : Fin n → Fin 2 → ℝ),
(∀ i, 0 < w i) ∧ IsNash w ![s₁, s₂] p ∧ 0 < opt w ![s₁, s₂] ∧
socialCost w ![s₁, s₂] p = (1 + s₂ / (s₁ + s₂)) * opt w ![s₁, s₂]) ∧
1 + s₂ / (s₁ + s₂) ≤ Real.goldenRatio ∧
(s₂ = Real.goldenRatio * s₁ → 1 + s₂ / (s₁ + s₂) = Real.goldenRatio) := by sorry
end WorstCaseEq.Speeds
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.