op_1641_convex_implies_two_thirds_convex_and_superadditive
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.
Nis the player type;Uis the utility type.vassigns 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.
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.
uses
CoalitionalGame.IsConvex.isSuperadditiverefine ⟨?_, CoalitionalGame.IsConvex.isSuperadditive G hconv⟩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.
uses
Or.inlintro 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.
- The pairwise distinctness assumptions on the coalitions S₁, S₂, S₃ are discarded (introduced as `_ _ _`) because convexity holds unconditionally for all pairs of coalitions.
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.
/-- 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₃⟩