{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T14:45:30Z","timestamp":1772635530079,"version":"3.50.1"},"reference-count":68,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"name":"Harvard University Center of Mathematical Sciences and Applications"},{"name":"Amazon"},{"name":"TAU Center for AI and Data Science"},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["866132"],"award-info":[{"award-number":["866132"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF-BSF","doi-asserted-by":"publisher","award":["2020788"],"award-info":[{"award-number":["2020788"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100021154","name":"Amazon Research Award","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100021154","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007229","name":"Harvard University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007229","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2600\/24"],"award-info":[{"award-number":["2600\/24"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"National Key R&D Program of China","doi-asserted-by":"publisher","award":["2023YFA1009500"],"award-info":[{"award-number":["2023YFA1009500"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62572291"],"award-info":[{"award-number":["62572291"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2026,4,30]]},"DOI":"10.1137\/24m1708917","type":"journal-article","created":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T08:01:40Z","timestamp":1772611300000},"page":"332-361","source":"Crossref","is-referenced-by-count":0,"title":["Order-Competitive Ratio"],"prefix":"10.1137","volume":"55","author":[{"given":"Liyan","family":"Chen","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomer","family":"Ezra","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, MA USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Feldman","sequence":"additional","affiliation":[{"name":"School of Computer Science and AI, Tel Aviv University, Tel Aviv, Israel."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nick","family":"Gravin","sequence":"additional","affiliation":[{"name":"Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics, Shanghai, China."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nuozhou","family":"Sun","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5094-1971","authenticated-orcid":true,"given":"Zhihao Gavin","family":"Tang","sequence":"additional","affiliation":[{"name":"Corresponding author.\u00a0Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics, Shanghai, China."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"351","published-online":{"date-parts":[[2026,3,4]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"A. Agarwal, S. Assadi, and S. Khanna, Stochastic submodular cover with limited adaptivity, in Proceedings of the 2019 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2019, pp. 323\u2013342.","DOI":"10.1137\/1.9781611975482.21"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"S. Agrawal, J. Sethuraman, and X. Zhang, On optimal ordering in the optimal stopping problem, in EC \u201920: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, 2020, J. D. Hartline, M. Ostrovsky, and A. D. Procaccia, eds. ACM, New York, 2020, pp. 187\u2013188.","DOI":"10.1145\/3391403.3399484"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1017\/jpr.2016.63"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"M. Arsenis, O. Drosis, and R. Kleinberg, Constrained-order prophet inequalities, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2021, pp. 2034\u20132046.","DOI":"10.1137\/1.9781611976465.121"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"P. D. Azar, R. Kleinberg, and S. M. Weinberg, Prophet inequalities with limited information, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2014, pp. 1358\u20131377.","DOI":"10.1137\/1.9781611973402.100"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"Y. Azar, A. Chiplunkar, and H. Kaplan, Prophet secretary: Surpassing the 1-1\/e barrier, in Proceedings of the 2018 ACM Conference on Economics and Computation, ACM, New York, 2018, pp. 303\u2013318.","DOI":"10.1145\/3219166.3219182"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9511-8"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0927-9"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2021.2121"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"M. Braverman, M. Derakhshan, and A. Molina Lovett, Max-weight online stochastic matching: Improved approximations against the online benchmark, in Proceedings of the 23rd ACM Conference on Economics and Computation, ACM, New York, 2022, pp. 967\u2013985.","DOI":"10.1145\/3490486.3538315"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"M. Braverman, M. Derakhshan, T. Pollner, A. Saberi, and D. Wajc, New philosopher inequalities for online Bayesian matching, via pivotal sampling, in Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2025, pp. 3029\u20133068.","DOI":"10.1137\/1.9781611978322.98"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"A. Bubna and A. Chiplunkar, Prophet inequality:\u00a0Order selection beats random order, in ACM Conference on Economics and Computation, ACM, New York, 2023, pp. 302\u2013336, https:\/\/doi.org\/10.1145\/3580507.3597687.","DOI":"10.1145\/3580507.3597687"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"C. Caramanis, P. D\u00fctting, M. Faw, F. Fusco, P. Lazos, S. Leonardi, O. Papadigenopoulos, E. Pountourakis, and R. Reiffenh\u00e4user, Single-sample prophet inequalities via greedy-ordered selection, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2022, pp. 1298\u20131325.","DOI":"10.1137\/1.9781611977073.54"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"C. Caramanis, P. D\u00fctting, M. Faw, F. Fusco, P. Lazos, S. Leonardi, O. Papadigenopoulos, E. Pountourakis, and R. Reiffenh\u00e4user, Single-sample prophet inequalities via greedy-ordered selection, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Virtual Conference \/ Alexandria, 2022, pp. 1298\u20131325.","DOI":"10.1137\/1.9781611977073.54"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2023.1363"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"J. Correa, A. Cristi, L. Feuilloley, T. Oosterwijk, and A. Tsigonias-Dimitriadis, The secretary problem with independent sampling, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2021, pp. 2047\u20132058.","DOI":"10.1137\/1.9781611976465.122"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"J. Correa, P. D\u00fctting, F. Fischer, and K. Schewior, Prophet inequalities for i.i.d.\u00a0random variables from an unknown distribution, in Proceedings of the 2019 ACM Conference on Economics and Computation, EC, ACM, New York, 2019, pp. 3\u201317.","DOI":"10.1145\/3328526.3329627"},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"J. R. Correa, A. Cristi, B. Epstein, and J. A. Soto, The two-sided game of Googol and sample-based prophet inequalities, in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2020, pp. 2066\u20132081.","DOI":"10.1137\/1.9781611975994.127"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01544-8"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"A. Cristi and B. Ziliotto, Prophet inequalities require only a constant number of samples, in Proceedings of the 56th Annual ACM Symposium on Theory of Computing, ACM, New York, 2024, pp. 491\u2013502.","DOI":"10.1145\/3618260.3649773"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0330"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/20M1323850"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1145\/3440968.3440972"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_37"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"P. D\u00fctting, S. Lattanzi, R. Paes Leme, and S. Vassilvitskii, Secretaries with advice, in Proceedings of the 22nd ACM Conference on Economics and Computation, ACM, New York, 2021, pp. 409\u2013429.","DOI":"10.1145\/3465456.3467623"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"S. Ehsani, M. Hajiaghayi, T. Kesselheim, and S. Singla, Prophet secretary for combinatorial auctions and matroids, in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2018, pp. 700\u2013714.","DOI":"10.1137\/1.9781611975031.46"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1137\/15M1029394"},{"key":"ref28","unstructured":"H. Esfandiari, M. Hajiaghayi, B. Lucier, and M. Mitzenmacher, Prophets, secretaries, and maximizing the probability of choosing the best, Proc. Mach. Learn. Res. (PMLR), 108, 2020, pp. 3717\u20133727."},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"T. Ezra, Prophet inequality from samples: Is the more the merrier? in Proceedings of the 2026 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2024, pp. 2099\u20132112.","DOI":"10.1137\/1.9781611978971.76"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"T. Ezra, M. Feldman, N. Gravin, and Z. G. Tang, Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models, in 2020 ACM Conference on Economics and Computation (EC), ACM, New York, 2020, pp. 769\u2013787.","DOI":"10.1145\/3391403.3399513"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"T. Ezra, M. Feldman, N. Gravin, and Z. G. Tang, \u201cWho is next in line?\u201d On the significance of knowing the arrival order in Bayesian online settings, in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2023, pp. 3759\u20133776.","DOI":"10.1137\/1.9781611977554.ch145"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"T. Ezra, M. Feldman, and I. Nehama, Prophets and secretaries with overbooking, in Proceedings of the 2018 ACM Conference on Economics and Computation (EC), ACM, New York, 2018, pp. 319\u2013320.","DOI":"10.1145\/3219166.3219211"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"T. Ezra, M. Feldman, and Z. G. Tang, Choosing behind the veil: Tight bounds for identity-blind online algorithms, in Proceedings of the 2024 ACM Conference on Economics and Computation, (EC), ACM, New York, 2024, pp. 136\u2013158.","DOI":"10.1145\/3670865.3673620"},{"key":"ref34","doi-asserted-by":"crossref","unstructured":"T. Ezra and T. Garbuz, The importance of knowing the arrival order in combinatorial bayesian settings, in International Conference on Web and Internet Economics, Springer, Cham, Switzerland, 2023, pp. 256\u2013271.","DOI":"10.1007\/978-3-031-48974-7_15"},{"key":"ref35","doi-asserted-by":"crossref","unstructured":"M. Feldman, N. Gravin, and B. Lucier, Combinatorial auctions via posted prices, in Proceedings of the 2015 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2015, pp. 123\u2013135.","DOI":"10.1137\/1.9781611973730.10"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1177012493"},{"key":"ref37","doi-asserted-by":"crossref","unstructured":"H. Fu, P. Lu, Z. G. Tang, H. Wu, J. Wu, and Q. Zhang, Sample-Based Matroid Prophet Inequalities, in Proceedings of the 2024 ACM Conference on Economics and Computation (EC), ACM, New Haven, 2024, 781.","DOI":"10.1145\/3670865.3673506"},{"key":"ref38","unstructured":"N. Garg, A. Gupta, S. Leonardi, and P. Sankowski, Stochastic analyses for online combinatorial optimization problems, in Proceedings of the 2008 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2008, pp. 942\u2013951."},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1966.10502008"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_50"},{"key":"ref41","doi-asserted-by":"crossref","unstructured":"N. Gravin, H. Li, and Z. G. Tang, Optimal prophet inequality with less than one sample, in International Conference on Web and Internet Economics, Springer, Cham, Switzerland, 2022,\u00a0pp. 115\u2013131.","DOI":"10.1007\/978-3-031-22832-2_7"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2022.1251"},{"key":"ref43","doi-asserted-by":"crossref","unstructured":"A. Gupta, V. Nagarajan, and S. Singla, Algorithms and adaptivity gaps for stochastic probing, in Proceedings of the 2016 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2016, pp. 1731\u20131747.","DOI":"10.1137\/1.9781611974331.ch120"},{"key":"ref44","doi-asserted-by":"crossref","unstructured":"A. Gupta, V. Nagarajan, and S. Singla, Adaptivity gaps for stochastic probing: Submodular and XOS functions, in Proceedings of the 2017 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2017, pp. 1688\u20131702.","DOI":"10.1137\/1.9781611974782.111"},{"key":"ref45","first-page":"58","volume-title":"Assoc. Adv. Artif. Intell.","volume":"7","author":"Hajiaghayi M. T.","year":"2007"},{"key":"ref46","doi-asserted-by":"crossref","unstructured":"E. Harb, New prophet inequalities via poissonization and sharding, in Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA), in SODA, SIAM, Philadelphia, 2025, pp. 1222\u20131269, https:\/\/doi.org\/10.1137\/1.9781611978322.37.","DOI":"10.1137\/1.9781611978322.37"},{"key":"ref47","series-title":"LIPIcs. Leibniz Int. Proc. Inform. 151","first-page":"45","volume-title":"Innovations in Theoretical Computer Science","author":"Jiang H.","year":"2020"},{"key":"ref48","doi-asserted-by":"crossref","unstructured":"H. Kaplan, D. Naori, and D. Raz, Competitive analysis with a sample and the secretary problem, in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2020, pp. 2082\u20132095.","DOI":"10.1137\/1.9781611975994.128"},{"key":"ref49","doi-asserted-by":"crossref","unstructured":"H. Kaplan, D. Naori, and D. Raz, Online weighted matching with a sample, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2022, pp. 1247\u20131272.","DOI":"10.1137\/1.9781611977073.52"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993009"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4149(87)90029-9"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.2307\/1427302"},{"key":"ref53","doi-asserted-by":"crossref","unstructured":"K. Kessel, A. Shameli, A. Saberi, and D. Wajc, The stationary prophet inequality problem, in Proceedings of the 23rd ACM Conference on Economics and Computation, ACM, New York, 2022, pp. 243\u2013244.","DOI":"10.1145\/3490486.3538374"},{"key":"ref54","doi-asserted-by":"crossref","unstructured":"R. Kleinberg and S. M. Weinberg, Matroid prophet inequalities, in Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 123\u2013136.","DOI":"10.1145\/2213977.2213991"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.11.002"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"ref57","first-page":"197","volume":"4","author":"Krengel U.","year":"1978","journal-title":"Probab. Banach Spaces"},{"key":"ref58","doi-asserted-by":"crossref","unstructured":"J. Li, Y. Liu, and Y. Zhang, Adaptivity gaps for stochastic probing with subadditive functions, in Proceedings of the 2025 IEEE Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Sydney, 2025, pp. 149\u2013185.","DOI":"10.1109\/FOCS63196.2025.00012"},{"key":"ref59","doi-asserted-by":"crossref","unstructured":"R. Niazadeh, A. Saberi, and A. Shameli, Prophet inequalities vs. approximating optimum online, in Web and Internet Economics - 14th International Conference, WINE 2018, Oxford, UK, 2018, Lecture Notes in Comput Sci 11316, G. Christodoulou and T. Harks, eds. Springer, Cham, Switzerland, 2018, pp. 356\u2013374.","DOI":"10.1007\/978-3-030-04612-5_24"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1145\/3465456.3467613"},{"key":"ref61","series-title":"LIPIcs Leibniz Int. Proc. Inform. 275","first-page":"23","volume-title":"APPROX\/RANDOM","author":"Patton K.","year":"2023"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00023"},{"key":"ref63","volume-title":"Beyond the Worst-Case Analysis of Algorithms","author":"Roughgarden T.","year":"2021"},{"key":"ref64","doi-asserted-by":"crossref","unstructured":"A. Rubinstein, Beyond matroids: Secretary problem and prophet inequality with general constraints, in Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, ACM, New York, 2016, pp. 324\u2013332.","DOI":"10.1145\/2897518.2897540"},{"key":"ref65","unstructured":"A. Rubinstein, J. Z. Wang, and S. M. Weinberg, Optimal single-choice prophet inequalities from samples, in 11th Innovations in Theoretical Computer Science Conference, LIPIcs. Leibniz Int. Proc. Inform. 151, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany, 2020, 60."},{"key":"ref66","series-title":"LIPIcs Leibniz Int. Proc. Inform. 198","first-page":"109","volume-title":"ICALP","author":"Saberi A.","year":"2021"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993150"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718196"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T08:02:10Z","timestamp":1772611330000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1708917"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,4]]},"references-count":68,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4,30]]}},"alternative-id":["10.1137\/24M1708917"],"URL":"https:\/\/doi.org\/10.1137\/24m1708917","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,4]]}}}