Linear Program-Based Approximation for Personalized Reserve Prices

Mahsa Derakhshan (), Negin Golrezaei () and Renato Paes Leme ()
Additional contact information
Mahsa Derakhshan: Department of Computer Science, University of Maryland, College Park, Maryland 20742
Negin Golrezaei: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Renato Paes Leme: Google Research, New York, New York 10011

Management Science, 2022, vol. 68, issue 3, 1849-1864

Abstract: 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 r that maximize the revenue earned on these auctions by running eager second price auctions with reserve r . For this problem, which is known to be NP complete, we present a novel linear program (LP) formulation and a rounding procedure, which achieves a 0.684 approximation. This improves over the 1 2 -approximation algorithm from 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.

Keywords: data-driven optimization; personalized reserve prices; eager second price auctions; LP-based algorithm (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2020.3897 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:68:y:2022:i:3:p:1849-1864

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().