AFTD Auto-Formalizing Theoretical Domains

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

Lean source view module on GitHub

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