AFTD Auto-Formalizing Theoretical Domains

is_matroid_rank_valuation

def

A set function on a finite set of indivisible goods is a matroid-rank valuation if it evaluates the empty set to 0, is submodular, and has binary marginal gains (every marginal value is 0 or 1).

Statement

def is_matroid_rank_valuation {m : ℕ} (v : Finset (Fin m) → ℝ) : Prop
Defined in
arXiv:2012.12710
Verified
28 Oct 2026
Axioms
none listed
Built on 2
  • is_submodularA set function is submodular: for S inside T and j outside T, the marginal value of j over T is at most its marginal value over S.
  • has_binary_marginalsEvery marginal value of the set function is 0 or 1.
Used by 4

Read back from the Lean

Given a natural number $m$ and a function $v : \mathrm{Finset}(\mathrm{Fin}\ m) \to \mathbb{R}$, the predicate is_matroid_rank_valuation v asserts the conjunction of three conditions: 1. $v(\emptyset) = 0$; 2. $v$ is submodular (is_submodular v); and 3. $v$ has binary marginal returns (has_binary_marginals v).

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 matroid-rank valuation is a normalized, submodular set function with binary marginal gains. -/
def is_matroid_rank_valuation {m : ℕ} (v : Finset (Fin m) → ℝ) : Prop :=
  v ∅ = 0 ∧ is_submodular v ∧ has_binary_marginals v
See it in the graphDiscuss this resultChallenge it