Equation (3.3) — the variation term is bounded by the total deletion loss
ProvedConsumerUtilityApprox.UnitDemand.eq_3_3consumer-utilitymechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be a buyer's type with independent coordinates , , and let be an independent copy of . Let be a truthful, individually rational single-buyer mechanism with nonnegative payments and allocations in , with utility , and let , , be its total expected deletion loss. Then
This bounds the variation term of the decomposition (3.1) of ; with Lemma 1 it gives the single-buyer bound (3.8) used in Lemma 5.
Differences from the source:
- reading: a single-buyer mechanism of §3 (unit-demand or constrained-additive; p. 13: the bounds need no unit demand) → any mechanism with x(b) ∈ [0,1]^m, no unit-demand clause; reason: §3 states these bounds for every feasible outcome set F ⊆ [0,1]^m (Theorem 1's setting); unit demand is a special case
- reading: expectations E[x_j(V)], E[u(V)] of a single-buyer mechanism (rules tacitly measurable) → IsTruthfulIRNPT includes Borel measurability of x and p; reason: the standing convention without which the source's expectations are undefined
- 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
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 eq_3_3 {m : ℕ} (hm : 1 ≤ m) (G : Fin m → ProbabilityMeasure ℝ≥0)
(hG : ∀ j, IsValueLaw (G j)) (M : Mechanism (Fin m)) (hM : IsTruthfulIRNPT M) :
(1 / 2 : ℝ) * ∫ vw, |buyerPayoff M vw.1 - buyerPayoff M vw.2| ∂((vecLaw G).prod (vecLaw G))
≤ totalDeletionLoss (vecLaw G) M := 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. 10, equation (3.3) (proved in Appendix A, p. 33, (A.1))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.