Approximation Schemes for Revenue Maximization with Multiple Subadditive Buyers

Abstract

We consider the problem of revenue maximization for a single monopolistic seller with $n$ independent items facing $m$ independent buyers. Our main technical result reduces finding a $(1 - O(\varepsilon))$-approximation to revenue maximization for a distribution over unbounded subadditive valuations to finding a $(1 - \varepsilon)$-approximation when the values are (almost) bounded and still subadditive. We use this reduction to show a quasi-polynomial time approximation scheme for multiple $k$-demand buyers who have constant support per item.

Along the way, we introduce several theoretical notions---modified revenue maximization, leftovers of an interim menu, making buyers exclusive above a threshold, and extending an interim menu with exclusive options---that might be of independent interest to mechanism designers.