(2), PDF p. 3 — c_i^j = w_i + Σ_{k≠i} p_k^j w_k = M^j + (1 − p_i^j) w_i
ProvedWorstCaseEq.Identical.eq2_linkCostLet agents with traffics share identical links, and let be a mixed profile: each is a probability distribution on the links. Write for the expected traffic on link .
Fix an agent and a link , and suppose agent sends its traffic on link with certainty while every other agent keeps its mixed strategy. Then the expected cost of agent (the expected traffic on link ) is
This is equation (2) of the paper. It turns the expected cost of a pure deviation into a closed form that is linear in the other agents' probabilities, and it is the starting point of the equilibrium characterization and of Theorem 2.
Formalization Note The first equality is stated for the expected cost in the profile in which agent 's strategy is replaced by the point mass on ; the second equality is an algebraic identity. No sign condition on the traffics is needed.
import Mathlib import Definitions.Def_agt_games import Definitions.Def_WorstCaseEq_Identical_Model
namespace WorstCaseEq.Identical
/-- (2), PDF p. 3: for a mixed profile `p`, the expected cost of agent `i` when its own traffic is
assigned to link `j` (the others keeping their lotteries) is `c_i^j = w_i + ∑_{k ≠ i} p_k^j w_k`, and
`c_i^j = M^j + (1 - p_i^j) w_i`. -/
theorem eq2_linkCost {n m : ℕ} (w : Fin n → ℝ) (p : Fin n → Fin m → ℝ)
(hp : AGT.IsMixedProfile (S := fun _ : Fin n => Fin m) p) :
∀ i j, -AGT.expectedPayoff (S := fun _ : Fin n => Fin m) (payoff w)
(Function.update p i (pureLottery j)) i = linkCost w p i j ∧
linkCost w p i j = expTraffic w p j + (1 - p i j) * w i := by sorry
end WorstCaseEq.Identical
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.