Improved Approximation and Tight Competition for Simple Auctions

Yichen Huang

Papers from arXiv.org

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{\pi^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 $\Theta(\log m)$ bidders in the worst case.

Date: 2026-10
New Economics Papers: this item is included in nep-com and nep-des
References: Add references at CitEc
Citations:

Downloads: (external link)
https://arxiv.org/pdf/2610.24973 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2610.24973

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().