The power of randomness in Bayesian optimal mechanism design

• 成果类型: Article
• 署名作者: Chawla, Shuchi; Malec, David; Sivan, Balasubramanian
• 署名单位: University of Wisconsin System; University of Wisconsin Madison
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2012.08.010
• 发表日期: 2015
• 页码: 297-317
• 关键词: Mechanism design; randomness; revenue; lotteries; screening; Multi-product pricing

摘要

We investigate the power of randomness in the context of a fundamental Bayesian optimal mechanism design problem a single seller aims to maximize expected revenue by allocating multiple kinds of resources to unit-demand agents with preferences drawn from a known distribution. When the agents' preferences are single-dimensional Myerson's seminal work (1981) shows that randomness offers no benefit the optimal mechanism is always deterministic. In the multi-dimensional case, when agents' preferences are arbitrarily correlated, Briest et al. (2010) showed that the gap between the expected revenue obtained by an optimal randomized mechanism and an optimal deterministic mechanism can be unbounded even when a single agent is offered only 4 services. We show that when the agents' values involve no correlation or a specific kind of positive correlation, the benefit of randomness is only a small constant factor. (C) 2012 Elsevier Inc. All rights reserved.