Pricing lotteries

• 成果类型: Article
• 署名作者: Briest, Patrick; Chawla, Shuchi; Kleinberg, Robert; Weinberg, S. Matthew
• 署名单位: University of Paderborn; University of Wisconsin System; University of Wisconsin Madison; Cornell University; Massachusetts Institute of Technology (MIT)
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2014.04.011
• 发表日期: 2015
• 页码: 144-174
• 关键词: Revenue maximization; Unit-demand; 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. (C) 2014 Published by Elsevier Inc.