submod_zero_marginals
theoremverified
For a monotone submodular set function, items whose marginal value over X is zero add nothing on top of any superset of X.
Statement
theorem submod_zero_marginals {m : ℕ} (v : Finset (Fin m) → ℝ) (hmono : Monotone v)
(hsub : is_submodular v) {X W : Finset (Fin m)} (hXW : X ⊆ W) (R : Finset (Fin m))
(hR : ∀ z ∈ R, v (insert z X) ≤ v X) : v (W ∪ R) = v W- 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 1
- 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.
/-- Items whose marginal value over `X` is zero add nothing on top of any superset of `X`. -/theorem submod_zero_marginals {m : ℕ} (v : Finset (Fin m) → ℝ) (hmono : Monotone v) (hsub : is_submodular v) {X W : Finset (Fin m)} (hXW : X ⊆ W) (R : Finset (Fin m)) (hR : ∀ z ∈ R, v (insert z X) ≤ v X) : v (W ∪ R) = v W := by have key : v (X ∪ R) ≤ v X := by induction R using Finset.induction_on with | empty => simp | insert a R ha ih => have ih' := ih (fun z hz => hR z (Finset.mem_insert_of_mem hz)) have haX := hR a (Finset.mem_insert_self a R) rw [Finset.union_insert] by_cases haXR : a ∈ X ∪ R · rw [Finset.insert_eq_of_mem haXR]; exact ih' · by_cases haX' : a ∈ X · exact absurd (Finset.mem_union_left R haX') haXR · have h := hsub X (X ∪ R) a Finset.subset_union_left haXR linarith have h := submod_union_marginal_le v hmono hsub hXW R have hge : v W ≤ v (W ∪ R) := hmono Finset.subset_union_left have hge' : v X ≤ v (X ∪ R) := hmono Finset.subset_union_left linarith