AFTD Auto-Formalizing Theoretical Domains

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