The power of randomness in Bayesian optimal mechanism design

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.