AFTD Auto-Formalizing Theoretical Domains

three_distant_convex_excess_marginal_eq_sdiff_singleton

theoremverifiedformalization

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.

  1. 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.

    lines 3–12

    uses Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_sdiff, Finset.mem_univ, Finset.mem_singleton, true_and, not_not

    private 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]
    
  2. 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.

    lines 13–19

    uses Finset.mem_union, Finset.mem_sdiff, Finset.mem_univ, Finset.mem_singleton, true_and

    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]
    
  3. 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}.

    lines 20–25

    uses Finset.mem_inter, Finset.mem_sdiff

    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]
    
  4. 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.

    lines 26–40

    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]
  5. 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.

    lines 41–46

      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
  6. 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.

    lines 47–50

      have hSne : S ≠ Finset.univ := by
        intro h
        rw [h] at h_excess
        linarith
  7. |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.

    lines 51–57

    uses Finset.ssubset_univ_iff.mpr, Finset.card_lt_card, Finset.card_pos.mpr, Finset.card_univ_sdiff

      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
  8. 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}.

    lines 58–65

    uses Finset.card_eq_one.mp, Finset.mem_sdiff, Finset.mem_singleton, Finset.mem_univ

      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)
  9. 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.

    lines 66–67

    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

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
See it in the graphDiscuss this resultChallenge it