Help
Cart
Skip main navigation

Available Issues

April 16, 2013 - May 25, 2026

Available Issues

April 16, 2013 - May 25, 2026

Online Selection with Uncertain Disruption

Published Online:22 Jun 2026https://doi.org/10.1287/opre.2025.1936

References

  • Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2):930–972.Crossref, Google Scholar
  • Alijani R, Banerjee S, Gollapudi S, Munagala K, Wang K (2020) Predict and match: Prophet inequalities with uncertain supply. Proc. ACM Measurement Anal. Comput. Systems 4(1):04.Google Scholar
  • Allouah A, Bahamou A, Besbes O (2023) Optimal pricing with a single point. Management Sci. 69(10):5866–5882.Link, Google Scholar
  • Aouad A, Saritaç Ö (2020) Dynamic stochastic matching under limited time. Biró P, Hartline JD, Ostrovsky M, Procaccia AD, eds. Proc. 21st ACM Conf. Econom. Comput. (EC ’20) (Association for Computing Machinery, New York), 789–790.Google Scholar
  • Arnosti N, Ma W (2023) Tight guarantees for static threshold policies in the prophet secretary problem. Oper. Res. 71(5):1777–1788.Link, Google Scholar
  • Assaf D, Samuel-Cahn E (2000) Simple ratio prophet inequalities for a mortal with multiple choices. J. Appl. Probab. 37(4):1084–1091.Crossref, Google Scholar
  • Brustle J, Perez-Salazar S, Verdugo V (2026) Splitting guarantees for prophet inequalities via nonlinear systems. Math. Oper. Res. 51(2):877–904.Link, Google Scholar
  • Chawla S, Devanur N, Lykouris T (2024) Static pricing for multi-unit prophet inequalities. Oper. Res. 72(4):1388–1399.Link, Google Scholar
  • Chawla S, Hartline JD, Kleinberg R (2007) Algorithmic pricing via virtual valuations. MacKie-Mason JK, Parkes DC, Resnick P, eds. Proc. 8th ACM Conf. Electronic Commerce (EC ’07) (Association for Computing Machinery, New York), 243–251.Google Scholar
  • Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Schulman LJ, ed. Proc. Forty-Second ACM Sympos. Theory Comput. (STOC ’10) (Association for Computing Machinery, New York), 311–320.Google Scholar
  • Cohen MC, Keller PW, Mirrokni V, Zadimoghaddam M (2019) Overcommitment in cloud services: Bin packing with chance constraints. Management Sci. 65(7):3255–3271.Link, Google Scholar
  • Correa J, Foncea P, Pizarro D, Verdugo V (2019) From pricing to prophets, and back! Oper. Res. Lett. 47(1):25–29.Crossref, Google Scholar
  • Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2017) Posted price mechanisms for a random stream of customers. Daskalakis C, Babaioff M, Moulin H, eds. Proc. 2017 ACM Conf. Econom. Comput. (EC ’17) (Association for Computing Machinery, New York), 169–186.Google Scholar
  • Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2021) Posted price mechanisms and optimal threshold strategies for random arrivals. Math. Oper. Res. 46(4):1452–1478.Link, Google Scholar
  • David HA, Nagaraja HN (2004) Order Statistics (John Wiley & Sons, Hoboken, NJ).Google Scholar
  • Dean BC, Goemans MX, Vondrák J (2008) Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res. 33(4):945–964.Link, Google Scholar
  • Delong S, Farhadi A, Niazadeh R, Sivan B, Udwani R (2024) Online bipartite matching with reusable resources. Math. Oper. Res. 49(3):1825–1854.Link, Google Scholar
  • Epstein B, Ma W (2024) Selection and ordering policies for hiring pipelines via linear programming. Oper. Res. 72(5):2000–2013.Link, Google Scholar
  • Feng Y, Li B, Li H, Wu X, Wu Y (2025) IID prophet inequality with a single data point. Artificial Intelligence 341:104296.Crossref, Google Scholar
  • Fu H, Li J, Xu P (2018) A PTAS for a class of stochastic dynamic programs. Chatzigiannakis I, Kaklamanis C, Marx D, Sannella D, eds. 45th Internat. Colloquium Automata Languages Programming (ICALP 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 107 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 56:1–56:14.Google Scholar
  • Goyal V, Ravi R (2010) A PTAS for the chance-constrained knapsack problem with random item sizes. Oper. Res. Lett. 38(3):161–164.Crossref, Google Scholar
  • Gupta V (2024) Greedy algorithm for multiway matching with bounded regret. Oper. Res. 72(3):1139–1155.Link, Google Scholar
  • Hajiaghayi MT, Kleinberg R, Sandholm T (2007) Automated online mechanism design and prophet inequalities. Holte RC, Howe AE, eds. Proc. 22nd Natl. Conf. Artificial Intelligence—Vol. 1 AAAI’07 (AAAI Press, Vancouver, BC), 58–65.Google Scholar
  • Harb E (2025) New prophet inequalities via Poissonization and sharding. Azar Y, Panigrahi D, eds. Proc. 2025 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1222–1269.Google Scholar
  • He S, Wei Y, Xu J, Yu SH (2025) Online resource allocation without re-solving: The effectiveness of primal-dual policies. Preprint, submitted February 24, https://dx.doi.org/10.2139/ssrn.5133857.Google Scholar
  • Hill TP, Kertz RP (1982) Comparisons of stop rule and supremum expectations of i.i.d. random variables. Ann. Probab. 10(2):336–345.Crossref, Google Scholar
  • Hill TP, Kertz RP (1992) A survey of prophet inequalities in optimal stopping theory. Contemporary Math. 125(1):191–207.Crossref, Google Scholar
  • Hill TP, Krengel U (1991) Minimax-optimal stop rules and distributions in secretary problems. Ann. Probab. 19(1):342–353.Crossref, Google Scholar
  • Jiang J, Ma W, Zhang J (2026) Tightness without counterexamples: A new approach and new results for prophet inequalities. Math. Oper. Res. 51(2):956–987.Google Scholar
  • Kerimov S, Ashlagi I, Gurvich I (2024) Dynamic matching: Characterizing and achieving constant regret. Management Sci. 70(5):2799–2822.Link, Google Scholar
  • Kerimov S, Ashlagi I, Gurvich I (2025) On the optimality of greedy policies in dynamic matching. Oper. Res. 73(1):560–582.Link, Google Scholar
  • Kertz RP (1986) Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate duality. J. Multivariate Anal. 19(1):88–112.Crossref, Google Scholar
  • Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. 83(4):745–747.Crossref, Google Scholar
  • Liu A, Leme RP, Pal M, Schneider J, Sivan B (2021) Variable decomposition for prophet inequalities and optimal ordering. Biró P, Chawla S, Echenique F, eds. Proc. 22nd ACM Conf. Econom. Comput. (EC ’21) (Association for Computing Machinery, New York), 692. Google Scholar
  • Ma W (2018) Improvements and generalizations of stochastic knapsack and Markovian bandits approximation algorithms. Math. Oper. Res. 43(3):789–812.Link, Google Scholar
  • Mehta A, Panigrahi D (2012) Online matching with stochastic rewards. Proc. 2012 IEEE 53rd Annual Sympos. Foundations Comput. Sci. FOCS ‘12 (IEEE Computer Society, Washington, DC), 728–737.Google Scholar
  • Naor P (1969) The regulation of queue size by levying tolls. Econometrica 37(1):15–24.Crossref, Google Scholar
  • Perez-Salazar S, Verdugo V (2024) Optimal guarantees for online selection over time. Preprint, submitted August 20, https://arxiv.org/abs/2408.11224.Google Scholar
  • Perez-Salazar S, Singh M, Toriello A (2026) The i.i.d. prophet inequality with limited flexibility. Math. Oper. Res. 51(1):218–254.Link, Google Scholar
  • Perez-Salazar S, Menache I, Singh M, Toriello A (2022) Dynamic resource allocation in the cloud with near-optimal efficiency. Oper. Res. 70(4):2517–2537.Link, Google Scholar
  • Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12(4):1213–1216.Crossref, Google Scholar
  • Samuel-Cahn E (1996) Optimal stopping with random horizon with application to the full-information best-choice problem with random freeze. J. Amer. Statist. Assoc. 91(433):357–364.Crossref, Google Scholar
  • Shiryaev AN (2007) Optimal Stopping Rules, vol. 8 (Springer Science & Business Media, Berlin).Google Scholar
  • Sion M (1958) On general minimax theorems. Pacific J. Math. 8(1):171–176.Crossref, Google Scholar
  • Van Mieghem JA (1995) Dynamic scheduling with convex delay costs: The generalized c|mu rule. Ann. Appl. Probab. 5(3):809–833.Crossref, Google Scholar
  • Wei Y, Xu J, Yu SH (2023) Constant regret primal-dual policy for multi-way dynamic matching. Smirni E, Avrachenkov K, Gill P, Urgaonkar B, eds. Abstract Proc. 2023 ACM SIGMETRICS Internat. Conf. Measurement Model. Comput. Systems (SIGMETRICS ’23) (Association for Computing Machinery, New York), 79–80.Google Scholar
  • Zhang J, Jaillet P (2023) Secretary problems with random number of candidates: How prior distributional information helps. Preprint, submitted October 11, https://arxiv.org/abs/2310.07884.Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree