§2, PDF p. 3 — at a Nash equilibrium each agent uses only links minimizing c_i^j, and c_i = min_j c_i^j
ProvedWorstCaseEq.Identical.nash_support_minimizesbest-responsemixed-strategiesnash-equilibriump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let agents with traffics share identical links, and let be a Nash equilibrium. For an agent and a link let be the cost of agent when its traffic is assigned to link , as in (2). Then:
- agent assigns positive probability only to links minimizing : if then for every link ;
- the expected cost of agent equals the minimum link cost,
This is the support description of equilibria in §2 of the paper. It justifies the paper's double use of , as the expected cost and as , which is how Theorem 2 is proved.
Formalization Note No sign condition on the traffics is needed. The minimum over links uses .
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_WorstCaseEq_Identical_Model
Formal statement
namespace WorstCaseEq.Identical
/-- Support property, §2, PDF p. 3: at a Nash equilibrium agent `i` puts positive probability only on
links `j` minimizing `c_i^j`, and its expected cost equals `c_i = min_j c_i^j`. -/
theorem nash_support_minimizes {n m : ℕ} [NeZero m] (w : Fin n → ℝ) (p : Fin n → Fin m → ℝ)
(hp : IsNash w p) :
(∀ i j, 0 < p i j → ∀ j', linkCost w p i j ≤ linkCost w p i j') ∧
∀ i, expCost w p i = Finset.univ.inf' Finset.univ_nonempty (linkCost w p i) := by sorry
end WorstCaseEq.Identical
Source
Koutsoupias & Papadimitriou, Worst-case equilibria (journal version, 2009), PDF p. 3, §2, paragraph after (2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.