Beating Greedy For Approximating Reserve Prices in Multi-Unit VCG Auctions

We study the problem of finding personalized reserve prices for unit-demand buyers in multi-unit eager VCG auctions with correlated buyers. The input to this problem is a dataset of submitted bids of n buyers in a set of auctions. The goal is to find a vector of reserve prices, one for each buyer, that maximizes the total revenue across all auctions. Roughgarden and Wang (2016) showed that this problem is APX-hard but admits a greedy frac12-approximation algorithm. Later, Derakhshan, Golrezai, and Paes Leme (2019) gave an LP-based algorithm achieving a 0.68-approximation for the (important) special case of the problem with a single-item, thereby beating greedy. We show in this paper that the algorithm of Derakhshan et al. in fact does not beat greedy for the general multi-item problem. This raises the question of whether or not the general problem admits a better-than-frac12 approximation. In this paper, we answer this question in the affirmative and provide a polynomial-time algorithm with a significantly better approximation-factor of 0.63. Our solution is based on a novel linear programming formulation, for which we propose two different rounding schemes. We prove that the best of these two and the no-reserve case (all-zero vector) is a 0.63-approximation.