Lemma 3.3 — the product bound behind the factor e
ProvedCompDesignBFM.lemma_3_3budget-feasiblemechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let satisfy , and let . Then
Differences from the source: none.
Preamble
import Mathlib
Formal statement
namespace CompDesignBFM
/-- Lemma 3.3, Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, p.16, PDF 18 (proof p.50, PDF 52). Let `x₁, …, xₙ ∈ [0, 1]` satisfy `∑ xᵢ ≤ 1`, and let
`i'` maximize `xᵢ`. Then `∏_(i ≠ i') (1 - xᵢ) ≥ e⁻¹`. -/
theorem lemma_3_3 {n : ℕ} (x : Fin n → ℝ) (hx0 : ∀ i, 0 ≤ x i) (hx1 : ∀ i, x i ≤ 1)
(hsum : ∑ i, x i ≤ 1) (i' : Fin n) (hi' : ∀ i, x i ≤ x i') :
Real.exp (-1) ≤ ∏ i ∈ Finset.univ.erase i', (1 - x i) := by sorry
end CompDesignBFM
Source
Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, Lemma 3.3, p.16 (PDF 18)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.