Proof of Theorem 4, PDF p. 6 — the instance's social cost is (s₁ + 2s₂)/(s₁ + s₂)
ProvedWorstCaseEq.Speeds.instance_socialCostmakespanp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchysocial-cost
Let . On two links with speeds , let two agents with traffic , play the mixed profile
Then the expected makespan (the expected maximum over the two links of load divided by speed) is
Together with this gives the ratio of Theorem 4.
Formalization Note The identity is algebraic and does not need (outside that range the "profile" is not a probability distribution, but the expected-makespan sum is still defined). The hypothesis decides which link carries the maximum when the agents split ().
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_WorstCaseEq_Speeds_Model
Formal statement
namespace WorstCaseEq.Speeds
theorem instance_socialCost (s₁ s₂ : ℝ) (h₁ : 0 < s₁) (h₁₂ : s₁ ≤ s₂) :
socialCost (instWeights s₁ s₂) (speeds s₁ s₂) (instProfile s₁ s₂)
= (s₁ + 2 * s₂) / (s₁ + s₂) := by sorry
end WorstCaseEq.Speeds
Source
Koutsoupias & Papadimitriou, Worst-case equilibria (journal version, 2009), PDF p. 6, proof of Theorem 4 (cost computation)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.