is_submodular
def
A 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.
Statement
def is_submodular {m : ℕ} (v : Finset (Fin m) → ℝ) : Prop
- Defined in
- Exploring Relations among Fairness Notions in Discrete Fair Division, arXiv:2502.02815 v3, Defs. 5, 7, 8, 11; formalized by the operator (Claude), 2026-10-02
- Verified
- 02 Oct 2026
- Axioms
- none listed
- Used by 15
- 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…
- is_submodular_addThe pointwise sum of two submodular set functions is submodular.
- zero_is_matroid_rank_valuationThe constantly zero set function is a matroid-rank valuation.
- submod_union_marginal_leFor a monotone submodular set function and S inside T, adding a set U gains at most as much on top of T as on top of S.
- submod_add_items_leFor a submodular set function, if every item of G lies outside A and adds at most delta >= 0 to A, then adding G to any superset W of A…
- is_submodular_smul_nonnegNon-negative scaling preserves submodularity of a set function.
- pmms_fair_not_imp_mms_fairOpen problem 4 of arXiv:2502.02815 has a negative answer: for submodular goods with binary marginals and equal entitlements, pairwise MMS…
- empty_eq_zero_of_matroid_rank_valuationA matroid-rank valuation evaluates the empty set to 0.
- op_737_two_level_submodularFor n > 2, any surjective block-assignment map proj : Fin n → Fin 2, any Gibbs vector γ in stdSimplex ℝ (Fin n) with strictly positive…
- is_polymatroid_rankA set function f on subsets of Fin n is a polymatroid rank function if it is normalized at the empty set (f ∅ = 0), nondecreasing with…
- submod_zero_marginalsFor a monotone submodular set function, items whose marginal value over X is zero add nothing on top of any superset of X.
- is_matroid_rank_valuationA 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…
- submod_biUnion_le_sumA monotone submodular set function with v(empty) = 0 is subadditive over a finite family of sets.
- mxs_fair_imp_prop1_fair_of_submodularOpen problem 3 of arXiv:2502.02815 has a positive answer: for submodular goods (monotone, v(empty) = 0) and equal entitlements, every…
- linopt_major_cycle_discards_corral_atomThe formal major-cycle relation can discard the previous atom even though the enlarged two-atom support is already a corral, for the base…
Lean source view module on GitHub
/-- A set function is submodular: marginal values shrink as the set grows. -/ def is_submodular {m : ℕ} (v : Finset (Fin m) → ℝ) : Prop := ∀ S T j, S ⊆ T → j ∉ T → v (insert j T) - v T ≤ v (insert j S) - v S