Proof of Theorem 3, p. 13 — refines , with equality if
ProvedCooperationGraphs.FairRule.quot_removeLink_refinescooperation-graphscooperative-gamesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a graph on , a link of and . Then the partition refines as a partition of : every block of is contained in a block of . Moreover, if , then
Removing a link can only split the connected pieces of a coalition, and cannot affect a coalition that does not contain one of its endpoints.
Formalization Note. The paper assumes a nonempty player set, stated as . Refinement is stated as: every block of satisfies for some block of (both are partitions of ). 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: `S/(g \ a,b)` refines `S/g` as a partition of `S`, and
`S/(g \ a,b) = S/g` if `a ∉ S`. -/
theorem quot_removeLink_refines {n : ℕ} (hn : 0 < n) (g : SimpleGraph (Fin n)) (a b : Fin n)
(hab : g.Adj a b) (S : Finset (Fin n)) (hS : S.Nonempty) :
(∀ B ∈ quot S (removeLink g a b), ∃ C ∈ quot S g, B ⊆ C) ∧
(a ∉ S → quot S (removeLink g a b) = quot S g) := 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.