§3.2.1 — monotone XOS functions are subadditive and self-bounding
ProvedCompDesignBFM.xos_subadditive_self_boundingbudget-feasiblemechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1
If is XOS and monotone, then is subadditive and self-bounding. Consequently can serve as its own proxy in the marginal-contribution branch.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_CompDesignBFM_IsXOS import Definitions.Def_CompDesignBFM_IsMonotoneSF import Definitions.Def_CompDesignBFM_IsSelfBounding import Definitions.Def_BudgetClock_Subadditive_Setting
Formal statement
namespace CompDesignBFM
/-- §3.2.1, Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, p.17, PDF 19. Monotone XOS functions are both subadditive and self-bounding. -/
theorem xos_subadditive_self_bounding {n : ℕ} (v : Finset (Fin n) → ℝ) (hx : IsXOS v)
(hm : IsMonotoneSF v) :
BudgetClock.Subadditive.IsSubadditive v ∧ IsSelfBounding v := by sorry
end CompDesignBFM
Source
Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, §3.2.1, p.17 (PDF 19)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.