Proof of Theorem 3, p. 13 — for superadditive , , with equality if
ProvedCooperationGraphs.FairRule.restrict_removeLink_lecooperation-graphscooperative-gamesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be superadditive, i.e. for all disjoint nonempty . Let be a graph on and a link of . Then for every coalition ,
and the inequality is an equality if .
Breaking a link can only lower the worth of every coalition in the graph-restricted game, and leaves unchanged the worth of coalitions not containing the endpoint .
Formalization Note. The paper assumes a nonempty player set, stated as . The link and nonempty-coalition conditions come 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 `(v/g)_S ≥ (v/(g \ a,b))_S` for every
coalition `S`, with equality if `a ∉ S`. -/
theorem 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)
(S : Finset (Fin n)) (hS : S.Nonempty) :
restrict v (removeLink g a b) S ≤ restrict v g S ∧
(a ∉ S → restrict v (removeLink g a b) S = restrict v g S) := 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.