Source-linked AI summary
Improved Revenue Guarantees for Selling Separately and Bundling
Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, Di Wang
TL;DR
For a single additive buyer with independent item values, the paper asks how much revenue may be lost by selling separately or offering a grand bundle instead of using an optimal mechanism. It uses a duality-based capped-welfare analysis and proves OPT ≤ 3.52 max{SREV, BREV}, improving the prior 5.2 factor toward the known lower bound of 2.
Problem
Optimal mechanisms for a single additive buyer with independent item values can require lotteries and infinite menus, while the prior 5.2 guarantee leaves a gap to the known lower bound of 2 for choosing between separate selling and grand bundling.
Source: §1 · pp. 1–2Method
The analysis uses duality, truncates at the joint revenue scale, and bounds non-favorite welfare through capped welfare and second-moment comparisons.
Source: §1.1 · p. 3Results
OPT ≤ 3.52 max{SREV, BREV}, uniformly over item counts and independent nonnegative value distributions without identical-distribution, MHR, or regularity requirements.
Source: §1 · p. 2Takeaways & Limitations
The guarantee narrows the known gap between the prior 5.2 factor and the lower bound of 2 for the better of separate selling and grand bundling.
Source: §1 · p. 2The theorem is scoped to a single buyer with additive valuations over independently distributed items.
Source: §2 · p. 4
Abstract
from arXiv · showhide
We study how much revenue a seller can lose by restricting attention to selling separately or grand bundling, in the setting of a single additive buyer with independent item values. Although revenue-optimal mechanisms can require lotteries and infinite menus, Babaioff, Immorlica, Lucier, and Weinberg showed that the better of these two simple formats always achieves a constant fraction of optimal revenue. We prove that $\mathrm{OPT} \le 3.52 \max\{\mathrm{SREV}, \mathrm{BREV}\}$, where $\mathrm{SREV}$ and $\mathrm{BREV}$ are the optimal revenues from selling separately and grand bundling, respectively. This improves the previous best-known approximation factor of $5.2$ due to Ma and Simchi-Levi and narrows the gap to the known lower bound of $2$.
1 Introduction
The introduction asks whether selling items separately or as one grand bundle can approximate optimal revenue for a single additive buyer with independent values. It gives a 3.52-factor guarantee and sketches a capped-welfare, second-moment proof.
1 Introduction
- The paper studies whether separate prices or a single bundle price can secure substantial revenue despite optimal mechanisms requiring lotteries and potentially infinite menus.Source: §1 · pp. 1–2
1.2 Further Related Work
- Earlier work progressed from logarithmic guarantees to a constant factor for arbitrary independent values; core–tail and duality analyses informed later bounds.Source: §1 · p. 2, §1.2 · p. 3
- Related guarantees also cover multiple XOS or subadditive buyers, dependent values, and other buyer settings, using mechanisms beyond separate selling or grand bundling.Source: §1 · p. 2, §1.2 · p. 3
1 Introduction
1.1 Technical Overview
- The proof uses duality and reduces expected non-favorite welfare to capped welfare, then compares second-moment bounds to obtain a 2.5168M bound.Source: §1.1 · pp. 2–3
- Truncating at the joint revenue scale M lets the analysis bypass the usual core–tail split and focus on a core-like capped quantity.Source: §1.1 · p. 3
2 Preliminaries
The paper studies one additive buyer with independent item values and compares optimal revenue with separate-selling and grand-bundling benchmarks.
Setting
- The model has one buyer with additive values for n independently distributed items.Each item's private value is nonnegative.Source: §2 · p. 4
Benchmarks
- OPT is the optimal expected revenue over randomized BIC and ex-post IR mechanisms.SREV sums optimal single-item revenues, while BREV is the optimal revenue from selling the grand bundle at one price.Source: §2 · p. 4
Notation
- M denotes the larger of SREV and BREV, the benchmark used to compare the two simple formats.The paper also defines V as the total bundle value and Mmax as the largest single-item value.Source: §2 · p. 4
- The item and aggregate survival functions are pj(z) = Pr(vj > z) and K(z) = sum_j pj(z).For every z > 0, zpj(z) is at most the optimal separate-selling revenue for item j.Source: §2 · p. 4
3 Proof Overview.
The proof combines a duality-based revenue bound with survival-function estimates, reduces the problem to a truncated sum, and bounds that sum through a second-moment tradeoff.
Proof roadmap
- The proof has four steps, beginning with a duality bound for BIC and ex-post IR mechanisms.It uses the duality framework of Cai, Devanur, and Weinberg.Source: §3 · p. 4
- A survival-integral estimate and the cap K(z) ≤ M/z reduce the analysis to the sum of item values truncated at M.The truncated sum is VM = sum_j min(vj, M).Source: §3 · p. 4
- Independence and single-item revenue caps bound the truncated sum's second moment, with Jensen's inequality aggregating the item bounds.The second-moment analysis uses that the truncated item values are independent.Source: §3 · p. 5
- A lower bound on the same second moment follows from the grand-bundle tail cap, and combining the bounds yields OPT ≤ SREV + 2.5168M.The resulting inequality gives OPT ≤ 3.5168M.Source: §3 · p. 5
4 Reducing OPT to the Truncated Sum
The section reduces optimal revenue to separate-selling revenue plus the expected sum of item values truncated at the benchmark M.
Duality decomposition
- The starting duality decomposition bounds optimal revenue by separate item revenues plus the expected value of non-favorite items.It is attributed to Cai, Devanur, and Weinberg.Source: §4 · p. 5
Survival integral
- Independence gives Pr(Mmax > z) ≥ 1 − e^−K(z), linking the maximum item value to the aggregate survival function.The section expresses E[V − Mmax] using the item survival probabilities.Source: §4 · p. 5
- The correction on [0, M] offsets the integral tail beyond M, leaving an upper bound by the survival integral truncated at M.The argument uses the cap K(z) ≤ M/z.Source: §4 · pp. 5–6
Reduction
- OPT ≤ SREV + E[VM], where VM is the sum of item values capped at M.This corollary follows by combining the duality decomposition with the survival-integral bound.Source: §4 · p. 6
5 Bounding the Truncated Sum via Second Moments
The section bounds the truncated sum by comparing upper and lower bounds on its second moment, obtaining a constant-factor bound on its expectation.
Upper second-moment bound
- For fixed item means, the upper second-moment bound pushes survival-curve area rightward as far as the revenue ceiling and monotonicity permit.When the mean exceeds the item's separate-selling revenue, the extremal curve has a flat portion followed by the ceiling Sj/z.Source: §5 · pp. 7–8
- Independence makes the truncated items' variances add, and Jensen's inequality aggregates their bounds into an upper bound on S2.The weights are based on each item's separate-selling revenue.Source: §5 · p. 8
Lower second-moment bound
- For fixed E[VM], the lower second-moment bound packs survival-curve area leftward under the grand-bundle tail ceiling.The extremal curve saturates the ceiling up to a cutoff.Source: §5 · pp. 8–9
Combining bounds
- Combining the second-moment bounds yields a scalar inequality in x = E[VM]/M, which forces x ≤ 2.5168.The proof substitutes the upper bound into the lower-bound inequality and rules out larger x.Source: §5 · pp. 9–10
Expected truncated sum
- 2.5168M bounds the expected truncated sum E[VM].The proof concludes that no feasible x = E[VM]/M can reach 2.5168.Source: §5 · pp. 9–10
6 Proof of the Main Theorem
Theorem 6.1 bounds optimal revenue by 3.52 times the larger of the revenues from selling separately and grand bundling.
6 Proof of the Main Theorem
- OPT ≤ 3.52 max{SREV, BREV} for a single additive buyer with n independent items.The proof invokes Corollary 4.4 and Lemma 5.3.Source: §6 · p. 10