Theorem 14, p. 9 — a truthful 6.75-approximate posted-price menu for unit-demand buyers of multiple copies of multiple items
ProvedCHMSPricing.UnitDemand.unit_demand_opm_approxConsider an instance of the BMUMD in which the seller has copies of each item of a finite set on sale, there are unit-demand buyers, and buyer has a value for item , the values being independent with regular distributions . The feasible allocations give each buyer at most one item and use at most copies of item .
Then there are prices such that for every arrival order of the buyers the order-oblivious price-menu mechanism with prices is truthful and individually rational, and
for every individually rational, truthful deterministic mechanism for the instance.
This covers the hotel-rooms example of the introduction: rooms of several types in several copies sold to unit-demand guests by posting a menu of prices, within a constant factor of the optimal revenue of any deterministic truthful mechanism.
Formalization Note "-approximate OPM" is spelled out: one set of prices, for every arrival order, a truthful mechanism, and the factor against every deterministic truthful individually rational mechanism (the benchmark of Theorem 4). The last sentence of the paper's theorem, that the prices can be computed in polynomial time, is not formalized: it is an algorithmic claim with no cost model here. Regularity of the distributions is added: the theorem follows from Theorem 13, whose proof is given for regular distributions, the non-regular case being only sketched with randomized prices (App. E). Distributions follow pin P1. Ties in a buyer's choice are broken by a fixed rule, which has probability zero of mattering.
import Mathlib import Definitions.Def_CHMSPricing_UnitDemand_MenuMech
namespace CHMSPricing.UnitDemand
/-- Theorem 14, p. 9: `m` unit-demand buyers, items `K` with `cap k` copies of item `k`, and
independent regular values `v_{(i,k)} ∼ F_{(i,k)}` of each buyer for each item. There are prices
`p` such that, for every arrival order `σ`, the order-oblivious price-menu mechanism with prices
`p` is truthful and `6.75`-approximates the revenue of every deterministic truthful individually
rational mechanism. -/
theorem unit_demand_opm_approx {m : ℕ} {K : Type*} [Fintype K] [DecidableEq K]
(cap : K → ℕ) (D : Fin m × K → ValueDist) (hreg : ∀ j, (D j).Regular) :
∃ p : Fin m × K → ℝ, ∀ σ : Equiv.Perm (Fin m),
IsTruthfulMulti D (unitDemandSystem cap) Prod.fst
(menuMech (unitDemandSystem cap) Prod.fst σ p) ∧
∀ A : MultiMechanism (Fin m × K) m,
IsTruthfulMulti D (unitDemandSystem cap) Prod.fst A →
revenueMulti D A ≤
(27 / 4 : ℝ) * revenueMulti D (menuMech (unitDemandSystem cap) Prod.fst σ p) := by sorry
end CHMSPricing.UnitDemand
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.