Theorem 6.1, proof — for efficient ψ, (6.3) is solvable iff ψ is the Shapley value on every v_S (Hart–Mas-Colell, Theorem A)
ProvedMondererShapley.Participation.hart_mas_colell_stepcooperative-gamesgame-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1shapley-value
Let be an efficient solution and (so ). Then there is a function on the coalitions of with
if and only if is the Shapley value on , that is, for every coalition and every , where is the Shapley value of the restriction of to the player set .
This is the final step of the proof of Theorem 6.1, which the paper takes from Theorem A of Hart and Mas-Colell (1989): a game has a potential whose marginal contributions add up to the worth of every coalition, and those marginal contributions are the Shapley value.
Formalization Note Since , ; the page's is kept on the left. is ψ S v and is shapleyOn S v i. Efficiency is assumed for every coalition and every game, as in the paper.
Preamble
import Mathlib import Definitions.Def_MondererShapley_Participation_Solution import Definitions.Def_MondererShapley_Participation_shapleyOn
Formal statement
namespace MondererShapley.Participation
/-- Theorem 6.1, proof, last step (Hart--Mas-Colell 1989, Theorem A): for an efficient solution
`ψ` and a game `v` with `v ∅ = 0`, a function `P` on coalitions with
`P(S) − P(S∖{i}) = ψ(v_{S∪{i}})(i)` for all `S` and `i ∈ S` exists iff `ψ` is the Shapley value
on every subgame `v_S`. -/
theorem hart_mas_colell_step {ι : Type*} [DecidableEq ι] (ψ : Solution ι) (hψ : IsEfficient ψ)
(v : Finset ι → ℝ) (hv : v ∅ = 0) :
(∃ P : Finset ι → ℝ, ∀ S : Finset ι, ∀ i ∈ S, P S - P (S \ {i}) = ψ (S ∪ {i}) v i) ↔
∀ S : Finset ι, ∀ i ∈ S, ψ S v i = shapleyOn S v i := by sorry
end MondererShapley.Participation
Source
Monderer and Shapley, Potential Games, Games Econ. Behav. 14 (1996), p. 137 (PDF p. 14), proof of Theorem 6.1, last step (Hart and Mas-Colell 1989, Theorem A)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.