(7), PDF p. 5 — q_i + q_k ≤ 1 + t_ik for distinct agents i, k
ProvedWorstCaseEq.Identical.eq7_contrib_add_leLet agents with traffics choose among identical links according to a mixed profile , and let be the contribution probability of agent (the probability that it is on the lexicographically first link of maximum load). For two distinct agents let be their collision probability, the probability that both are on the same link. Then
Both agents can contribute to the social cost in the same outcome only if they collide. Inequality (7) is the pairwise bound at the heart of the proof of Theorem 3.
Formalization Note The page prints the inequality as ""; the index is a typo for , and the statement here uses . The page's "both agents and " means distinct agents, and is a hypothesis: for the inequality can fail.
import Mathlib import Definitions.Def_agt_games import Definitions.Def_WorstCaseEq_Identical_Model
namespace WorstCaseEq.Identical
/-- (7), proof of Theorem 3, PDF p. 5: two distinct agents `i`, `k` can both contribute to the social
cost only if they collide, so `q_i + q_k ≤ 1 + t_ik`. -/
theorem eq7_contrib_add_le {n m : ℕ} [NeZero m] (w : Fin n → ℝ) (p : Fin n → Fin m → ℝ)
(hp : AGT.IsMixedProfile (S := fun _ : Fin n => Fin m) p) :
∀ i k, i ≠ k → contribProb w p i + contribProb w p k ≤ 1 + collisionProb p i k := 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.