OpenAlex ·

A Bulow-Klemperer Theorem for Bundling and Improved Approximation Bounds for Simple Auctions

Yichen Huang

Published
Source
OpenAlex
Published in
arXiv (Cornell University)
DOI
10.48550/arxiv.2610.24973
Original
Read it at the publisher
Topics
Computational ComplexityEconometricsGeneral EconomicsOptimization & Control

Abstract

We study simple auctions for one additive bidder whose values for $m$ items are independent. Write $\mathrm{REV}$ for the optimal revenue, $\mathrm{SREV}$ and $\mathrm{BREV}$ for the optimal revenues from separate selling and grand bundling, and $\mathrm{BSPA}_2$ for the grand-bundle second-price revenue with two independent bidders. For independent regular items, we prove $\mathrm{REV} \le \mathrm{BSPA}_2 \le 2\,\mathrm{BREV}$. Thus, one additional bidder lets a reserve-free second-price auction for the grand bundle match the optimal revenue from one bidder, regardless of the number of items. This gives a Bulow-Klemperer theorem for bundling and resolves an open question of Beyhaghi, Cai, Feng, Li, and Weinberg (EC 2025) on whether constant competition suffices for bundling. The factor-$2$ bundling approximation is also tight. 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). For the lower bound, we construct an instance in which pricing three disjoint bundles earns more than $2.11\max\{\mathrm{SREV},\mathrm{BREV}\}$, improving the previous lower bound of $2$ from Rubinstein (ITCS 2016). Together, these results narrow the tight approximation ratio to the range $[2.11, 2.645]$.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Computational Complexity

Get the few papers worth your time in Computational Complexity every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics