§2, PDF p. 4 — opt ≥ max{w_i, Σ_i w_i/m}
ProvedWorstCaseEq.Identical.opt_ge_maxload-balancinglower-boundmakespanp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let agents with nonnegative traffics be assigned to identical links, and let be the least possible maximum link load over all assignments of agents to links. Then
These are the two elementary lower bounds on the optimum that the paper uses to bound the price of anarchy: some link carries agent , and the busiest link carries at least the average load. For any mixed profile the expected traffics satisfy , so the average load is also , which is how the page writes it.
Formalization Note The paper states the first bound for under the ordering ; the statement here gives it for every agent and assumes no ordering. Nonnegative traffics suffice.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_WorstCaseEq_Identical_Model
Formal statement
namespace WorstCaseEq.Identical
/-- PDF p. 4: the social optimum is at least the traffic of every single agent and at least the average
load `∑_i w_i / m`. -/
theorem opt_ge_max {n m : ℕ} [NeZero m] (w : Fin n → ℝ) (hw : ∀ i, 0 ≤ w i) :
(∀ i, w i ≤ opt m w) ∧ (∑ i, w i) / m ≤ opt m w := by sorry
end WorstCaseEq.Identical
Source
Koutsoupias & Papadimitriou, Worst-case equilibria (journal version, 2009), PDF p. 4, last paragraph of §2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.