Proof of Theorem 4, p. 11 — exists
ProvedCooperationGraphs.FairRule.exists_isGreatest_shiftcooperation-graphscooperative-gamesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a game in graph function form: for every embedded subgraph , i.e. every graph and connected component , the set is closed, comprehensive and a proper subset of . Then for every embedded subgraph and every vector , the maximum
exists.
This is what makes the recursion (18) of the proof of Theorem 4 well defined: the constant is the largest uniform shift of that remains feasible.
Formalization Note. The paper assumes a nonempty player set, stated as . "The maximum exists" is stated as the existence of a greatest element (IsGreatest) of the set; a greatest element is unique, which is the paper's "uniquely defined".
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, sentence after (17): for a game `w` in graph function form, an
embedded subgraph `(S, g)` and any `r ∈ ℝ^S`, the maximum of `{x | (x + r_i)_{i ∈ S} ∈ w(S,g)}`
exists. -/
theorem exists_isGreatest_shift {n : ℕ} (hn : 0 < n) (G : GraphFunctionGame n) (g : SimpleGraph (Fin n))
(S : Finset (Fin n)) (hS : S ∈ quot univ g) (r : ↥S → ℝ) :
∃ x : ℝ, IsGreatest {x : ℝ | (fun i : ↥S => x + r i) ∈ G.w g S} x := by sorry
end CooperationGraphs.FairRule
Source
Myerson, Graphs and Cooperation in Games, Discussion Paper No. 246 (Sept. 1976), proof of Theorem 4, p. 11, sentence after (17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.