Proof of Theorem 3, p. 13 — for superadditive ,
ProvedCooperationGraphs.FairRule.shapley_restrict_removeLink_lecooperation-graphscooperative-gamesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1shapley-value
Let be superadditive, let be the Shapley value, let be a graph on and a link of . Then
With Theorem 2 this is exactly total stability of the fair allocation rule: a player never loses by keeping a link.
Formalization Note. The paper assumes a nonempty player set, stated as . is the platform's Supermodularity.Cooperative.ShapleyValue applied after setting the game's value at to . The link condition comes from the paper's context.
Preamble
import Mathlib import Definitions.Def_CooperationGraphs_FairRule_Basic
Formal statement
namespace CooperationGraphs.FairRule
open Finset
open scoped Classical
/-- Proof of Theorem 3, p. 13: if `v` is superadditive then `φ_a(v/g) − φ_a(v/(g \ a,b)) ≥ 0`. -/
theorem shapley_restrict_removeLink_le {n : ℕ} (hn : 0 < n) (v : Game n) (hv : IsSuperadditive v)
(g : SimpleGraph (Fin n)) (a b : Fin n) (hab : g.Adj a b) :
shapley (restrict v (removeLink g a b)) a ≤ shapley (restrict v g) a := by sorry
end CooperationGraphs.FairRule
Source
Myerson, Graphs and Cooperation in Games, Discussion Paper No. 246 (Sept. 1976), proof of Theorem 3 (headed "PROOF OF THEOREM 4." in the typescript), p. 13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.