Minimizing Regret with Multiple Reserves

摘要

We study the problem of computing and learning non-anonymous reserve prices to maximize revenue. We first define the Maximizing Multiple Reserves (MMR) problem in single-parameter matroid environments, where the input ism 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.