Proof of Theorem 4, p. 11, (16) — equity holds iff is constant on components
ProvedCooperationGraphs.FairRule.equitable_iff_componentwisecooperation-graphscooperative-gamesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a function and a graph , write , the sum over strict subgraphs of . Then satisfies the equity condition (10),
if and only if, for every graph and every connected component , there is a number with
This characterization turns equity into a recursion in the number of links: is determined by the values on strict subgraphs up to one constant per component.
Formalization Note. The paper assumes a nonempty player set, stated as . is altSum Y g n; is quot univ g; links are g.Adj a b.
Preamble
import Mathlib import Definitions.Def_CooperationGraphs_FairRule_Basic
Formal statement
namespace CooperationGraphs.FairRule
open Finset
open scoped Classical
/-- Proof of Theorem 4, p. 11, (16): a rule `Y` satisfies the equity condition (10) iff for every
graph `g` and every component `S ∈ N/g` there is a number `d(S,g)` with
`Y_i(g) − t_i(g) = d(S,g)` for all `i ∈ S`. -/
theorem equitable_iff_componentwise {n : ℕ} (hn : 0 < n) (Y : Rule n) :
IsEquitable Y ↔ ∀ g : SimpleGraph (Fin n), ∀ S ∈ quot univ g,
∃ d : ℝ, ∀ i ∈ S, Y g i - altSum Y g i = d := by sorry
end CooperationGraphs.FairRule
Source
Myerson, Graphs and Cooperation in Games, Discussion Paper No. 246 (Sept. 1976), proof of Theorem 4, p. 11, (15)–(16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.