Proposition 6 (iii), p. 14 — Rev(X) is the supremum over IC, IR and NPT mechanisms
ProvedMultiItemRev.Decomp.proposition_6_iiimechanism-designno-positive-transferp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1revenue
Let be a -good random valuation in , . Then the optimal revenue can be computed over mechanisms with no positive transfer:
No positive transfers () can thus be assumed without loss of generality when maximizing revenue. This is what allows the revenue from a mechanism to be split over two regions of the valuation space that cover it, as in the proofs of Theorem A and Theorem 7.
Formalization Note The supremum ranges over mechanisms in the class (IC, IR, , measurable ) that are also NPT; their revenues are nonnegative, so the clipping to in toENNReal is the identity on them.
Preamble
import Mathlib import Definitions.Def_MultiItemRev_Decomp_Model open MeasureTheory open scoped NNReal ENNReal
Formal statement
namespace MultiItemRev.Decomp
theorem proposition_6_iii {ι : Type*} [Fintype ι] [Nonempty ι]
(μ : Measure (ι → ℝ≥0)) [IsProbabilityMeasure μ] :
Rev μ = ⨆ (M : Mechanism ι) (_ : IsAdmissible M ∧ IsNPT M), (expRevenue μ M).toENNReal := by sorry
end MultiItemRev.Decomp
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.