Computer Science – Computer Science and Game Theory
Scientific paper
2010-02-20
Computer Science
Computer Science and Game Theory
Minor formatting changes
Scientific paper
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 [Myerson '81] 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. [Briest, Chawla, Kleinberg, and Weinberg '10] 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 additive values) is a natural model for unit-demand agents and items that are substitutes. Our results extend to multiple agent settings as well.
Chawla Shuchi
Malec David
Sivan Balasubramanian
No associations
LandOfFree
The power of randomness in Bayesian optimal mechanism design does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The power of randomness in Bayesian optimal mechanism design, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The power of randomness in Bayesian optimal mechanism design will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-692683