The power of randomness in bayesian optimal mechanism design
- 7 June 2010
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 149-158
- https://doi.org/10.1145/1807342.1807366
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 [14] shows that randomness offers no benefit - the optimal mechanism is always deterministic. In the multi-dimensional case, where each agent's preferences are given by different values for each of the available services, Briest et al.[6] recently 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. However, this large gap is attained through unnatural instances where values of the agent for different services are correlated in a specific way. We show that when the agent's values involve no correlation or a specific kind of positive correlation, the benefit of randomness is only a small constant factor (4 and 8 respectively). Our model of positively correlated values (that we call the common base value model) is a natural model for unit-demand agents and items that are substitutes. Our results extend to multiple agent settings as well.Keywords
Other Versions
This publication has 15 references indexed in Scilit:
- Multidimensional mechanism design: Revenue maximization and the multiple-good monopolyJournal of Economic Theory, 2007
- Profit Maximization in Mechanism DesignPublished by Cambridge University Press (CUP) ,2007
- Algorithmic pricing via virtual valuationsPublished by Association for Computing Machinery (ACM) ,2007
- Bundling as an optimal selling mechanism for a multiple-good monopolistJournal of Economic Theory, 2006
- Haggling over substitutesJournal of Economic Theory, 2004
- Ironing, Sweeping, and Multidimensional ScreeningEconometrica, 1998
- Multidimensional incentive compatibility and mechanism designJournal of Economic Theory, 1988
- Optimal Selling Strategies: When to Haggle, When to Hold FirmThe Quarterly Journal of Economics, 1983
- Optimal Auction DesignMathematics of Operations Research, 1981
- Comments on bases in dependence structuresBulletin of the Australian Mathematical Society, 1969