Papers for

online ad auction developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Tighter bounds on revenue from simple auctions with independent items

Improved Approximation and Tight Competition for Simple Auctions

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.

Sun 18 OctComputer Science and Game Theory
The gist
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.
Open → 2610.24973v1