submod_add_items_le
theoremverified
For 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 gains at most |G| delta.
Statement
theorem submod_add_items_le {m : ℕ} (v : Finset (Fin m) → ℝ)
(hsub : is_submodular v) {A W : Finset (Fin m)} (hAW : A ⊆ W) {δ : ℝ} (hδ : 0 ≤ δ)
(G : Finset (Fin m)) (hG : ∀ g ∈ G, g ∉ A ∧ v (insert g A) ≤ v A + δ) :
v (W ∪ G) ≤ v W + G.card * δ- 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 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.
/-- If every item of `G` lies outside `A` and adds at most `δ ≥ 0` to `A`, then adding `G` to any superset `W` of `A` gains at most `|G| δ`. -/theorem submod_add_items_le {m : ℕ} (v : Finset (Fin m) → ℝ) (hsub : is_submodular v) {A W : Finset (Fin m)} (hAW : A ⊆ W) {δ : ℝ} (hδ : 0 ≤ δ) (G : Finset (Fin m)) (hG : ∀ g ∈ G, g ∉ A ∧ v (insert g A) ≤ v A + δ) : v (W ∪ G) ≤ v W + G.card * δ := by induction G using Finset.induction_on with | empty => simp | insert a G ha ih => have ih' := ih (fun g hg => hG g (Finset.mem_insert_of_mem hg)) obtain ⟨haA, hadd⟩ := hG a (Finset.mem_insert_self a G) rw [Finset.union_insert, Finset.card_insert_of_notMem ha] push_cast by_cases haWG : a ∈ W ∪ G · rw [Finset.insert_eq_of_mem haWG]; nlinarith · have h := hsub A (W ∪ G) a (hAW.trans Finset.subset_union_left) haWG linarith