Theorem 2, PDF pp. 4–5 — at every Nash equilibrium on m identical links, c_i ≤ Σ_k w_k/m + ((m − 1)/m) w_i ≤ (2 − 1/m) opt
ProvedWorstCaseEq.Identical.theorem2_expected_cost_boundapproximation-ratioload-balancingnash-equilibriump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let agents with positive traffics share identical links, let be a Nash equilibrium, and let be the expected cost of agent at (the expected traffic on the link it picks). Let be the least maximum link load over all assignments of agents to links. Then for every agent ,
and
This is Theorem 2 of the paper: the expected cost seen by every individual agent at any equilibrium is within a factor of the optimum, for any number of agents and links. The sharper bound (6) is used, for , in the proof of Theorem 3.
Formalization Note Positive traffics are part of the paper's model. Both conclusions are stated for every agent.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_WorstCaseEq_Identical_Model
Formal statement
namespace WorstCaseEq.Identical
/-- Theorem 2 with (6), PDF pp. 4–5: on `m` identical links, at every Nash equilibrium the expected cost
of each agent `i` is at most `∑_k w_k / m + ((m - 1)/m) w_i`, and at most `(2 - 1/m)` times the optimum. -/
theorem theorem2_expected_cost_bound {n m : ℕ} [NeZero m] (w : Fin n → ℝ) (hw : ∀ i, 0 < w i)
(p : Fin n → Fin m → ℝ) (hp : IsNash w p) :
∀ i, expCost w p i ≤ (∑ k, w k) / m + (((m : ℝ) - 1) / m) * w i ∧
expCost w p i ≤ (2 - 1 / (m : ℝ)) * opt m w := by sorry
end WorstCaseEq.Identical
Source
Koutsoupias & Papadimitriou, Worst-case equilibria (journal version, 2009), PDF pp. 4–5, Theorem 2, (6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.