Proof of Theorem 2, pp. 12–13 — is if and if
ProvedCooperationGraphs.FairRule.carrier_identitycooperation-graphscooperative-gamesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1shapley-value
Let and let be a graph on . For a component define the game by
Let be the Shapley value. Then for any components ,
The set is a carrier of ; this identity is the carrier axiom of Shapley (1953) applied to , and with it gives the efficiency of on components.
Formalization Note. The paper assumes a nonempty player set, stated as . Two components of are either equal or disjoint, so the two cases are stated as if S = T then u^T_N else 0. is the platform's Supermodularity.Cooperative.ShapleyValue applied to with its value at set to ( in any case).
Preamble
import Mathlib import Definitions.Def_CooperationGraphs_FairRule_Basic
Formal statement
namespace CooperationGraphs.FairRule
open Finset
open scoped Classical
/-- Proof of Theorem 2, pp. 12–13 (carrier axiom): for `S, T ∈ N/g`,
`∑_{i ∈ S} φ_i(u^T) = u^T_N` if `S = T`, and `= 0` if `S ∩ T = ∅` (distinct components are
disjoint). -/
theorem carrier_identity {n : ℕ} (hn : 0 < n) (v : Game n) (g : SimpleGraph (Fin n))
(S T : Finset (Fin n)) (hS : S ∈ quot univ g) (hT : T ∈ quot univ g) :
∑ i ∈ S, shapley (uGame v g T) i = if S = T then uGame v g T univ else 0 := by sorry
end CooperationGraphs.FairRule
Source
Myerson, Graphs and Cooperation in Games, Discussion Paper No. 246 (Sept. 1976), proof of Theorem 2, pp. 12–13, display at the top of p. 13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.