Proof of Theorem 3, PDF p. 5 — cost = Σ_i q_i w_i
ProvedWorstCaseEq.Identical.socialCost_eq_sum_contribLet agents with traffics choose among identical links according to a profile , and let be the social cost (4), the expected maximum link load. For each pure assignment take the lexicographically first link of maximum load, and let the contribution probability of agent be the probability that agent is on that link. Then
This identity, stated as evident in the proof of Theorem 3, rewrites the expected maximum as a weighted sum of per-agent probabilities, which is what makes the pairwise argument of that proof possible.
Formalization Note The identity holds outcome by outcome, so it is stated for every real array , without requiring the to be probability distributions. The tie-breaking rule (the lowest-indexed maximum link) is the paper's.
import Mathlib import Definitions.Def_agt_games import Definitions.Def_WorstCaseEq_Identical_Model
namespace WorstCaseEq.Identical
/-- Proof of Theorem 3, PDF p. 5: the social cost is `∑_i q_i w_i`, where `q_i` is the probability that
agent `i` is on the lexicographically first link of maximum load. -/
theorem socialCost_eq_sum_contrib {n m : ℕ} [NeZero m] (w : Fin n → ℝ) (p : Fin n → Fin m → ℝ) :
socialCost w p = ∑ i, contribProb w p i * w i := by sorry
end WorstCaseEq.Identical
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.