Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 13, p. 9 — for the intersection of two partition matroids some Rpobl\mathcal R^{\mathrm{obl}}_{\mathbf p}Rpobl​6.756.756.75-approximates the optimal revenue

Proved
CHMSPricing.UnitDemand.two_partition_opm_approx

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

matroidsmechanism-designp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-paperp2o-v1posted-prices

Let I\mathcal II be an instance of the BSMD with independent regular values vi∼Fiv_i \sim F_ivi​∼Fi​ whose feasibility constraint is the intersection of two partition matroids M1,M2\mathcal M_1, \mathcal M_2M1​,M2​. Then there exist prices ppp such that

RM≤6.75⋅Rpobl\mathcal R^{M} \le 6.75 \cdot \mathcal R^{\mathrm{obl}}_{\mathbf p}RM≤6.75⋅Rpobl​

for every truthful mechanism MMM for I\mathcal II; in particular Rpobl\mathcal R^{\mathrm{obl}}_{\mathbf p}Rpobl​ 6.756.756.75-approximates the revenue RM\mathcal R^{\mathcal M}RM of Myerson's mechanism.

With Theorem 4 this yields the price-menu mechanism of Theorem 14 for unit-demand buyers of several items in several copies, whose constraint is such an intersection.

Formalization Note The comparison is with every truthful mechanism (pin P4), which by Theorem 19 is the paper's comparison with RM\mathcal R^{\mathcal M}RM; the prices are chosen before the mechanism (∃p ∀M\exists p\ \forall M∃p ∀M). The constant is written 27/427/427/4. Regularity is assumed as in the proof (App. D.4: "the mechanism which achieves a 6.75-approximation when the distributions are regular"); the non-regular extension is out of scope.

Preamble
import Mathlib
import Definitions.Def_CHMSPricing_UnitDemand_Mechanism
Formal statement
namespace CHMSPricing.UnitDemand

/-- Theorem 13, p. 9: for an instance of the BSMD (regular distributions) whose feasibility
constraint is the intersection of two partition matroids, there are prices `p` such that
`ℛ^obl_p` `6.75`-approximates the optimal revenue: `ℛ^M ≤ (27/4)·ℛ^obl_p` for every truthful
mechanism `M`. -/
theorem two_partition_opm_approx {ι β₁ β₂ : Type*} [Fintype ι] [DecidableEq ι]
    [DecidableEq β₁] [DecidableEq β₂]
    (D : ι → ValueDist) (hreg : ∀ i, (D i).Regular)
    (part₁ : ι → β₁) (cap₁ : β₁ → ℕ) (part₂ : ι → β₂) (cap₂ : β₂ → ℕ) :
    ∃ p : ι → ℝ, ∀ M : Mechanism ι,
      IsTruthful D (twoPartitionSystem part₁ cap₁ part₂ cap₂) M →
        revenue D M ≤ (27 / 4 : ℝ) * oblRevenue D (twoPartitionSystem part₁ cap₁ part₂ cap₂) 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, Theorem 13 (proof: pp. 19–20, App. D.4)
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