Improved Revenue Guarantees for Selling Separately and Bundling

Yang Cai; Vineet Gupta; Yanchen Jiang; Christopher Liaw; Aranyak Mehta; Grigoris Velegkas; Di Wang

In the authors' words

We study how much revenue a seller can lose by restricting attention to selling separately or grand bundling, in the setting of a single additive buyer with independent item values. Although revenue-optimal mechanisms can require lotteries and infinite menus, Babaioff, Immorlica, Lucier, and Weinberg showed that the better of these two simple formats always achieves a constant fraction of optimal revenue. We prove that $O P T \leq 3.52 max {S R E V, B R E V}$ , where $S R E V$ and $B R E V$ are the optimal revenues from selling separately and grand bundling, respectively. This improves the previous best-known approximation factor of $5.2$ due to Ma and Simchi-Levi and narrows the gap to the known lower bound of $2$ .

Main resultLimitation the authors admit

Improved Revenue Guarantees for Selling Separately and Bundling

In the authors' words

More on Algorithms & complexity that day

A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond N4/3

A General Composition Theorem for Approximate Degree

Practical and Space-Efficient LZ77 and LZ Pre-Compression via String Synchronizing Sets

Sharp Lovasz-Theta Bounds on Random Graphs

A Human-Like Pedestrian Model for Automated Driving Simulations

A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$