Proof of Theorem 3, PDF p. 5 — c_i = w_i + Σ_{k≠i} t_ik w_k
ProvedWorstCaseEq.Identical.expCost_eq_collisionload-balancingmixed-strategiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let agents with traffics choose among identical links according to a mixed profile , and let be the expected cost of agent , the expected traffic on the link it picks. With the collision probabilities ,
since the expected contribution of agent to the link of agent is .
In the proof of Theorem 3 this identity connects the collision probabilities of (7) with the bound (6) on .
Formalization Note The identity holds for every mixed profile, not only at an equilibrium as the page uses it.
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: the expected cost of agent `i` is `c_i = w_i + ∑_{k ≠ i} t_ik w_k`. -/
theorem expCost_eq_collision {n m : ℕ} (w : Fin n → ℝ) (p : Fin n → Fin m → ℝ)
(hp : AGT.IsMixedProfile (S := fun _ : Fin n => Fin m) p) :
∀ i, expCost w p i = w i + ∑ k ∈ Finset.univ.erase i, collisionProb p i k * w k := by sorry
end WorstCaseEq.Identical
Source
Koutsoupias & Papadimitriou, Worst-case equilibria (journal version, 2009), PDF p. 5, proof of Theorem 3, display after (7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.