Lemma A.1 — structure of the monotone closure
ProvedCompDesignBFM.lemma_A_1budget-feasiblemechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be normalized and nonnegative.
- If is subadditive, then is normalized, monotone and subadditive.
- If is XOS, then is normalized, monotone and XOS.
This reduces the nonmonotone classes of the goal to monotone ones.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_CompDesignBFM_closure import Definitions.Def_CompDesignBFM_IsMonotoneSF import Definitions.Def_CompDesignBFM_IsXOS import Definitions.Def_BudgetClock_Subadditive_Setting
Formal statement
namespace CompDesignBFM
/-- Lemma A.1, Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, p.40, PDF 42. If `v` is normalized, nonnegative and subadditive, then `v̂` is normalized,
monotone and subadditive. If `v` is normalized, nonnegative and XOS, then `v̂` is normalized, monotone and XOS. -/
theorem lemma_A_1 {n : ℕ} (v : Finset (Fin n) → ℝ) (hv0 : v ∅ = 0) (hv : ∀ S, 0 ≤ v S) :
(BudgetClock.Subadditive.IsSubadditive v →
closure v ∅ = 0 ∧ IsMonotoneSF (closure v) ∧
BudgetClock.Subadditive.IsSubadditive (closure v)) ∧
(IsXOS v → closure v ∅ = 0 ∧ IsMonotoneSF (closure v) ∧ IsXOS (closure v)) := by sorry
end CompDesignBFM
Source
Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, Lemma A.1, p.40 (PDF 42)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.