Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 14, p. 9 — a truthful 6.75-approximate posted-price menu for unit-demand buyers of multiple copies of multiple items

Proved
CHMSPricing.UnitDemand.unit_demand_opm_approx

by mikedeng1 · Oct 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

mechanism-designp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-paperp2o-v1posted-pricesunit-demand

Consider an instance of the BMUMD in which the seller has cap(k)\mathrm{cap}(k)cap(k) copies of each item kkk of a finite set KKK on sale, there are mmm unit-demand buyers, and buyer iii has a value v(i,k)v_{(i,k)}v(i,k)​ for item kkk, the values being independent with regular distributions F(i,k)F_{(i,k)}F(i,k)​. The feasible allocations give each buyer at most one item and use at most cap(k)\mathrm{cap}(k)cap(k) copies of item kkk.

Then there are prices p=(p(i,k))p = (p_{(i,k)})p=(p(i,k)​) such that for every arrival order σ\sigmaσ of the buyers the order-oblivious price-menu mechanism Pσ\mathcal P_\sigmaPσ​ with prices ppp is truthful and individually rational, and

RA≤6.75⋅RPσ\mathcal R^{\mathcal A} \le 6.75 \cdot \mathcal R^{\mathcal P_\sigma}RA≤6.75⋅RPσ​

for every individually rational, truthful deterministic mechanism A\mathcal AA 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 "6.756.756.75-approximate OPM" is spelled out: one set of prices, for every arrival order, a truthful mechanism, and the factor 27/427/427/4 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.

Preamble
import Mathlib
import Definitions.Def_CHMSPricing_UnitDemand_MenuMech
Formal statement
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
Source
Chawla, Hartline, Malec and Sivan, Multi-parameter Mechanism Design and Sequential Posted Pricing, arXiv:0907.2435v2, p. 9, §6.1, Theorem 14 (from Theorems 4 and 13)
Human review
  • Endorsed by Shuze Chen · Oct 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 4, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me