three_distant_convex_excess_marginal_eq_sdiff_singleton
Let N be a finite player type with decidable equality, and let v : Finset N → ℝ be a 3-distant convex cooperative game. For any coalition S : Finset N and any player i ∈ S, if v S - v (S \ {i}) > v Finset.univ - v (Finset.univ \ {i}), then there exists j ∈ Finset.univ \ {i} such that S = Finset.univ \ {j}.
Statement
theorem three_distant_convex_excess_marginal_eq_sdiff_singleton {N : Type*} [DecidableEq N] [Fintype N] {v : Finset N → ℝ} (hv : is_three_distant_convex v) (S : Finset N) (i : N) (hi : i ∈ S) (h_excess : v S - v (S \ {i}) > v Finset.univ - v (Finset.univ \ {i})) : ∃ j ∈ Finset.univ \ {i}, S = Finset.univ \ {j}
- Formalizes
- arXiv:2611.07572 Lemma 8
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_three_distant_convexA cooperative game v on a finite set of players is 3-distant convex if v(S) + v(T) ≤ v(S ∪ T) + v(S ∩ T) for all coalitions S and T whose…
Read back from the Lean
Let $N$ be a finite type with decidable equality, and let $v : \mathrm{Finset}(N) \to \mathbb{R}$ be a function satisfying is_three_distant_convex. Let $S \subseteq N$ be a finset and $i \in N$ such that $i \in S$. If the marginal contribution of $i$ to $S \setminus \{i\}$ is strictly greater than the marginal contribution of $i$ to $N \setminus \{i\}$ (that is, $v(S) - v(S \setminus \{i\}) > v(N) - v(N \setminus \{i\})$), then there exists $j \in N$ with $j \neq i$ such that $S = N \setminus \{j\}$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by bounding the size of the coalition S. Setting T = N \\ {i}, the union is S ∪ T = N and the intersection is S ∩ T = S \\ {i}. If the symmetric difference S ∆ T had size at least 3, the 3-distant convexity of v would imply that the marginal contribution of i in S is at most its marginal contribution in N, contradicting the assumed excess marginal contribution. Since |S ∆ T| = |N| - |S| + 1, this forces |S| ≥ |N| - 1; since S cannot be the grand coalition N, |S| must equal |N| - 1. Therefore, S is the complement of a singleton {j}, where j ≠ i because i ∈ S.
For any coalition S containing player i, the symmetric difference of S and N \\ {i} equals {i} ∪ (N \\ S).
By extensionality, an element x belongs to S ∆ (N \\ {i}) if and only if it belongs to S but not N \\ {i}, or to N \\ {i} but not S. Case splitting on whether x = i: if x = i, then x ∈ S (since i ∈ S) and x ∉ N \\ {i}, so x is in both sets; if x ≠ i, then x ∈ N \\ {i}, so x is in the symmetric difference if and only if x ∉ S, which matches x ∈ N \\ S.
uses
Finset.mem_symmDiff,Finset.mem_insert,Finset.mem_sdiff,Finset.mem_univ,Finset.mem_singleton,true_and,not_notprivate lemma three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_symm {N : Type*} [DecidableEq N] [Fintype N] (S : Finset N) (i : N) (hi : i ∈ S) : symmDiff S (Finset.univ \ {i}) = insert i (Finset.univ \ S) := by ext x simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_sdiff, Finset.mem_univ, Finset.mem_singleton, true_and, not_not] by_cases h : x = i · subst h; simp [hi] · simp [h]
For any coalition S containing player i, S ∪ (N \\ {i}) equals the grand coalition N.
By extensionality, every player x belongs to S ∪ (N \\ {i}). Case splitting on whether x = i: if x = i, then x ∈ S because i ∈ S; if x ≠ i, then x ∈ N \\ {i}. In either case, x belongs to the union.
uses
Finset.mem_union,Finset.mem_sdiff,Finset.mem_univ,Finset.mem_singleton,true_andprivate lemma three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_union {N : Type*} [DecidableEq N] [Fintype N] (S : Finset N) (i : N) (hi : i ∈ S) : S ∪ (Finset.univ \ {i}) = Finset.univ := by ext x simp only [Finset.mem_union, Finset.mem_sdiff, Finset.mem_univ, Finset.mem_singleton, true_and] by_cases h : x = i <;> simp [h, hi]
The intersection S ∩ (N \\ {i}) equals S \\ {i}.
An element x belongs to S ∩ (N \\ {i}) if and only if x ∈ S and x ≠ i, which is the definition of S \\ {i}.
uses
Finset.mem_inter,Finset.mem_sdiffprivate lemma three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_inter {N : Type*} [DecidableEq N] [Fintype N] (S : Finset N) (i : N) : S ∩ (Finset.univ \ {i}) = S \ {i} := by ext x simp [Finset.mem_inter, Finset.mem_sdiff]
The union S ∪ (N \\ {i}) is N, the intersection is S \\ {i}, and the symmetric difference S ∆ (N \\ {i}) has cardinality |N| - |S| + 1.
The auxiliary lemmas establish the union and intersection. Furthermore, the symmetric difference is {i} ∪ (N \\ S). Since i ∈ S, i does not belong to N \\ S, so the cardinality of this disjoint union is |N \\ S| + 1 = |N| - |S| + 1.
uses
three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_union,three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_inter,three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_symm,Finset.mem_sdiff,Finset.card_insert_of_notMem,Finset.card_univ_sdiff/-- Coalitions with excess marginal contribution in 3-distant convex games are co-singletons. -/ theorem three_distant_convex_excess_marginal_eq_sdiff_singleton {N : Type*} [DecidableEq N] [Fintype N] {v : Finset N → ℝ} (hv : is_three_distant_convex v) (S : Finset N) (i : N) (hi : i ∈ S) (h_excess : v S - v (S \ {i}) > v Finset.univ - v (Finset.univ \ {i})) : ∃ j ∈ Finset.univ \ {i}, S = Finset.univ \ {j} := by have hunion : S ∪ (Finset.univ \ {i}) = Finset.univ := three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_union S i hi have hinter : S ∩ (Finset.univ \ {i}) = S \ {i} := three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_inter S i have hsymm : symmDiff S (Finset.univ \ {i}) = insert i (Finset.univ \ S) := three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_symm S i hi have hnotmem : i ∉ Finset.univ \ S := by simp [Finset.mem_sdiff, hi] have hcard : (symmDiff S (Finset.univ \ {i})).card = Fintype.card N - S.card + 1 := by rw [hsymm, Finset.card_insert_of_notMem hnotmem, Finset.card_univ_sdiff]
It is not the case that |S| + 2 ≤ |N|.
Suppose for contradiction that |S| + 2 ≤ |N|. Then the symmetric difference S ∆ (N \\ {i}) has size |N| - |S| + 1 ≥ 3. Applying 3-distant convexity of v to S and N \\ {i} gives v(S) + v(N \\ {i}) ≤ v(S ∪ (N \\ {i})) + v(S ∩ (N \\ {i})), which simplifies to v(S) + v(N \\ {i}) ≤ v(N) + v(S \\ {i}). Rearranging yields v(S) - v(S \\ {i}) ≤ v(N) - v(N \\ {i}), directly contradicting the excess marginal contribution hypothesis.
have hkey : ¬ (S.card + 2 ≤ Fintype.card N) := by intro hle have h3 : 3 ≤ (symmDiff S (Finset.univ \ {i})).card := by rw [hcard]; omega have h := hv S (Finset.univ \ {i}) h3 rw [hunion, hinter] at h linarith
S is not the grand coalition N.
If S = N, substituting S = N into the excess marginal contribution assumption yields v(N) - v(N \\ {i}) > v(N) - v(N \\ {i}), which is an immediate contradiction.
have hSne : S ≠ Finset.univ := by intro h rw [h] at h_excess linarith
|S| = |N| - 1 and the complement N \\ S has cardinality 1.
Since S ≠ N, S is a strict subset of N, so |S| < |N|. Together with ¬(|S| + 2 ≤ |N|), linear integer arithmetic yields |S| = |N| - 1. Because i ∈ S, S is nonempty (|S| > 0). The complement N \\ S therefore has size |N| - |S| = |N| - (|N| - 1) = 1.
uses
Finset.ssubset_univ_iff.mpr,Finset.card_lt_card,Finset.card_pos.mpr,Finset.card_univ_sdiffhave hlt : S.card < Fintype.card N := by have hsub : S ⊂ Finset.univ := Finset.ssubset_univ_iff.mpr hSne simpa using Finset.card_lt_card hsub have hScc : S.card = Fintype.card N - 1 := by omega have hpos : 0 < S.card := Finset.card_pos.mpr ⟨i, hi⟩ have hcompl : (Finset.univ \ S).card = 1 := by rw [Finset.card_univ_sdiff, hScc]; omega
The complement N \\ S is a singleton {j} with j ∈ N \\ {i}.
Because |N \\ S| = 1, there exists some player j such that N \\ S = {j}. To show j ∈ N \\ {i}, we check j ≠ i: if j = i, then since j ∈ N \\ S we would have i ∉ S, contradicting i ∈ S. Hence j ≠ i, meaning j ∈ N \\ {i}.
uses
Finset.card_eq_one.mp,Finset.mem_sdiff,Finset.mem_singleton,Finset.mem_univobtain ⟨j, hj⟩ := Finset.card_eq_one.mp hcompl refine ⟨j, ?_, ?_⟩ · rw [Finset.mem_sdiff, Finset.mem_singleton] refine ⟨Finset.mem_univ j, ?_⟩ intro hji have hjS : j ∈ Finset.univ \ S := by rw [hj]; simp rw [Finset.mem_sdiff] at hjS exact hjS.2 (hji ▸ hi)
S = N \\ {j}.
Since N \\ S = {j}, taking the complement relative to N gives N \\ (N \\ S) = N \\ {j}. Because S is a subset of N, the double complement N \\ (N \\ S) is equal to S itself.
uses
Finset.sdiff_sdiff_eq_self,Finset.subset_univ· rw [← hj] exact (Finset.sdiff_sdiff_eq_self (Finset.subset_univ S)).symm
Finset.mem_symmDiff- An element belongs to the symmetric difference of two finite sets if and only if it belongs to exactly one of them.
Finset.mem_insert- An element belongs to insert a s if and only if it equals a or belongs to s.
Finset.mem_sdiff- An element belongs to s \\ t if and only if it belongs to s and does not belong to t.
Finset.mem_univ- Every element of a finite type belongs to the universal set Finset.univ.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
true_and- The conjunction of True with any proposition p is logically equivalent to p.
not_not- Double negation elimination: not not a is equivalent to a.
Finset.mem_union- An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
Finset.mem_inter- An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_union- For any coalition S containing player i, the union of S and N \\ {i} is the grand coalition Finset.univ.
three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_inter- The intersection of any coalition S with N \\ {i} is S \\ {i}.
three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_symm- For any coalition S containing player i, the symmetric difference of S and N \\ {i} equals {i} ∪ (N \\ S).
Finset.card_insert_of_notMem- Inserting an element not present in a finite set increases its cardinality by 1.
Finset.card_univ_sdiff- The cardinality of the complement Finset.univ \\ s is the ambient size |N| minus the cardinality of s.
Finset.ssubset_univ_iff.mpr- A finite set that is not equal to Finset.univ is a strict subset of Finset.univ.
Finset.card_lt_card- A strict subset of a finite set has strictly smaller cardinality.
Finset.card_pos.mpr- A nonempty finite set has strictly positive cardinality.
Finset.card_eq_one.mp- A finite set with cardinality 1 is a singleton {a}.
Finset.sdiff_sdiff_eq_self- For any subset t ⊆ s, the complement in s of the complement in s of t is t itself.
Finset.subset_univ- Every finite set of elements of a finite type is a subset of Finset.univ.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finsetprivate lemma three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_symm {N : Type*} [DecidableEq N] [Fintype N] (S : Finset N) (i : N) (hi : i ∈ S) : symmDiff S (Finset.univ \ {i}) = insert i (Finset.univ \ S) := by ext x simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_sdiff, Finset.mem_univ, Finset.mem_singleton, true_and, not_not] by_cases h : x = i · subst h; simp [hi] · simp [h]private lemma three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_union {N : Type*} [DecidableEq N] [Fintype N] (S : Finset N) (i : N) (hi : i ∈ S) : S ∪ (Finset.univ \ {i}) = Finset.univ := by ext x simp only [Finset.mem_union, Finset.mem_sdiff, Finset.mem_univ, Finset.mem_singleton, true_and] by_cases h : x = i <;> simp [h, hi]private lemma three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_inter {N : Type*} [DecidableEq N] [Fintype N] (S : Finset N) (i : N) : S ∩ (Finset.univ \ {i}) = S \ {i} := by ext x simp [Finset.mem_inter, Finset.mem_sdiff]/-- Coalitions with excess marginal contribution in 3-distant convex games are co-singletons. -/theorem three_distant_convex_excess_marginal_eq_sdiff_singleton {N : Type*} [DecidableEq N] [Fintype N] {v : Finset N → ℝ} (hv : is_three_distant_convex v) (S : Finset N) (i : N) (hi : i ∈ S) (h_excess : v S - v (S \ {i}) > v Finset.univ - v (Finset.univ \ {i})) : ∃ j ∈ Finset.univ \ {i}, S = Finset.univ \ {j} := by have hunion : S ∪ (Finset.univ \ {i}) = Finset.univ := three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_union S i hi have hinter : S ∩ (Finset.univ \ {i}) = S \ {i} := three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_inter S i have hsymm : symmDiff S (Finset.univ \ {i}) = insert i (Finset.univ \ S) := three_distant_convex_excess_marginal_eq_sdiff_singleton_aux_symm S i hi have hnotmem : i ∉ Finset.univ \ S := by simp [Finset.mem_sdiff, hi] have hcard : (symmDiff S (Finset.univ \ {i})).card = Fintype.card N - S.card + 1 := by rw [hsymm, Finset.card_insert_of_notMem hnotmem, Finset.card_univ_sdiff] have hkey : ¬ (S.card + 2 ≤ Fintype.card N) := by intro hle have h3 : 3 ≤ (symmDiff S (Finset.univ \ {i})).card := by rw [hcard]; omega have h := hv S (Finset.univ \ {i}) h3 rw [hunion, hinter] at h linarith have hSne : S ≠ Finset.univ := by intro h rw [h] at h_excess linarith have hlt : S.card < Fintype.card N := by have hsub : S ⊂ Finset.univ := Finset.ssubset_univ_iff.mpr hSne simpa using Finset.card_lt_card hsub have hScc : S.card = Fintype.card N - 1 := by omega have hpos : 0 < S.card := Finset.card_pos.mpr ⟨i, hi⟩ have hcompl : (Finset.univ \ S).card = 1 := by rw [Finset.card_univ_sdiff, hScc]; omega obtain ⟨j, hj⟩ := Finset.card_eq_one.mp hcompl refine ⟨j, ?_, ?_⟩ · rw [Finset.mem_sdiff, Finset.mem_singleton] refine ⟨Finset.mem_univ j, ?_⟩ intro hji have hjS : j ∈ Finset.univ \ S := by rw [hj]; simp rw [Finset.mem_sdiff] at hjS exact hjS.2 (hji ▸ hi) · rw [← hj] exact (Finset.sdiff_sdiff_eq_self (Finset.subset_univ S)).symm