Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
A Simple and Approximately Optimal Mechanism for an Additive Buyer

Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg


We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer has a value for each item drawn independently according to (non-identical) distributions, and his value for a set of items is additive. The seller aims to maximize his revenue. It is known that an optimal mechanism in this setting may be quite complex, requiring randomization [HR12] and menus of infinite size [DDT13]. Hart and Nisan [HN12] have initiated a study of two very simple pricing schemes for this setting: item pricing, in which each item is priced at its monopoly reserve; and bundle pricing, in which the entire set of items is priced and sold as one bundle. Hart and Nisan [HN12] have shown that neither scheme can guarantee more than a vanishingly small fraction of the optimal revenue. In sharp contrast, we show that for any distributions, the better of item and bundle pricing is a constant-factor approximation to the optimal revenue. We further discuss extensions to multiple buyers and to valuations that are correlated across items.


Publication typeInproceedings
Published inSymposium on Foundations of Computer Science (FOCS 2014)
PublisherIEEE – Institute of Electrical and Electronics Engineers
> Publications > A Simple and Approximately Optimal Mechanism for an Additive Buyer