  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.
