The power of randomness in Bayesian optimal mechanism design

► We study the benefit of randomness in optimal multi-dimensional mechanism design. ► We bound the ratio of revenues of the optimal randomized and deterministic mechanisms. ► For one agent with independent values for multiple items, this ratio is at most 4. ► In contrast, prior work showed the ratio is unbounded with arbitrary correlation. ► Our bounds extend to settings with multiple agents and a certain form of correlation.