Lemma 3.1 — marginals of submodular functions
ProvedCompDesignBFM.lemma_3_1budget-feasiblemechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every normalized monotone submodular valuation and every ,
So monotone submodular functions are self-bounding, and the marginal-contribution rule on is budget feasible.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_CompDesignBFM_IsMonotoneSF import Definitions.Def_CompDesignBFM_IsSubmodularSF
Formal statement
namespace CompDesignBFM
/-- Lemma 3.1, Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, p.13, PDF 15. For every normalized monotone submodular valuation and every `S ⊆ N`,
`∑ i ∈ S, (v S - v (S ∖ {i})) ≤ v S`. -/
theorem lemma_3_1 {n : ℕ} (v : Finset (Fin n) → ℝ) (hv0 : v ∅ = 0) (hm : IsMonotoneSF v)
(hs : IsSubmodularSF v) (S : Finset (Fin n)) :
∑ i ∈ S, (v S - v (S.erase i)) ≤ v S := by sorry
end CompDesignBFM
Source
Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, Lemma 3.1, p.13 (PDF 15)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.