Gregory Kehne, Washington University, St. Louis

Abstract

We study multi-buyer multi-item sequential item pricing mechanisms for revenue maximization with the goal of approximating a natural fractional relaxation -- the ex ante optimal revenue. We assume that buyers' values are subadditive but make no assumptions on the value distributions. While the optimal revenue, and therefore also the ex ante benchmark, is inapproximable by any simple mechanism in this context, previous work has shown that a weaker benchmark that optimizes over so-called ``buy-many" mechanisms can be approximable. Approximations are known, in particular, for settings with either a single buyer or many unit-demand buyers. We extend these results to the much broader setting of many subadditive buyers. We show that the ex ante buy-many revenue can be approximated via sequential item pricings to within an O(log^2 m) factor, where m is the number of items. We also show that a logarithmic dependence on m is necessary.

This is joint work with Shuchi Chawla, Dimitris Christou, Trung Dang, Zhiyi Huang, and Rojin Rezvan, and appeared at SODA 2025.

See: https://theory.cs.rutgers.edu/theory_seminar