Lemma B.1 — congestion payoffs decomposed by the number of users of each facility
ProvedMondererShapley.Congestion.lemma_B_1Let be a congestion game with players , facilities , strategy sets and facility payoffs , and payoffs as in (3.1). For and write , , and , . For and write . For every define by .
Then for every and every ,
The -th term is evaluated on the set of facilities used by player together with exactly other players, namely . The lemma rewrites a congestion game as a sum of "level" contributions, which is the form in which the proof of Theorem 3.2 builds a congestion game with prescribed payoffs.
Formalization Note. The page prints ; is the number of facilities, and the lemma "follows from (3.1)" only with , so the misprint is corrected. The "" is read as the general term above, whose cases are the printed ones; is Fintype.card ι. The congestion game is the published model with = G.latency j r.
import Mathlib import Definitions.Def_CongestionPoA_AsymSum_Model import Definitions.Def_MondererShapley_Congestion_congestionPayoff open CongestionPoA.AsymSum
namespace MondererShapley.Congestion
/-- Monderer and Shapley (1996), p. 139, Lemma B.1, (B.1): in a congestion game, with
`x^r(j) = c_j(r)`, every payoff decomposes by the number of users of each facility:
`vⁱ(A) = x¹(A(i) ∩ A(−i)^c) + x²(∪_{k≠i}[A(i) ∩ A(k) ∩ A(−{i,k})^c]) + ⋯ + xⁿ(∩_{k∈N} A(k))`,
where `A(S) = ∪_{k∈S} Aᵏ` and `A(−S) = A(Sᶜ)`.
**Formalization Note.** The printed `x^r(j) = c_j(m)` is a misprint for `c_j(r)`. The `r`-th term is
read as `x^r(∪_{S ∋ i, |S| = r} [∩_{k∈S} A(k) ∩ A(−S)^c])`, whose cases `r = 1, 2, n` are the printed
ones; `n = Fintype.card ι`. -/
theorem lemma_B_1 {ι M : Type*} [Fintype ι] [DecidableEq ι] [Fintype M] [DecidableEq M]
(G : CongestionGame ι M) (i : ι) (A : ∀ k, ↥(G.strategies k)) :
congestionPayoff G i A =
∑ r ∈ Finset.Icc 1 (Fintype.card ι),
∑ j ∈ Finset.univ.filter (fun j : M => ∃ S : Finset ι, i ∈ S ∧ S.card = r ∧
(∀ k ∈ S, j ∈ (A k : Finset M)) ∧ ∀ k ∉ S, j ∉ (A k : Finset M)),
G.latency j r := by sorry
end MondererShapley.Congestion
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.