Improved Revenue Guarantees for Selling Separately and Bundling

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 OPT ≤ 3.52 maxSREV, BREV, where SREV and BREV 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.