{"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":1782185657150,"version":"3.54.5"},"reference-count":39,"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>The prophet inequality is one of the cornerstone problems in optimal stopping theory and has become a crucial tool for designing sequential algorithms in Bayesian settings. In the i.i.d. k-selection prophet inequality problem, we sequentially observe n nonnegative random values sampled from a known distribution. Each time, a decision is made to accept or reject the value, and under the constraint of accepting at most k items. For k = 1, Hill and Kertz [Ann. Probab. 1982] provided an upper bound on the worst-case approximation ratio that was later matched by an algorithm of Correa et al. [Math. Oper. Res. 2021]. The worst-case tight approximation ratio for k = 1 is computed by studying a differential equation that naturally appears when analyzing the optimal dynamic programming policy. A similar result for k &gt; 1 has remained elusive. In this work, we introduce a nonlinear system of differential equations for the i.i.d. k-selection prophet inequality that generalizes Hill and Kertz\u2019s equation when k = 1. Our nonlinear system is defined by k constants that determine its functional structure, and their summation provides a lower bound on the optimal policy\u2019s asymptotic approximation ratio for the i.i.d. k-selection prophet inequality. To obtain this result, we introduce for every k an infinite-dimensional linear programming formulation that fully characterizes the worst-case tight approximation ratio of the k-selection prophet inequality problem for every n, and then we follow a dual-fitting approach to link with our nonlinear system for sufficiently large values of n. As a corollary, we use our provable lower bounds to establish a tight approximation ratio for the stochastic sequential assignment problem in the i.i.d. nonnegative regime.<\/jats:p>\n                  <jats:p>Funding: This research was supported by Agencia Nacional de Investigaci\u00f3n y Desarrollo (Chile) [Grants FONDECYT 1241846 and ANILLO ACT210005].<\/jats:p>","DOI":"10.1287\/moor.2024.0413","type":"journal-article","created":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T12:30:06Z","timestamp":1744893006000},"page":"877-904","source":"Crossref","is-referenced-by-count":3,"title":["Splitting Guarantees for Prophet Inequalities via Nonlinear Systems"],"prefix":"10.1287","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-2523-8051","authenticated-orcid":false,"given":"Johannes","family":"Brustle","sequence":"first","affiliation":[{"name":"Department of Computer and Systems Sciences, Sapienza University of Rome, 00185 Rome, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4534-7721","authenticated-orcid":false,"given":"Sebastian","family":"Perez-Salazar","sequence":"additional","affiliation":[{"name":"Department of Computational Applied Mathematics and Operations Research, Rice University, Houston, Texas 77005; and Ken Kennedy Institute, Rice University, Houston, Texas 77005"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0817-7356","authenticated-orcid":false,"given":"Victor","family":"Verdugo","sequence":"additional","affiliation":[{"name":"Institute for Mathematical and Computational Engineering, Pontificia Universidad Cat\u00f3lica de Chile, Chile; and Department of Industrial and Systems Engineering, Pontificia Universidad Cat\u00f3lica de Chile, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1137\/120878422"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2022.2419"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1031863177"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_2"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2021.2121"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2022.0230"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0604"},{"key":"B8","first-page":"158","volume":"2010","author":"Chakraborty T","year":"2010","journal-title":"6th Internat. Workshop WINE"},{"key":"B9","first-page":"1169","author":"Chan TH","year":"2014","journal-title":"25th Annual ACM-SIAM Sympos. Discrete Algorithms"},{"key":"B10","doi-asserted-by":"crossref","unstructured":"Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing.\n                      Proc. 55th Annual ACM Sympos. Theory of Comput.\n                      (Association for Computing Machinery, New York), 311\u2013320.","DOI":"10.1145\/1806689.1806733"},{"key":"B11","doi-asserted-by":"crossref","unstructured":"Correa J, Cristi A (2023) A constant factor prophet inequality for online combinatorial auctions.\n                      Proc. 55th Annual ACM Sympos. Theory of Comput.\n                      \n                      (Association for Computing Machinery, New York), 686\u2013697.","DOI":"10.1145\/3564246.3585151"},{"key":"B12","doi-asserted-by":"crossref","unstructured":"Correa J, D\u00fctting P, Fischer F, Schewior K (2019) Prophet inequalities for i.i.d. random variables from an unknown distribution.\n                      Proc. 24th 2019 ACM Conf. Econom. Comput.\n                      (Association for Computing Machinery, New York), 3\u201317.","DOI":"10.1145\/3328526.3329627"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2018.11.010"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1145\/3331033.3331039"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2020.1105"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.7.349"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1137\/20M1323850"},{"key":"B18","doi-asserted-by":"crossref","unstructured":"Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids.\n                      Sympos. on Discrete Algorithms 2018\n                      (Society for Industrial and Applied Mathematics, Philadelphia), 700\u2013714.","DOI":"10.1137\/1.9781611975031.46"},{"key":"B19","doi-asserted-by":"crossref","unstructured":"Ekbatani F, Niazadeh R, Nuti P, Vondr\u00e1k J (2024) Prophet inequalities with cancellation costs.\n                      Proc. 56th Annual ACM Symposium Theory Comput.\n                      (Association for Computing Machinery, New York), 1247\u20131258.","DOI":"10.1145\/3618260.3649786"},{"key":"B20","doi-asserted-by":"crossref","unstructured":"Feldman M, Svensson O, Zenklusen R (2016) Online contention resolution schemes.\n                      Sympos. on Discrete Algorithms 2016\n                      (Society for Industrial and Applied Mathematics, Philadelphia), 1014\u20131033.","DOI":"10.1137\/1.9781611974331.ch72"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2022.2345"},{"key":"B22","unstructured":"Hajiaghayi MT, Kleinberg R, Sandholm T (2007) Automated online mechanism design and prophet inequalities.\n                      Assoc. Adv. Artificial Intelligence 2007\n                      (Association for the Advancement of Artificial Intelligence, Washington, DC), 58\u201365."},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993861"},{"key":"B24","doi-asserted-by":"crossref","unstructured":"Jiang J, Ma W, Zhang J (2023) Tightness without counterexamples: A new approach and new results for prophet inequalities.\n                      Proc. 24th ACM Conf. Econom. Comput. 2023\n                      (Association for Computing Machinery, New York), 909.","DOI":"10.1145\/3580507.3597734"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(86)90095-3"},{"key":"B26","doi-asserted-by":"crossref","unstructured":"Kesselheim T, T\u00f6nnis A, Radke K, V\u00f6cking B (2014) Primal beats dual on online packing LPs in the random-order model.\n                      Proc. 46th Annual ACM Sympos. Theory of Comput.\n                      (Association for Computing Machinery, New York), 303\u2013312.","DOI":"10.1145\/2591796.2591810"},{"key":"B27","doi-asserted-by":"crossref","unstructured":"Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities.\n                      Proc. 44th Annual ACM Sympos. Theory of Comput.\n                      (Association for Computing Machinery, New York), 123\u2013136.","DOI":"10.1145\/2213977.2213991"},{"key":"B28","volume-title":"Introductory Real Analysis","author":"Kolmogorov AN","year":"1975"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"B30","unstructured":"Lee E, Singla S (2018) Optimal online contention resolution schemes via ex-ante prophet inequalities.\n                      26th Ann. Eur. Sympos. Algorithms 2018\n                      (Schloss Dagstuhl \u2013 Leibniz-Zentrum fuer Informatik, Wandern, Germany)."},{"key":"B31","doi-asserted-by":"crossref","unstructured":"Liu A, Leme RP, P\u00e1l M, Schneider J, Sivan B (2021) Variable decomposition for prophet inequalities and optimal ordering.\n                      Proc. 22nd ACM Conf. Econom. Comput.\n                      (Association for Computing Machinery, New York), 692.","DOI":"10.1145\/3465456.3467598"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1145\/3144722.3144725"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"B34","doi-asserted-by":"crossref","unstructured":"Molina M, Gast N, Loiseau P, Perchet V (2025) Prophet inequalities: Competing with the top \u2113 items is easy.\n                      Sympos. on Discrete Algorithms 2025\n                      (Society for Industrial and Applied Mathematics, Philadelphia), 1270\u20131307.","DOI":"10.1137\/1.9781611978322.38"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1193342386"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2023.0210"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2022.0345"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993150"},{"key":"B39","doi-asserted-by":"crossref","unstructured":"Yan Q (2011) Mechanism design via correlation gap.\n                      Sympos. on Discrete Algorithms 2011\n                      (Society for Industrial and Applied Mathematics, 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.2024.0413","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:25:10Z","timestamp":1778228710000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2024.0413"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/moor.2024.0413"],"URL":"https:\/\/doi.org\/10.1287\/moor.2024.0413","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}