Proposition 6 (iii), p. 14 — Rev(X) is the supremum of R(µ;X) over IC, IR and NPT mechanisms
ProvedMultiItemRev.BundlingOpt.proposition_6_iiimechanism-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1revenue
Let be a -good random valuation with with law on . Then the optimal revenue is already attained in the supremum over mechanisms with no positive transfer:
Restricting to NPT mechanisms () is what allows the proof of Theorem 16 to truncate revenue integrals without sign issues.
Formalization Note Each revenue is clipped at inside the supremum, exactly as in the definition of ; for NPT mechanisms , so the clip is inactive there.
Preamble
import Mathlib import Definitions.Def_MultiItemRev_BundlingOpt_Model open MeasureTheory open scoped NNReal ENNReal
Formal statement
namespace MultiItemRev.BundlingOpt
theorem proposition_6_iii {ι : Type*} [Fintype ι] [Nonempty ι] (μ : Measure (ι → ℝ≥0))
[IsProbabilityMeasure μ] :
Rev μ = ⨆ (M : Mechanism ι) (_ : IsAdmissible M ∧ IsNPT M), (expRevenue μ M).toENNReal := by sorry
end MultiItemRev.BundlingOpt
Source
Hart and Nisan, Approximate Revenue Maximization with Multiple Items, arXiv:1204.1846v3, p. 14, Proposition 6 (iii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.