AFTD Auto-Formalizing Theoretical Domains

submod_union_marginal_le

theoremverified

For 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.

Statement

theorem submod_union_marginal_le {m : ℕ} (v : Finset (Fin m) → ℝ) (hmono : Monotone v)
    (hsub : is_submodular v) {S T : Finset (Fin m)} (hST : S ⊆ T) (U : Finset (Fin m)) :
    v (T ∪ U) - v T ≤ v (S ∪ U) - v S
Source
step towards mxs_fair_imp_prop1_fair_of_submodular (open problem 3 of arXiv:2502.02815 v3, Sec. 6)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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.
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…
  • 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.
  • 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…

Lean source view module on GitHub

/-- For a monotone submodular set function and `S ⊆ T`, adding a set `U` gains at most as much on top of `T` as on top of `S`. -/theorem submod_union_marginal_le {m : ℕ} (v : Finset (Fin m) → ℝ) (hmono : Monotone v)    (hsub : is_submodular v) {S T : Finset (Fin m)} (hST : S ⊆ T) (U : Finset (Fin m)) :    v (T ∪ U) - v T ≤ v (S ∪ U) - v S := by  induction U using Finset.induction_on with  | empty => simp  | insert a U ha ih =>    rw [Finset.union_insert, Finset.union_insert]    by_cases haT : a ∈ T ∪ U    · rw [Finset.insert_eq_of_mem haT]      have : v (S ∪ U) ≤ v (insert a (S ∪ U)) := hmono (Finset.subset_insert _ _)      linarith    · have h := hsub (S ∪ U) (T ∪ U) a (Finset.union_subset_union hST le_rfl) haT      linarith
See it in the graphDiscuss this resultChallenge it