Pricing lotteries

We examine optimal mechanisms for a multi-product monopolist selling n substitutable goods to a buyer of unknown type randomly sampled from a known distribution. The optimal selling strategy assigns posted prices to lotteries (probability distributions over items), and it is known that pricing lotteries can be strictly superior to pricing individual items. Our results quantify the magnitude of this phenomenon and shed light on the computational hardness of determining (or approximating) the optimal selling strategy. In particular, we show that when the number of items is at least three, there is no finite upper bound on the ratio between the maximum revenue attainable by pricing lotteries and that which can be attained by pricing items. Furthermore, the time required to compute the optimal selling strategy is polynomial in the support size of the buyer's type distribution. We also show that these two results are reversed in a model in which the buyer is allowed to buy any desired number of lotteries and receive an independent sample from each: the ratio between the revenue of the optimal selling strategy and that which can be attained by pricing items is only logarithmic in the number of goods n, and under standard complexity-theoretic assumptions there is no polynomial-time algorithm to compute or even approximate the optimal selling strategy.