Proof of Theorem 2, p. 12 —
ProvedCooperationGraphs.FairRule.quot_eq_biUnioncooperation-graphscooperative-gamesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a graph on and a coalition. Any two players connected in by are also connected in by , so the partition of into -connected pieces is obtained by cutting each component of down to :
Consequently , the decomposition of the graph-restricted game used in the proof of Theorem 2.
Formalization Note. The paper assumes a nonempty player set, stated as . Partitions are Finset (Finset (Fin n)) and the union is Finset.biUnion. The paper takes , so is required to be nonempty.
Preamble
import Mathlib import Definitions.Def_CooperationGraphs_FairRule_Basic
Formal statement
namespace CooperationGraphs.FairRule
open Finset
open scoped Classical
/-- Proof of Theorem 2, p. 12: for every graph `g` and coalition `T`,
`T/g = ⋃_{S ∈ N/g} (T ∩ S)/g`. -/
theorem quot_eq_biUnion {n : ℕ} (hn : 0 < n) (g : SimpleGraph (Fin n))
(T : Finset (Fin n)) (hT : T.Nonempty) :
quot T g = (quot univ g).biUnion (fun S => quot (T ∩ S) g) := by sorry
end CooperationGraphs.FairRule
Source
Myerson, Graphs and Cooperation in Games, Discussion Paper No. 246 (Sept. 1976), proof of Theorem 2, p. 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.