Proof of Theorem 4, PDF p. 6 — with w₁ = s₂, w₂ = s₁ on speeds s₁, s₂ > 0, opt = 1
ProvedWorstCaseEq.Speeds.instance_optload-balancingmakespanp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchy
Let be the speeds of two links and consider two agents with traffic and . The least makespan over all pure assignments of the two agents to the two links is
attained by placing agent 1 on link 2 and agent 2 on link 1.
This is the denominator of the ratio in Theorem 4.
Formalization Note The paper's proof has in force; the value holds for all positive speeds, so only positivity is assumed.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_WorstCaseEq_Speeds_Model
Formal statement
namespace WorstCaseEq.Speeds
theorem instance_opt (s₁ s₂ : ℝ) (h₁ : 0 < s₁) (h₂ : 0 < s₂) :
opt (instWeights s₁ s₂) (speeds s₁ s₂) = 1 := by sorry
end WorstCaseEq.Speeds
Source
Koutsoupias & Papadimitriou, Worst-case equilibria (journal version, 2009), PDF p. 6, proof of Theorem 4 ("and opt = 1")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.