Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 8 (p. 24) — a feasible vector outside the core is dominated by a core point

Proved
CoresConvexGames.Stability.dominated_by_core_of_not_mem_core

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-gamecooperative-gamep2o-batch-p100ap2o-gran-per-chapterp2o-plan-paperp2o-v1stable-set

Let N={1,…,n}N=\{1,\dots,n\}N={1,…,n} be a finite set of players and v:2N→Rv:2^N\to\mathbb Rv:2N→R a game, i.e. a set function with v(∅)=0v(\emptyset)=0v(∅)=0. For a payoff vector a∈RNa\in\mathbb R^Na∈RN and a coalition S⊆NS\subseteq NS⊆N write a(S)=∑i∈Saia(S)=\sum_{i\in S}a_ia(S)=∑i∈S​ai​. Suppose vvv is convex: v(S)+v(T)≤v(S∪T)+v(S∩T)v(S)+v(T)\le v(S\cup T)+v(S\cap T)v(S)+v(T)≤v(S∪T)+v(S∩T) for all S,TS,TS,T. Let CCC be the core (a(N)=v(N)a(N)=v(N)a(N)=v(N) and a(S)≥v(S)a(S)\ge v(S)a(S)≥v(S) for all SSS), call bbb feasible if b(N)≤v(N)b(N)\le v(N)b(N)≤v(N), and say that aaa dominates bbb if some nonempty SSS has a(S)≤v(S)a(S)\le v(S)a(S)≤v(S) and ai>bia_i>b_iai​>bi​ for all i∈Si\in Si∈S. Then every feasible b∉Cb\notin Cb∈/C is dominated by an element of CCC:

b(N)≤v(N), b∉C ⟹ ∃ a∈C: a dominates b.b(N)\le v(N),\ b\notin C\ \Longrightarrow\ \exists\,a\in C:\ a \text{ dominates } b .b(N)≤v(N), b∈/C ⟹ ∃a∈C: a dominates b.

This is the external stability of the core of a convex game, the substantive half of Theorem 8.

Formalization Note Players are Fin n (a relabelling of Shapley's arbitrary finite NNN), a game is f : Finset (Fin n) → ℝ, and the core is the published Supermodularity.Cooperative.Core Finset.univ f. The paper's proof starts from a regular configuration; the hypothesis here is convexity, which is the hypothesis of Theorem 8 whose proof this is (regularity follows by Theorem 5, and the last step of the proof uses the convexity inequality directly).

Preamble
import Mathlib
import Definitions.Def_Supermodularity_Cooperative_IsConvexGame
import Definitions.Def_Supermodularity_Cooperative_Core
import Definitions.Def_CoresConvexGames_Stability_IsFeasible
import Definitions.Def_CoresConvexGames_Stability_Dominates
Formal statement
namespace CoresConvexGames.Stability

open Supermodularity.Cooperative

/-- Shapley (1971), p. 24, §4.3, proof of Theorem 8, first paragraph: in a convex game,
every feasible payoff vector outside the core is dominated by an element of the core. -/
theorem dominated_by_core_of_not_mem_core {n : ℕ} (f : Finset (Fin n) → ℝ)
    (hf : IsConvexGame f) (b : Fin n → ℝ) (hb : IsFeasible f b)
    (hbC : b ∉ Core Finset.univ f) :
    ∃ a ∈ Core Finset.univ f, Dominates f a b := by sorry

end CoresConvexGames.Stability
Source
Shapley, Cores of Convex Games, Int. J. Game Theory 1, 1971, https://doi.org/10.1007/BF01753431, p. 24, §4.3, proof of Theorem 8, first paragraph (first two sentences)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Fix n∈Nn \in \mathbb{N}n∈N, N={0,…,n−1}N = \{0, \dots, n-1\}N={0,…,n−1}, a game fff (real-valued on subsets of NNN) and a vector b∈Rnb \in \mathbb{R}^nb∈Rn.

Hypotheses.

  • IsConvexGame⁡(f)\operatorname{IsConvexGame}(f)IsConvexGame(f) holds. This is an external definition whose body is not shown.
  • bbb is feasible: ∑i∈Nbi≤f(N)\sum_{i \in N} b_i \le f(N)∑i∈N​bi​≤f(N).
  • b∉Core⁡(N,f)b \notin \operatorname{Core}(N, f)b∈/Core(N,f). This is also an external definition whose body is not shown.

There is no hypothesis f(∅)=0f(\emptyset) = 0f(∅)=0, unless one is built into IsConvexGame⁡\operatorname{IsConvexGame}IsConvexGame.

Conclusion. There exists a∈Core⁡(N,f)a \in \operatorname{Core}(N, f)a∈Core(N,f) that dominates bbb. That is, there is a nonempty coalition S⊆NS \subseteq NS⊆N such that

∑i∈Sai≤f(S)andbi<ai  for all i∈S.\sum_{i \in S} a_i \le f(S) \qquad \text{and} \qquad b_i < a_i \ \text{ for all } i \in S.i∈S∑​ai​≤f(S)andbi​<ai​  for all i∈S.

In particular, the conclusion implies that the core is nonempty whenever such a bbb exists.

Degenerate cases: when n=0n = 0n=0 there is no nonempty coalition, so the conclusion cannot hold. The statement then says the hypotheses can never all be met: it forbids a convex game on the empty player set whose single vector is feasible (0≤f(∅)0 \le f(\emptyset)0≤f(∅)) but not in the core. Whether that matches the unseen definitions of Core⁡\operatorname{Core}Core and IsConvexGame⁡\operatorname{IsConvexGame}IsConvexGame cannot be told from the code given.

Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me