Tighter bounds on revenue from simple auctions with independent items
Improved Approximation and Tight Competition for Simple Auctions
Computer Science and Game Theory
Summary
Selling multiple items to one buyer can be done in simple ways like selling items separately or all together as a bundle. The authors study how well these simple ways do compared to the best possible method for maximizing seller revenue. They show better and tighter mathematical limits on how close these simple methods can get to the best. They also explore scenarios with multiple bidders and how many bidders are needed for simple methods to be optimal.
What this means in practice
- •For ecommerce platform designers: Design pricing strategies for selling multiple independent items more effectively using tighter revenue bounds from simple auctions.
- •For online ad auction developers: Improve auction formats by applying tight competition guarantees for bundling in auctions involving independent valuations.
A theory result. No direct application yet.
Authors
Yichen Huang
Abstract
We study simple auctions for one additive buyer whose values for $m$ items are independent. Write $\mathrm{REV}$ for optimal revenue, $\mathrm{SREV}$ and $\mathrm{BREV}$ for the revenues from separate selling and grand bundling, and $\mathrm{BSPA}_2$ for grand-bundle second-price revenue with two independent bidders. For independent regular items, we prove $\mathrm{REV}\le\mathrm{BSPA}_2\le2\mathrm{BREV}$. This establishes tight approximation and competition guarantees for bundling under regularity and answers an open question from Beyhaghi et al. (EC 2025). For general independent items, we prove $\mathrm{REV} \le \mathrm{SREV} + \frac{π^2}{6}\mathrm{BREV} \le 2.645 \max\{\mathrm{SREV}, \mathrm{BREV}\}$. This improves the previous approximation factors of $6$ from Babaioff, Immorlica, Lucier, and Weinberg (FOCS 2014, JACM 2020) and $5.2$ from Ma and Simchi-Levi (AISTATS 2021). On the lower bound side, we construct an instance in which prices for three disjoint bundles earn more than $2.11\max\{\mathrm{SREV},\mathrm{BREV}\}$, improving the previous lower bound of $2$ from Rubinstein (ITCS 2016). We also show that exact recovery of one buyer's optimal revenue by the better of separate selling and bundling requires $Θ(\log m)$ bidders in the worst case.