Abstract
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 her value for a set of items is additive. The seller aims to maximize her revenue. It is known that an optimal mechanism in this setting may be quite complex, requiring randomization and menus of infinite size. Hart and Nisan 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 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 yields a 6-approximation to the optimal revenue. We further extend this result to settings where the buyer has a valuation function that is just subadditive, but "independent across items," showing that the better of item and bundle pricing still yields a constant-factor approximation.
Based on joint works with Moshe Babaioff, Nicole Immorlica and Brendan Lucier, and Aviad Rubinstein.