PDF pp. 3, 6 — at a Nash equilibrium with speeds, each agent uses only links minimizing c_i^j, and c_i = min_j c_i^j
ProvedWorstCaseEq.Speeds.nash_support_minimizesbest-responseload-balancingnash-equilibriump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1support
Consider agents with traffic on parallel links with speeds , and let be a Nash equilibrium. Write for the cost to agent of placing its traffic on link (see (8)) and for the expected cost of agent at . Then:
- agent assigns positive probability only to links that minimize : if then for every link ;
- the expected cost of agent is the minimum link cost,
This is the support characterization of equilibria on which the closed-form description of all Nash equilibria ((3) and (9)) rests.
Formalization Note The paper states this for identical links in §2 (PDF p. 3) and applies it with speeds in §3 ("We can estimate all Nash equilibria again", PDF p. 6). The statement holds for arbitrary real speeds and traffic, so no positivity is assumed; at least one link is required for the minimum to exist.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_WorstCaseEq_Speeds_Model
Formal statement
namespace WorstCaseEq.Speeds
theorem nash_support_minimizes {n m : ℕ} [NeZero m] (w : Fin n → ℝ) (s : Fin m → ℝ)
(p : Fin n → Fin m → ℝ) (hp : IsNash w s p) :
(∀ i j, 0 < p i j → ∀ j', linkCost w s p i j ≤ linkCost w s p i j') ∧
∀ i, expCost w s p i = Finset.univ.inf' Finset.univ_nonempty (linkCost w s p i) := by sorry
end WorstCaseEq.Speeds
Source
Koutsoupias & Papadimitriou, Worst-case equilibria (journal version, 2009), PDF p. 3 (§2, support property and c_i = min_j c_i^j); PDF p. 6 (Links with different capacities)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.