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 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.