Theorem 19, p. 12 — a revenue-optimal truthful mechanism exists ()
ProvedCHMSPricing.UnitDemand.optimal_mechanism_existsmechanism-designmyersonp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-paperp2o-v1revenue
Consider a single-parameter instance with independent regular values and a set system . There is a truthful mechanism (Myerson's mechanism) such that
The construction of the prices in Theorem 13 starts from the service probabilities of this optimal mechanism, so its existence is what allows one set of prices to serve as a benchmark for all truthful mechanisms at once.
Formalization Note The statement is the existence content of Theorem 19: Myerson's mechanism is not constructed (pin P4). It is stated for regular distributions, the case used by the body of the paper (pin P2); the paper's theorem also covers non-regular distributions through ironing.
Preamble
import Mathlib import Definitions.Def_CHMSPricing_UnitDemand_Mechanism
Formal statement
namespace CHMSPricing.UnitDemand
/-- Theorem 19, p. 12 (existence form, pin P4): with regular distributions there is a truthful
mechanism (Myerson's) whose expected revenue `ℛ^ℳ` is at least `ℛ^𝒜` for every truthful
mechanism `𝒜`. -/
theorem optimal_mechanism_exists {ι : Type*} [Fintype ι] [DecidableEq ι]
(D : ι → ValueDist) (hreg : ∀ i, (D i).Regular) (𝒥 : SetSystem ι) :
∃ Mstar : Mechanism ι, IsTruthful D 𝒥 Mstar ∧
∀ A : Mechanism ι, IsTruthful D 𝒥 A → revenue D A ≤ revenue D Mstar := by sorry
end CHMSPricing.UnitDemand
Source
Chawla, Hartline, Malec and Sivan, Multi-parameter Mechanism Design and Sequential Posted Pricing, arXiv:0907.2435v2, p. 12, Theorem 19, App. A
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.