Lemma 2 (regular part), p. 5 — the revenue of a truthful mechanism is at most
ProvedCHMSPricing.UnitDemand.revenue_le_sum_price_mul_probConsider a single-parameter instance with independent values , each regular, and any set system . Let be a truthful mechanism, let be the probability (over ) that allocates to agent , and let , the point of the support with . Then
Applied to the instance with copies, this bounds the optimal revenue by a sum of single-agent posted-price revenues, the quantity the order-oblivious prices of Theorem 13 are compared with.
Formalization Note Only the first (regular) paragraph of Lemma 2 is stated; the second paragraph, about non-regular distributions and pairs of prices, is out of scope. The inverse distribution function is not defined: the prices are arguments, tied to by the hypothesis and ; such a point exists and is unique since is continuous and strictly increasing on the support. Regularity is assumed as in the paper.
import Mathlib import Definitions.Def_CHMSPricing_UnitDemand_Mechanism
namespace CHMSPricing.UnitDemand
/-- Lemma 2 (regular part), p. 5: if every `Fᵢ` is regular, the revenue of every truthful
mechanism `M` is at most `∑ᵢ p^M_i q^M_i`, where `q^M_i` is the probability that `M` serves
agent `i` and `p^M_i = Fᵢ⁻¹(1 − q^M_i)` (the point of the support with `Fᵢ(p^M_i) = 1 − q^M_i`). -/
theorem revenue_le_sum_price_mul_prob {ι : Type*} [Fintype ι] [DecidableEq ι]
(D : ι → ValueDist) (hreg : ∀ i, (D i).Regular) (𝒥 : SetSystem ι)
(M : Mechanism ι) (hM : IsTruthful D 𝒥 M) (pM : ι → ℝ)
(hpM : ∀ i, pM i ∈ Set.Icc (D i).lo (D i).hi ∧ (D i).cdf (pM i) = 1 - servProb D M i) :
revenue D M ≤ ∑ i, pM i * servProb D M i := by sorry
end CHMSPricing.UnitDemand
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.