The power of randomness in Bayesian optimal mechanism design

Shuchi Chawla, David Malec and Balasubramanian Sivan

Games and Economic Behavior, 2015, vol. 91, issue C, 297-317

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

Keywords: Mechanism design; Randomness; Revenue; Lotteries; Screening; Multi-product pricing (search for similar items in EconPapers)
JEL-codes: D42 D44 D82 (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899825612001303
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:91:y:2015:i:c:p:297-317

DOI: 10.1016/j.geb.2012.08.010

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().