AFTD Auto-Formalizing Theoretical Domains

op_1641_convex_implies_two_thirds_convex_and_superadditive

theoremverified

Every convex coalitional game with real characteristic function is both 2/3-convex and superadditive.

Statement

theorem op_1641_convex_implies_two_thirds_convex_and_superadditive {N : Type*} [DecidableEq N]
    (G : CoalitionalGame N ℝ) (hconv : G.IsConvex) :
    G.IsTwoThirdsConvex ∧ G.IsSuperadditive
Source
arXiv:2611.16207, Core nonemptiness for 2/3-convex games, Section 2
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • CoalitionalGame.IsTwoThirdsConvexA transferable-utility game G with real characteristic function v on a finite set of players N is 2/3-convex if for every triple of…
  • CoalitionalGame.IsSuperadditiveA game is superadditive if the worth of the union of disjoint coalitions is at least the sum of their worths. [MSZ 16.8] Requires [LE U]…
  • CoalitionalGame.IsConvexA game is convex if it satisfies the supermodularity condition. [MSZ 17.51] Requires [LE U] (addition comes from [AddZeroClass U]).
  • CoalitionalGame.IsConvex.isSuperadditiveConvexity implies superadditivity. The [LE U] constraint is all that's needed beyond the section's [AddZeroClass U].
  • CoalitionalGameA coalitional game with transferable utility. N is the player type; U is the utility type. v assigns a worth to each coalition, with…

Read back from the Lean

For any type N with decidable equality, and any coalitional game G with player type N and real payoffs (that is, a characteristic function v : Finset N → ℝ satisfying v ∅ = 0), if G satisfies G.IsConvex, then G satisfies both G.IsTwoThirdsConvex and G.IsSuperadditive.

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

To show that a convex coalitional game is both 2/3-convex and superadditive, the proof splits the conjunction into two goals. Superadditivity is established immediately by an existing theorem showing that convexity implies superadditivity. For 2/3-convexity, which requires the supermodularity inequality to hold for at least two pairs among any three distinct coalitions, full convexity guarantees the inequality holds for all pairs, so the first case of the disjunction is satisfied directly.

  1. G is superadditive, reducing the theorem to showing that G is 2/3-convex.

    We split the conjunction into its two components. The second conjunct, that G is superadditive, is proved directly by CoalitionalGame.IsConvex.isSuperadditive, which states that any convex game is superadditive. This leaves the first conjunct, that G is 2/3-convex, as the remaining goal.

    line 5

    uses CoalitionalGame.IsConvex.isSuperadditive

      refine ⟨?_, CoalitionalGame.IsConvex.isSuperadditive G hconv⟩
  2. G is 2/3-convex.

    To show 2/3-convexity, we consider three arbitrary coalitions S₁, S₂, S₃ and discard the assumptions that they are pairwise distinct. The definition of 2/3-convexity requires that at least two of the three pairs among {S₁, S₂}, {S₁, S₃}, and {S₂, S₃} satisfy the supermodularity inequality v(S ∪ T) + v(S ∩ T) ≥ v(S) + v(T). Because G is convex, this inequality holds for every pair of coalitions. In particular, it holds for (S₁, S₂) and (S₁, S₃), satisfying the first disjunct via Or.inl.

    lines 6–7

    uses Or.inl

      intro S₁ S₂ S₃ _ _ _
      exact Or.inl ⟨hconv S₁ S₂, hconv S₁ S₃⟩
CoalitionalGame.IsConvex.isSuperadditive
Every convex coalitional game is superadditive: if S and T are disjoint coalitions, then v(S ∪ T) ≥ v(S) + v(T).
Or.inl
If proposition A holds, then the disjunction A ∨ B holds.

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

/-- Every convex game satisfies both 2/3-convexity and superadditivity. -/theorem op_1641_convex_implies_two_thirds_convex_and_superadditive {N : Type*} [DecidableEq N]    (G : CoalitionalGame N ℝ) (hconv : G.IsConvex) :    G.IsTwoThirdsConvex ∧ G.IsSuperadditive := by  refine ⟨?_, CoalitionalGame.IsConvex.isSuperadditive G hconv⟩  intro S₁ S₂ S₃ _ _ _  exact Or.inl ⟨hconv S₁ S₂, hconv S₁ S₃⟩
See it in the graphDiscuss this resultChallenge it