{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T14:10:12Z","timestamp":1723731012177},"reference-count":8,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2024,8]]},"abstract":" We study the competition complexity of dynamic pricing relative to the optimal auction in the fundamental single-item setting. In prophet inequality terminology, we compare the expected reward [Formula: see text] achievable by the optimal online policy on m independent and identically distributed (i.i.d.) random variables distributed according to F to the expected maximum [Formula: see text] of n i.i.d. draws from F. We ask how big m has to be to ensure that [Formula: see text] for all F. We resolve this question and characterize the competition complexity as a function of \u03b5. When [Formula: see text], the competition complexity is unbounded. That is, for any n and m there is a distribution F such that [Formula: see text]. In contrast, for any [Formula: see text], it is sufficient and necessary to have [Formula: see text], where [Formula: see text]. Therefore, the competition complexity not only drops from unbounded to linear, it is actually linear with a very small constant. The technical core of our analysis is a lossless reduction to an infinite dimensional and nonlinear optimization problem that we solve optimally. A corollary of this reduction is a novel proof of the factor [Formula: see text] i.i.d. prophet inequality, which simultaneously establishes matching upper and lower bounds. <\/jats:p> Funding: This work was supported by ANID (Anillo ICMD) [Grant ACT210005] and the Center for Mathematical Modeling [Grant FB210005]. <\/jats:p>","DOI":"10.1287\/moor.2022.0230","type":"journal-article","created":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T05:47:16Z","timestamp":1697780836000},"page":"1986-2008","source":"Crossref","is-referenced-by-count":0,"title":["The Competition Complexity of Dynamic Pricing"],"prefix":"10.1287","volume":"49","author":[{"given":"Johannes","family":"Brustle","sequence":"first","affiliation":[{"name":"Department of Mathematics, London School of Economics and Political Science, London WC2A 2AE, United Kingdom;"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-3012-7622","authenticated-orcid":false,"given":"Jos\u00e9","family":"Correa","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering, Universidad de Chile, Santiago 8330111, Chile;"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-0635-6812","authenticated-orcid":false,"given":"Paul","family":"Duetting","sequence":"additional","affiliation":[{"name":"Google Research, 8002 Z\u00fcrich, Switzerland;"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-0817-7356","authenticated-orcid":false,"given":"Victor","family":"Verdugo","sequence":"additional","affiliation":[{"name":"Institute of Engineering Sciences, Universidad de O\u2019Higgins, O\u2019Higgins 2820000, Chile"}]}],"member":"109","reference":[{"issue":"1","key":"B4","first-page":"180","volume":"86","author":"Bulow J","year":"1996","journal-title":"Amer. Econom. Rev."},{"doi-asserted-by":"publisher","key":"B9","DOI":"10.1016\/j.orl.2018.11.010"},{"doi-asserted-by":"publisher","key":"B10","DOI":"10.1287\/moor.2020.1105"},{"doi-asserted-by":"publisher","key":"B17","DOI":"10.1080\/01621459.1966.10502008"},{"doi-asserted-by":"publisher","key":"B21","DOI":"10.1214\/aop\/1176993861"},{"key":"B30","first-page":"289","volume":"22","author":"Moser L","year":"1956","journal-title":"Scripta Math."},{"doi-asserted-by":"publisher","key":"B31","DOI":"10.1287\/moor.6.1.58"},{"key":"B32","first-page":"217","volume":"9","author":"Picard E","year":"1893","journal-title":"J. Math. Pures Appl."}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2022.0230","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T13:37:01Z","timestamp":1723729021000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2022.0230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8]]},"references-count":8,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["10.1287\/moor.2022.0230"],"URL":"https:\/\/doi.org\/10.1287\/moor.2022.0230","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"type":"print","value":"0364-765X"},{"type":"electronic","value":"1526-5471"}],"subject":[],"published":{"date-parts":[[2024,8]]}}}