zero_is_permutationally_convex
The constant zero cooperative game is permutationally convex.
Statement
theorem zero_is_permutationally_convex {α : Type*} [DecidableEq α] [Fintype α] : is_permutationally_convex (fun (_ : Finset α) => (0 : ℝ))
- Source
- folklore
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_permutationally_convexA cooperative game v on a finite set of players α is permutationally convex if there exists an ordering of the players e : Fin (|α|) ≃ α…
Read back from the Lean
For any finite type α with decidable equality, the constant zero function on Finset α (sending every Finset α to (0 : ℝ)) is permutationally convex (is_permutationally_convex).
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
A cooperative game is permutationally convex if there exists an ordering of the players such that marginal contributions along its prefix coalitions satisfy a convexity condition. For the constant zero game, any ordering works. The proof chooses the canonical ordering given by `Fintype.equivFin α`, after which the convexity inequality reduces to 0 + 0 ≤ 0 + 0, which holds trivially.
It suffices to show that under the canonical ordering of the players, the constant zero game satisfies the convexity inequality for all prefix indices j ≤ k and disjoint coalitions S.
Unfolding the definition of permutational convexity (`is_permutationally_convex`), we must exhibit an ordering of the players given by a bijection e : Fin (|α|) ≃ α. We instantiate this witness with the inverse of `Fintype.equivFin α`, the canonical equivalence between the finite type α and Fin (|α|).
uses
Fintype.equivFinunfold is_permutationally_convex use (Fintype.equivFin α).symm
The constant zero game satisfies the permutational convexity inequality.
We introduce arbitrary prefix indices j ≤ k and an arbitrary coalition S disjoint from the prefix coalition pref(k). The required inequality is v(pref(j) ∪ S) + v(pref(k)) ≤ v(pref(k) ∪ S) + v(pref(j)). Because the characteristic function v is identically zero, this simplifies to 0 + 0 ≤ 0 + 0, which `norm_num` verifies by elementary arithmetic.
intros norm_num
Fintype.equivFin- A canonical bijection between a finite type α and the set `Fin (Fintype.card α)` of natural numbers strictly less than the cardinality of α.
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.
/-- The constant zero game is permutationally convex. -/theorem zero_is_permutationally_convex {α : Type*} [DecidableEq α] [Fintype α] : is_permutationally_convex (fun (_ : Finset α) => (0 : ℝ)) := by unfold is_permutationally_convex use (Fintype.equivFin α).symm intros norm_num