Proof of Theorem 4, p. 11, (17) — given (16), efficiency (14) holds iff is the largest feasible shift
ProvedCooperationGraphs.FairRule.efficientGF_iff_isGreatestcooperation-graphscooperative-gamesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a game in graph function form and let satisfy (16) with numbers : for every graph and component , for all , where . Then satisfies the efficiency condition (14), for every and , if and only if
Together with (16), this reduces the fair allocation rule of a graph function game to the explicit recursion (18).
Formalization Note. The paper assumes a nonempty player set, stated as . The paper's (17) writes under the index ; we read , as in (18b). " equals the maximum" is stated as " is the greatest element of the set" (IsGreatest). The numbers are an arbitrary function of , read only on embedded subgraphs. is the topological frontier in .
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, (17): if `Y` satisfies (16) with numbers `d(S,g)`, then `Y` satisfies
the efficiency condition (14) iff for every embedded subgraph `(S, g)`, `d(S,g)` is the maximum of
`{x | (x + t_i(g))_{i ∈ S} ∈ w(S,g)}`. -/
theorem efficientGF_iff_isGreatest {n : ℕ} (hn : 0 < n) (G : GraphFunctionGame n) (Y : Rule n)
(d : SimpleGraph (Fin n) → Finset (Fin n) → ℝ)
(hd : ∀ g : SimpleGraph (Fin n), ∀ S ∈ quot univ g, ∀ i ∈ S, Y g i - altSum Y g i = d g S) :
IsEfficientGF G Y ↔
∀ g : SimpleGraph (Fin n), ∀ S ∈ quot univ g,
IsGreatest {x : ℝ | (fun i : ↥S => x + altSum Y g i) ∈ G.w g S} (d g S) := by sorry
end CooperationGraphs.FairRule
Source
Myerson, Graphs and Cooperation in Games, Discussion Paper No. 246 (Sept. 1976), proof of Theorem 4, p. 11, (17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.