Proof of Theorem 3, PDF p. 5 — on two links, Σ_{k≠i} q_k w_k ≤ (3/2 − q_i) Σ_{k≠i} w_k at every equilibrium
ProvedWorstCaseEq.Identical.sum_contrib_leload-balancingnash-equilibriump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchy
Let agents with positive traffics share two identical links, let be a Nash equilibrium, and let be the contribution probability of agent (the probability that it is on the lexicographically first link of maximum load). Then for every agent ,
The proof of Theorem 3 obtains this by combining (7), the collision form of and the bound (6) for ; together with and it yields the bound.
Formalization Note The two links are indexed by Fin 2. Positive traffics are part of the paper's model.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_WorstCaseEq_Identical_Model
Formal statement
namespace WorstCaseEq.Identical
/-- Proof of Theorem 3, PDF p. 5: on two identical links, at every Nash equilibrium and for every agent
`i`, `∑_{k ≠ i} q_k w_k ≤ (3/2 - q_i) ∑_{k ≠ i} w_k`. -/
theorem sum_contrib_le {n : ℕ} (w : Fin n → ℝ) (hw : ∀ i, 0 < w i) (p : Fin n → Fin 2 → ℝ)
(hp : IsNash w p) :
∀ i, ∑ k ∈ Finset.univ.erase i, contribProb w p k * w k ≤
(3 / 2 - contribProb w p i) * ∑ k ∈ Finset.univ.erase i, w k := by sorry
end WorstCaseEq.Identical
Source
Koutsoupias & Papadimitriou, Worst-case equilibria (journal version, 2009), PDF p. 5, proof of Theorem 3, last display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.