LP-based Approximation for Personalized Reserve Prices
share
We study the problem of computing revenue-optimal personalize (non-anonymous) reserve prices in eager second price auction in a single-item environment without having any assumption on valuation distributions. Here, the input is a dataset that contains the submitted bids of n buyers in a set of auctions and the goal is to return personalized reserve prices ṟ that maximize the revenue earned on these auctions by running eager second price auctions with reserve ṟ. We present a novel LP formulation to this problem and a rounding procedure which achievesOur main result in a polynomial-time LP-based algorithm that achieves a (1+2(√(2)-1)e^√(2)-2)^-1≈-approximation. This improves over the 12-approximation algorithm due to Roughgarden and Wang. We show that our analysis is tight for this rounding procedure. We also bound the integrality gap of the LP, which bounds the performance of any algorithm based on this LP.and obtains the best known approximation ratio even for the special case of independent distributions.
READ FULL TEXT