AFTD Auto-Formalizing Theoretical Domains

is_permutationally_convex

def

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

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