Lemma A.2 — benchmark preservation
ProvedCompDesignBFM.lemma_A_2budget-feasiblemechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be normalized and nonnegative and . For every nonnegative cost vector ,
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_CompDesignBFM_closure import Definitions.Def_CompDesignBFM_OPT
Formal statement
namespace CompDesignBFM
/-- Lemma A.2, Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, p.40, PDF 42. For every nonnegative cost vector `c`, `OPT_v̂(c) = OPT_v(c)`, for a normalized
nonnegative `v` (Appendix A, p.40) and a budget `B > 0`. -/
theorem lemma_A_2 {n : ℕ} (v : Finset (Fin n) → ℝ) (hv0 : v ∅ = 0) (hv : ∀ S, 0 ≤ v S) (B : ℝ) (hB : 0 < B)
(c : Fin n → ℝ) (hc : ∀ i, 0 ≤ c i) :
OPT (closure v) B c = OPT v B c := by sorry
end CompDesignBFM
Source
Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, Lemma A.2, p.40 (PDF 42)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.