is_permutationally_convex
A cooperative game v on a finite set of players α is permutationally convex if there exists an ordering of the players e : Fin (|α|) ≃ α such that for all indices 0 ≤ j ≤ k ≤ |α| and all coalitions S disjoint from the prefix of the first k players, v([j] ∪ S) + v([k]) ≤ v([k] ∪ S) + v([j]).
Statement
def is_permutationally_convex {α : Type*} [DecidableEq α] [Fintype α] (v : Finset α → ℝ) : Prop
- Defined in
- arXiv:2611.16207 Section 3.2, equation (8); Granot and Huberman (1982)
- Verified
- 14 Nov 2026
- Axioms
- none listed
- Used by 1
- zero_is_permutationally_convexThe constant zero cooperative game is permutationally convex.
Read back from the Lean
Given a finite type α with decidable equality and a set function v : Finset α → ℝ, is_permutationally_convex v asserts that:
There exists a bijection e : Fin (Fintype.card α) ≃ α such that, for pref : Fin (Fintype.card α + 1) → Finset α defined by pref k = { e(i) | i : Fin (Fintype.card α), (i : ℕ) < (k : ℕ) },
for all k, j : Fin (Fintype.card α + 1) with j ≤ k,
and for all S : Finset α that are disjoint from pref k,
v (pref j ∪ S) + v (pref k) ≤ v (pref k ∪ S) + v (pref j).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A cooperative game is permutationally convex if there is an ordering whose prefixes satisfy the convexity inequality for all disjoint coalitions. -/ def is_permutationally_convex {α : Type*} [DecidableEq α] [Fintype α] (v : Finset α → ℝ) : Prop := ∃ e : Fin (Fintype.card α) ≃ α, let pref : Fin (Fintype.card α + 1) → Finset α := fun k => (Finset.univ.filter (fun (i : Fin (Fintype.card α)) => (i : ℕ) < (k : ℕ))).image e ∀ (k j : Fin (Fintype.card α + 1)), j ≤ k → ∀ S : Finset α, Disjoint S (pref k) → v (pref j ∪ S) + v (pref k) ≤ v (pref k ∪ S) + v (pref j)