Improved Approximation and Tight Competition for Simple Auctions

We study simple auctions for one additive buyer whose values for $m$ items are independent. Write $\mathrm{R}\mathrm{E}\mathrm{V}$ for optimal revenue, $\mathrm{S}\mathrm{R}\mathrm{E}\mathrm{V}$ and $\mathrm{B}\mathrm{R}\mathrm{E}\mathrm{V}$ for the revenues from separate selling and grand bundling, and ${\mathrm{B}\mathrm{S}\mathrm{P}\mathrm{A}}_2$ for grand-bundle second-price revenue with two independent bidders. For independent regular items, we prove $\mathrm{R}\mathrm{E}\mathrm{V}\le {\mathrm{B}\mathrm{S}\mathrm{P}\mathrm{A}}_2\le 2\mathrm{B}\mathrm{R}\mathrm{E}\mathrm{V}$. 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{R}\mathrm{E}\mathrm{V}\le \mathrm{S}\mathrm{R}\mathrm{E}\mathrm{V}+\frac{{\pi }^2}{6}\mathrm{B}\mathrm{R}\mathrm{E}\mathrm{V}\le 2.645\max \{\mathrm{S}\mathrm{R}\mathrm{E}\mathrm{V},\mathrm{B}\mathrm{R}\mathrm{E}\mathrm{V}\}$. 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{S}\mathrm{R}\mathrm{E}\mathrm{V},\mathrm{B}\mathrm{R}\mathrm{E}\mathrm{V}\}$, 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 $\mathrm{\Theta }(\log m)$ bidders in the worst case.