Search for: All records

We study the problem of computing and learning non-anonymous reserve prices to maximize revenue. We first define the M aximizing M ultiple R eserves (MMR) problem in single-parameter matroid environments, where the input is m valuation profiles v 1 ,…, v m , indexed by the same n bidders, and the goal is to compute the vector r of (non-anonymous) reserve prices that maximizes the total revenue obtained on these profiles by the VCG mechanism with reserves r . We prove that the problem is APX -hard, even in the special case of single-item environments, and give a polynomial-time 1/2-approximation algorithm for it in arbitrary matroid environments. We then consider the online no-regret learning problem and show how to exploit the special structure of the MMR problem to translate our offline approximation algorithm into an online learning algorithm that achieves asymptotically time-averaged revenue at least 1/2 times that of the best fixed reserve prices in hindsight. On the negative side, we show that, quite generally, computational hardness for the offline optimization problem translates to computational hardness for obtaining vanishing time-averaged regret. Thus, our hardness result for the MMR problem implies that computationally efficient online learning requires approximation, even in the special case of single-item auction environments. 

The field of optimal mechanism design enjoys a beautiful and well-developed theory, as well as several killer applications. Rules of thumb produced by the field influence everything from how governments sell wireless spectrum licenses to how the major search engines auction off online advertising. There are, however, some basic problems for which the traditional optimal mechanism design approach is ill suited—either because it makes overly strong assumptions or because it advocates overly complex designs. This article reviews several common issues with optimal mechanisms, including exorbitant communication, computation, and informational requirements; it also presents several examples demonstrating that relaxing the goal to designing an approximately optimal mechanism allows us to reason about fundamental questions that seem out of reach of the traditional theory.