Proof of Theorem 2, p. 13 — on components
ProvedCooperationGraphs.FairRule.shapley_restrict_sum_componentcooperation-graphscooperative-gamesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1shapley-value
Let , let be a graph on and let be the Shapley value. For every connected component ,
Since for a component of , the right-hand side is , so the rule satisfies the efficiency condition (7).
Formalization Note. The paper assumes a nonempty player set, stated as . is the platform's Supermodularity.Cooperative.ShapleyValue applied to with its value at set to ; already, since is empty.
Preamble
import Mathlib import Definitions.Def_CooperationGraphs_FairRule_Basic
Formal statement
namespace CooperationGraphs.FairRule
open Finset
open scoped Classical
/-- Proof of Theorem 2, p. 13: for every graph `g` and component `S ∈ N/g`,
`∑_{i ∈ S} φ_i(v/g) = ∑_{R ∈ S/g} v_R`. -/
theorem shapley_restrict_sum_component {n : ℕ} (hn : 0 < n) (v : Game n) (g : SimpleGraph (Fin n))
(S : Finset (Fin n)) (hS : S ∈ quot univ g) :
∑ i ∈ S, shapley (restrict v g) i = ∑ R ∈ quot S g, v R := by sorry
end CooperationGraphs.FairRule
Source
Myerson, Graphs and Cooperation in Games, Discussion Paper No. 246 (Sept. 1976), proof of Theorem 2, p. 13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.