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
- complete_pmms_matroid_rank_sharp_mms_factorFor every integer n ≥ 2, every finite set of m indivisible goods, every profile of matroid-rank valuations v_1, ..., v_n on the goods, and…
- zero_is_matroid_rank_valuationThe constantly zero set function is a matroid-rank valuation.
- empty_eq_zero_of_matroid_rank_valuationA matroid-rank valuation evaluates the empty set to 0.
- pmms_matroid_rank_mms_factor_two_agentsFor two agents with matroid-rank valuations, every complete pairwise maximin-share fair allocation gives each agent at least 1/(2-1) = 1…
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