← 研踪 PaperTrailarXiv:2610.24973 · v2
A Bulow-Klemperer Theorem for Bundling and Improved Approximation Bounds for Simple Auctions
首次提交 2026-10-18 11:09
版本更新 2026-11-04 05:56
雷达观测 2026-11-05 10:08
摘要
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]$.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-04 05:56 · 最新观测版本
A Bulow-Klemperer Theorem for Bundling and Improved Approximation Bounds for Simple Auctions
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]$.
查看此版本解读 →查看此版本原文 ↗