Theorem 13, p. 9 — for the intersection of two partition matroids some -approximates the optimal revenue
ProvedCHMSPricing.UnitDemand.two_partition_opm_approxLet be an instance of the BSMD with independent regular values whose feasibility constraint is the intersection of two partition matroids . Then there exist prices such that
for every truthful mechanism for ; in particular -approximates the revenue 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 ; the prices are chosen before the mechanism (). The constant is written . 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.
import Mathlib import Definitions.Def_CHMSPricing_UnitDemand_Mechanism
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.