Linear Program-Based Approximation for Personalized Reserve Prices

• 成果类型: Article
• 署名作者: Derakhshan, Mahsa; Golrezaei, Negin; Leme, Renato Paes
• 署名单位: University System of Maryland; University of Maryland College Park; Massachusetts Institute of Technology (MIT); Alphabet Inc.; Google Incorporated
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2020.3897
• 发表日期: 2022
• 页码: 1849-1864
• 关键词: data-driven optimization; personalized reserve prices; eager second price auctions; LP-based algorithm

摘要

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 1approximation algorithm from Rough-garden 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.