# LP-based Approximation for Personalized Reserve Prices

arXiv: https://arxiv.org/abs/1905.01526 · HTML: https://mlsanity.com/paper/1905.01526/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2019.

## Built on by (most cited first, 3 of 3)

- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Learning and Collusion in Multi-unit Auctions](https://mlsanity.com/paper/2305.17402/) (2023)
- [Learning in Repeated Multi-Unit Pay-As-Bid Auctions](https://mlsanity.com/paper/2307.15193/) (2023)

## Abstract (arXiv)

We study the problem of computing data-driven personalized reserve prices in eager second price auctions without having any assumption on valuation distributions. Here, the input is a data-set that contains the submitted bids of n buyers in a set of auctions and the problem is to return personalized reserve prices textbf r that maximize the revenue earned on these auctions by running eager second price auctions with reserve textbf r. For this problem, which is known to be APX-hard, we present a novel LP formulation and a rounding procedure which achieves a (1+2(√2-1)e^√2-2)-1 ≈ 0.684-approximation. This improves over the frac12-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 shows that it is impossible to design an algorithm that yields an approximation factor larger than 0.828 with respect to this LP.