CATS-Feb-15-2013
Title
Approximations in Bayesian optimal multi-dimensional mechanism design
Speaker
David Malec
Abstract
We will consider the classical problem of Bayesian (revenue-)optimal mechanism design. Here, a seller with a set of items wants to design a protocol to sell them to a set of potential buyers, who have various preferences among the items. The seller wants to maximize expected revenue given distributional information on how the buyers value each item. If the seller had only one item, a seminal result of Myerson (1981) exactly characterizes the optimal mechanism for this setting. Unfortunately, this optimal mechanism can be complicated and impractical; furthermore, the characterization fails to generalize to settings where there are multiple items, and buyers have distinct values for different items. We instead consider a class of mechanisms called sequential posted-pricings for selling items. As we shall see, these mechanisms are approximately optimal, and are simple, practical, and extremely robust to collusion among buyers. Furthermore, their nice properties allow us to extend our approximations to unit-demand multi-item settings, where buyers have different values for different items but want to receive at most one item. One aspect of multi-item mechanism design we give special attention to is the benefit of randomness. While Myerson's characterization shows that deterministic mechanisms can achieve optimal revenue in single-item settings, this is not true in multi-item ones. In fact, when buyers' values for different items may exhibit arbitrary correlation, Briest et al. (2010) demonstrated an unbounded gap between optimal randomized and optimal deterministic mechanisms, even with just four items and a single buyer. We shall see, however, that with independent values the benefit of randomness is bounded by a constant.