(6.3) — with P(ε_S) = Q(ε_S) + Σ_{i∈S} cⁱ, Q satisfies (6.2) iff P(ε_S) − P(ε_{S∖{i}}) = ψ(v_{S∪{i}})(i)
ProvedMondererShapley.Participation.eq_6_3game-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-games
Let be a solution, , a TU game and . Define on coalitions by
Then satisfies (6.2), i.e. for every and , if and only if
The change of variables removes the outside options from the condition, which is why Theorem 6.1 holds for every .
Formalization Note is a function on coalitions (Finset ι → ℝ), standing for the page's ; is a bijection onto . The defining relation of is the hypothesis hP.
Preamble
import Mathlib import Definitions.Def_MondererShapley_Participation_Solution import Definitions.Def_MondererShapley_Participation_profileOf
Formal statement
namespace MondererShapley.Participation
/-- (6.3): with `P(ε_S) = Q(ε_S) + ∑_{i∈S} cⁱ`, `Q` satisfies (6.2) iff `P` satisfies
`P(ε_S) − P(ε_{S∖{i}}) = ψ(v_{S∪{i}})(i)` for all `S ⊆ N` and every `i ∈ S`. -/
theorem eq_6_3 {ι : Type*} [DecidableEq ι] (ψ : Solution ι) (c : ι → ℝ)
(v : Finset ι → ℝ) (Q : (ι → Bool) → ℝ) (P : Finset ι → ℝ)
(hP : ∀ S : Finset ι, P S = Q (profileOf S) + ∑ i ∈ S, c i) :
(∀ S : Finset ι, ∀ i ∈ S,
Q (profileOf S) - Q (profileOf (S \ {i})) = ψ (S ∪ {i}) v i - c i) ↔
∀ S : Finset ι, ∀ i ∈ S, P S - P (S \ {i}) = ψ (S ∪ {i}) 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, (6.3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.