Linear Program-Based Approximation for Personalized Reserve Prices
<jats:p> 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 ret...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2022
|
| Online Access: | https://hdl.handle.net/1721.1/144168 |
| _version_ | 1826193335877894144 |
|---|---|
| author | Derakhshan, Mahsa Golrezaei, Negin Paes Leme, Renato |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Derakhshan, Mahsa Golrezaei, Negin Paes Leme, Renato |
| author_sort | Derakhshan, Mahsa |
| collection | MIT |
| description | <jats:p> 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 [Formula: see text]-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. </jats:p><jats:p> This paper was accepted by Chung Piaw Teo, Management Science Special Section on Data-Driven Prescriptive Analytics. </jats:p> |
| first_indexed | 2024-09-23T09:37:26Z |
| format | Article |
| id | mit-1721.1/144168 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:37:26Z |
| publishDate | 2022 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/1441682023-03-30T20:42:41Z Linear Program-Based Approximation for Personalized Reserve Prices Derakhshan, Mahsa Golrezaei, Negin Paes Leme, Renato Sloan School of Management <jats:p> 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 [Formula: see text]-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. </jats:p><jats:p> This paper was accepted by Chung Piaw Teo, Management Science Special Section on Data-Driven Prescriptive Analytics. </jats:p> 2022-08-01T14:47:29Z 2022-08-01T14:47:29Z 2022 2022-08-01T14:42:17Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/144168 Derakhshan, Mahsa, Golrezaei, Negin and Paes Leme, Renato. 2022. "Linear Program-Based Approximation for Personalized Reserve Prices." Management Science, 68 (3). en 10.1287/MNSC.2020.3897 Management Science Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) arXiv |
| spellingShingle | Derakhshan, Mahsa Golrezaei, Negin Paes Leme, Renato Linear Program-Based Approximation for Personalized Reserve Prices |
| title | Linear Program-Based Approximation for Personalized Reserve Prices |
| title_full | Linear Program-Based Approximation for Personalized Reserve Prices |
| title_fullStr | Linear Program-Based Approximation for Personalized Reserve Prices |
| title_full_unstemmed | Linear Program-Based Approximation for Personalized Reserve Prices |
| title_short | Linear Program-Based Approximation for Personalized Reserve Prices |
| title_sort | linear program based approximation for personalized reserve prices |
| url | https://hdl.handle.net/1721.1/144168 |
| work_keys_str_mv | AT derakhshanmahsa linearprogrambasedapproximationforpersonalizedreserveprices AT golrezaeinegin linearprogrambasedapproximationforpersonalizedreserveprices AT paeslemerenato linearprogrambasedapproximationforpersonalizedreserveprices |