Proof of Theorem 4, PDF p. 6 — with w₁ = s₂, w₂ = s₁ on speeds s₁ ≤ s₂ ≤ φs₁, the stated mixed profile is a Nash equilibrium
ProvedWorstCaseEq.Speeds.instance_isNashgolden-ratiomixed-strategiesnash-equilibriump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchy
Let , where . Consider two links with speeds and two agents with traffic and , with no other traffic on the links. Let agent choose link 1 with probability and link 2 with probability , where
Then this mixed profile is a Nash equilibrium: both and are probability distributions, and neither agent can lower its expected delay by changing its strategy unilaterally.
This is the equilibrium whose social cost gives the lower bound of Theorem 4.
Formalization Note The paper's agents 1, 2 and links 1, 2 are 0, 1; the weight vector is ![s₂, s₁] and the speed vector ![s₁, s₂]. The speeds enter only through the hypotheses; follows from .
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_WorstCaseEq_Speeds_Model
Formal statement
namespace WorstCaseEq.Speeds
theorem instance_isNash (s₁ s₂ : ℝ) (h₁ : 0 < s₁) (h₁₂ : s₁ ≤ s₂)
(hφ : s₂ ≤ Real.goldenRatio * s₁) :
IsNash (instWeights s₁ s₂) (speeds s₁ s₂) (instProfile s₁ s₂) := by sorry
end WorstCaseEq.Speeds
Source
Koutsoupias & Papadimitriou, Worst-case equilibria (journal version, 2009), PDF p. 6, proof of Theorem 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.