Lemma 3.2 — the marginal-contribution rule is nonnegative and budget feasible
ProvedCompDesignBFM.lemma_3_2budget-feasiblemechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be normalized and self-bounding, and let . For every participating set , the marginal-contribution payments (7) satisfy
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_CompDesignBFM_IsSelfBounding import Definitions.Def_CompDesignBFM_mcPay
Formal statement
namespace CompDesignBFM
/-- Lemma 3.2, Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, p.14, PDF 16. If `F` is normalized and self-bounding, then the marginal-contribution
payment rule (7) is nonnegative and budget feasible, at every participating set `S`. -/
theorem lemma_3_2 {n : ℕ} (F : Finset (Fin n) → ℝ) (B : ℝ) (hB : 0 < B) (hF0 : F ∅ = 0)
(hF : IsSelfBounding F) (S : Finset (Fin n)) :
(∀ i, 0 ≤ mcPay F B S i) ∧ ∑ i ∈ S, mcPay F B S i ≤ B := by sorry
end CompDesignBFM
Source
Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, Lemma 3.2, p.14 (PDF 16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.