{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T03:34:17Z","timestamp":1782185657947,"version":"3.54.5"},"reference-count":33,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>Prophet inequalities consist of many beautiful statements that establish tight performance ratios between online and offline allocation algorithms. Typically, tightness is established by constructing an algorithmic guarantee and a worst-case instance separately, whose bounds match as a result of some \u201cingenuity.\u201d In this paper, we instead formulate the construction of the worst-case instance as an optimization problem, which directly finds the tight ratio without needing to construct two bounds separately. Our analysis of this optimization problem involves identifying structure in a new \u201cType Coverage\u201d dual problem. It can be seen as akin to the celebrated Magician and OCRS (Online Contention Resolution Scheme) problems, except more general, in that it can also provide tight ratios relative to the optimal offline allocation, whereas the earlier problems only establish tight ratios relative to the ex ante relaxation of the offline problem. Through this analysis, our paper provides a unified framework that derives new prophet inequalities and recovers existing ones, with our principal results being twofold. First, we show that the \u201coblivious\u201d method of setting a static threshold due to Chawla et al., surprisingly, is best-possible among all static threshold algorithms, under any number k of selection slots. We emphasize that this result is derived without needing to explicitly find any counterexample instances. This implies the tightness of the asymptotic convergence rate of [Formula: see text] for static threshold algorithms from Hajiaghayi et al. Turning to the independent and identically distributed setting, our second principal result is to use our framework to characterize the tight guarantee (of adaptive algorithms) under any number k of selection slots and any fixed number of agents n.<\/jats:p>","DOI":"10.1287\/moor.2023.0221","type":"journal-article","created":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T11:04:36Z","timestamp":1745924676000},"page":"956-987","source":"Crossref","is-referenced-by-count":2,"title":["Tightness Without Counterexamples: A New Approach and New Results for Prophet Inequalities"],"prefix":"10.1287","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5230-4231","authenticated-orcid":false,"given":"Jiashuo","family":"Jiang","sequence":"first","affiliation":[{"name":"Department of Industrial Engineering and Decision Analytics, Hong Kong University of Science and Technology, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2420-4468","authenticated-orcid":false,"given":"Will","family":"Ma","sequence":"additional","affiliation":[{"name":"Decision, Risk, and Operations Division, Graduate School of Business, Columbia University, New York, New York 10027"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-8702-056X","authenticated-orcid":false,"given":"Jiawei","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Technology, Operations, and Statistics, Stern School of Business, New York University, New York, New York 10012"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1060.0368"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1137\/120878422"},{"key":"B3","doi-asserted-by":"crossref","unstructured":"Alaei S, Hajiaghayi M, Liaghat V (2012) Online prophet-inequality matching with applications to ad allocation.\n                      Proc. 13th ACM Conf. Electronic Commerce\n                      (Association for Computing Machinery, New York), 18\u201335.","DOI":"10.1145\/2229012.2229018"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1287\/stsy.2018.0028"},{"key":"B5","doi-asserted-by":"crossref","unstructured":"Arnosti N, Ma W (2012) Tight guarantees for static threshold policies in the prophet secretary problem.\n                      Proc. 23rd ACM Conf. Econom. Comput.\n                      (Association for Computing Machinery, New York), 242.","DOI":"10.1145\/3490486.3538377"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2021.2121"},{"key":"B7","doi-asserted-by":"crossref","unstructured":"Brustle J, Perez-Salazar S, Verdugo V (2024) Splitting guarantees for prophet inequalities via nonlinear systems. Preprint, submitted June 25, https:\/\/arxiv.org\/abs\/2406.17767.","DOI":"10.1287\/moor.2024.0413"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0604"},{"key":"B9","unstructured":"Chawla S, Devanur N, Lykouris T (2020) Static pricing for multi-unit prophet inequalities. Preprint, submitted July 15, https:\/\/arxiv.org\/abs\/2007.07990v1."},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2018.3203"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01544-8"},{"key":"B12","doi-asserted-by":"crossref","unstructured":"Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2017) Posted price mechanisms for a random stream of customers.\n                      Proc. 2017 ACM Conf. Econom. Comput\n                      . (Association for Computing Machinery, New York), 169\u2013186.","DOI":"10.1145\/3033274.3085137"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1145\/3331033.3331039"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1287\/opre.51.6.850.24925"},{"key":"B15","unstructured":"Duembgen L (2010) Bounding standard Gaussian tail probabilities. Preprint, submitted December 20, https:\/\/arxiv.org\/abs\/1012.2063."},{"key":"B16","doi-asserted-by":"crossref","unstructured":"Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids.\n                      Proc. Twenty-Ninth Annu. ACM-SIAM Sympos. Discrete Algorithms\n                      (SIAM, Philadelphia), 700\u2013714.","DOI":"10.1137\/1.9781611975031.46"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1152"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1137\/18M1226130"},{"key":"B19","doi-asserted-by":"crossref","unstructured":"Fu H, Lu P, Tang ZG, Turkieltaub A, Wu H, Wu J, Zhang Q (2022) Oblivious online contention resolution schemes.\n                      Sympos. Simplicity Algorithms SOSA\n                      (SIAM, Philadelphia), 268\u2013278.","DOI":"10.1137\/1.9781611977066.20"},{"key":"B20","unstructured":"Gallego G, Li A, Truong V-A, Wang X (2015) Online resource allocation with customer choice. Preprint, submitted November 5, https:\/\/arxiv.org\/abs\/1511.01837."},{"key":"B21","unstructured":"Hajiaghayi MT, Kleinberg R, Sandholm T (2007) Automated online mechanism design and prophet inequalities.\n                      AAAI\u201907 Proc. 22nd Natl. Conf. Artificial Intelligence\n                      , vol. 1 (AAAI Press, Cambridge, MA), 58\u201365."},{"issue":"6","key":"B22","first-page":"943","volume":"52","author":"Harremo\u00ebs P","year":"2016","journal-title":"Kybernetika"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993861"},{"key":"B24","doi-asserted-by":"crossref","unstructured":"Jiang J, Li X, Zhang J (2025) Online stochastic optimization with Wasserstein based nonstationarity.\n                      Management Sci.\n                      , ePub ahead of print March 3, https:\/\/doi.org\/10.1287\/mnsc.2020.03850.","DOI":"10.1287\/mnsc.2020.03850"},{"key":"B25","doi-asserted-by":"crossref","unstructured":"Jiang J, Ma W, Zhang J (2022) Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack.\n                      Proc. 2022 Annu. ACM-SIAM Sympos. Discrete Algorithms SODA\n                      (SIAM, Philadelphia), 1221\u20131246.","DOI":"10.1137\/1.9781611977073.51"},{"key":"B26","doi-asserted-by":"crossref","unstructured":"Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities.\n                      Proc. Forty-Fourth Annu. ACM Sympos. Theory Comput.\n                      (Association for Computing Machinery, New York), 123\u2013136,","DOI":"10.1145\/2213977.2213991"},{"key":"B27","first-page":"197","volume-title":"Probability on Banach Spaces","volume":"4","author":"Krengel U","year":"1978"},{"key":"B28","unstructured":"Lee E, Singla S (2018) Optimal online contention resolution schemes via ex-ante prophet inequalities. Preprint, submitted June 25, https:\/\/arxiv.org\/abs\/1806.09251."},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2020.3671"},{"key":"B30","unstructured":"Perez-Salazar S, Singh M, Toriello A (2022) The IID prophet inequality with limited flexibility. Preprint, submitted October 11, https:\/\/arxiv.org\/abs\/2210.05634v1."},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993150"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1080\/02331930902730070"},{"key":"B33","doi-asserted-by":"crossref","unstructured":"Yan Q (2011) Mechanism design via correlation gap.\n                      Proc. Twenty-Second Annu. ACM-SIAM Sympos. Discrete Algorithms\n                      (SIAM, Philadelphia), 710\u2013719.","DOI":"10.1137\/1.9781611973082.56"}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2023.0221","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:26:07Z","timestamp":1778228767000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2023.0221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/moor.2023.0221"],"URL":"https:\/\/doi.org\/10.1287\/moor.2023.0221","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}