Lemma 3 — posting independent single-item prices together keeps the caps and a (1 − 1/e) fraction of single-item utility
ProvedConsumerUtilityApprox.UnitDemand.lemma_3consumer-utilitymechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probability
Let be independent item values ( on , ) and independent prices, independent of the values, with laws on (: item is not offered). Suppose for each and . Let , and let post all prices together, the buyer taking an item of largest strictly positive surplus (ties uniform, no purchase otherwise) and paying its price. Then allocates item with probability at most , and
This recovers the deletion-loss part of the benchmark with a unit-demand mechanism.
Differences from the source:
- encoding: values in R_+, laws F_j, items 1..m → ℝ≥0, ProbabilityMeasure ℝ≥0, Fin m; product law vecLaw; reason: Lean conventions for the same objects
- generalization: independent (possibly randomized) nonnegative prices P_j → independent price laws on [0, ∞], ∞ meaning no offer; reason: §2.3 and Lemma 5 apply the lemma to prices that may be infinite; finite prices are the special case of laws on [0, ∞)
- reading: the buyer chooses their utility-maximizing option → largest strictly positive surplus, ties uniform, no purchase at zero surplus; reason: tie rules of p. 7
Preamble
import Mathlib import Definitions.Def_MultiItemRev_BundlingOpt_Model import Definitions.Def_ConsumerUtilityApprox_UnitDemand_Model open MeasureTheory ProbabilityTheory open scoped NNReal ENNReal open MultiItemRev.BundlingOpt
Formal statement
namespace ConsumerUtilityApprox.UnitDemand
theorem lemma_3 {m : ℕ} (hm : 1 ≤ m) (G : Fin m → ProbabilityMeasure ℝ≥0)
(hG : ∀ j, IsValueLaw (G j)) (π : Fin m → Measure ℝ≥0∞)
[∀ j, IsProbabilityMeasure (π j)] (q : Fin m → ℝ)
(hq : ∀ j, saleProb1 (G j) (π j) ≤ q j) (hsum : ∑ j, q j ≤ 1) :
(∀ j, udAlloc G π j ≤ q j) ∧
(1 - Real.exp (-1)) * ∑ j, postedUtility1 (G j) (π j) ≤ udUtility G π := by sorry
end ConsumerUtilityApprox.UnitDemand
Source
Goldner, Lundy, Tsilivis, A Constant-Factor Approximation to Multidimensional Consumer Utility, arXiv:2610.10516 (version of November 3, 2026, sha256 94e0dd44…), p. 14, Lemma 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.