submod_biUnion_le_sum
theoremverified
A monotone submodular set function with v(empty) = 0 is subadditive over a finite family of sets.
Statement
theorem submod_biUnion_le_sum {m n : ℕ} (v : Finset (Fin m) → ℝ) (hmono : Monotone v)
(hsub : is_submodular v) (h0 : v ∅ = 0) (K : Finset (Fin n)) (B : Fin n → Finset (Fin m)) :
v (K.biUnion B) ≤ ∑ j ∈ K, v (B j)- 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 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.
- 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.
- Used by 2
- 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…
- 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- A monotone submodular set function with `v ∅ = 0` is subadditive over a family of sets. -/theorem submod_biUnion_le_sum {m n : ℕ} (v : Finset (Fin m) → ℝ) (hmono : Monotone v) (hsub : is_submodular v) (h0 : v ∅ = 0) (K : Finset (Fin n)) (B : Fin n → Finset (Fin m)) : v (K.biUnion B) ≤ ∑ j ∈ K, v (B j) := by induction K using Finset.induction_on with | empty => simp [h0] | insert a K ha ih => rw [Finset.biUnion_insert, Finset.sum_insert ha] have h := submod_union_marginal_le v hmono hsub (Finset.empty_subset (B a)) (K.biUnion B) rw [Finset.empty_union, h0] at h linarith