{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T00:38:51Z","timestamp":1768351131226,"version":"3.49.0"},"reference-count":36,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research"],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:p>The prophet inequality is a cornerstone of online decision making, comparing a sequential decision maker to a prophet who knows all outcomes in advance. In \u201cTrading Prophets,\u201d J. Correa, A. Cristi, P. D\u00fctting, M. Hajiaghayi, J. Olkowski, and K. Schewior initiate the study of buy-and-sell prophet inequalities. Here, an online algorithm observes a sequence of prices, one after the other, to trade an item. At each time step, the algorithm can decide to buy and pay the current price if it does not already hold the item, or it can decide to sell and collect the current price as a reward if it holds the item. The authors identify settings where a constant-factor approximation to the all-knowing prophet benchmark can be achieved. Interestingly, these conditions differ from those required for standard prophet inequalities. Specifically, they show that no constant-factor inequality exists for arbitrary independent prices. In contrast, they prove that a constant factor is achievable when independent prices arrive in a random order.<\/jats:p>","DOI":"10.1287\/opre.2023.0593","type":"journal-article","created":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T15:17:38Z","timestamp":1761578258000},"page":"260-280","source":"Crossref","is-referenced-by-count":0,"title":["Trading Prophets"],"prefix":"10.1287","volume":"74","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3012-7622","authenticated-orcid":false,"given":"Jos\u00e9","family":"Correa","sequence":"first","affiliation":[{"name":"Departamento de Ingenier\u00eda Industrial, Universidad de Chile, Santiago 8370439, Chile"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1227-2092","authenticated-orcid":false,"given":"Andr\u00e9s","family":"Cristi","sequence":"additional","affiliation":[{"name":"College of Management of Technology, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, 1015 Lausanne, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0635-6812","authenticated-orcid":false,"given":"Paul","family":"D\u00fctting","sequence":"additional","affiliation":[{"name":"Google Research, 8002 Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4842-0533","authenticated-orcid":false,"given":"Mohammad","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"Computer Science Department, University of Maryland, College Park, Maryland 20742"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9278-3935","authenticated-orcid":false,"given":"Jan","family":"Olkowski","sequence":"additional","affiliation":[{"name":"Computer Science Department, University of Maryland, College Park, Maryland 20742"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2236-0210","authenticated-orcid":false,"given":"Kevin","family":"Schewior","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Cologne, 50969 K\u00f6ln, Germany; and Department of Mathematics and Computer Science, University of Southern Denmark, 5230 Odense, Denmark"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"crossref","unstructured":"Abolhassani M, Ehsani S, Esfandiari H, Hajiaghayi M, Kleinberg RD, Lucier B (2017) Beating 1\u22121\/e for ordered prophets.\n                      Proc. ACM SIGACT Sympos. Theory Comput.\n                      (ACM, New York), 61\u201371.","DOI":"10.1145\/3055399.3055479"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1137\/120878422"},{"key":"B3","volume-title":"Online Computation and Competitive Analysis","author":"Borodin A","year":"1998"},{"key":"B4","doi-asserted-by":"crossref","unstructured":"Braun A, Kesselheim T (2021) Truthful mechanisms for two-sided markets via prophet inequalities.\n                      Proc. ACM Conf. Econom. Comput.\n                      (ACM, New York), 202\u2013203.","DOI":"10.1145\/3465456.3467632"},{"key":"B5","doi-asserted-by":"crossref","unstructured":"Brustle J, Cai Y, Wu F, Zhao M (2017) Approximating gains from trade in two-sided markets via simple mechanisms.\n                      Proc. ACM Conf. Econom. Comput.\n                      (ACM, New York), 589\u2013590.","DOI":"10.1145\/3033274.3085148"},{"key":"B6","doi-asserted-by":"crossref","unstructured":"Caramanis C, D\u00fctting P, Faw M, Fusco F, Lazos P, Leonardi S, Papadigenopoulos O, et al. (2022) Single-sample prophet inequalities via greedy-ordered selection.\n                      Proc. ACM-SIAM Sympos. Discrete Algorithms\n                      (SIAM, Philadelphia), 1298\u20131325.","DOI":"10.1137\/1.9781611977073.54"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.2307\/1909935"},{"key":"B8","doi-asserted-by":"crossref","unstructured":"Colini-Baldeschi R, de Keijzer B, Leonardi S, Turchetta S (2016) Approximately efficient double auctions with strong budget balance.\n                      Proc. ACM-SIAM Sympos. Discrete Algorithms\n                      (SIAM, Philadelphia), 1424\u20131443.","DOI":"10.1137\/1.9781611974331.ch98"},{"key":"B9","doi-asserted-by":"crossref","unstructured":"Colini-Baldeschi R, Goldberg PW, de Keijzer B, Leonardi S, Turchetta S (2017a) Fixed price approximability of the optimal gain from trade.\n                      Proc. Internat. Conf. Web Internet Econom.\n                      (Springer, Heidelberg, Berlin), 146\u2013160.","DOI":"10.1007\/978-3-319-71924-5_11"},{"key":"B10","doi-asserted-by":"crossref","unstructured":"Colini-Baldeschi R, Goldberg PW, de Keijzer B, Leonardi S, Roughgarden T, Turchetta S (2017b) Approximately efficient two-sided combinatorial auctions.\n                      Proc. ACM Conf. Econom. Comput.\n                      (ACM, New York), 591\u2013608.","DOI":"10.1145\/3033274.3085128"},{"key":"B11","unstructured":"Correa JR, Hartline J, Immorlica N (2022a) A semester virtual institute. Accessed October 10, 2025, https:\/\/cacm.acm.org\/blogs\/blog-cacm\/258538-a-semester-virtual-institute\/fulltext."},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01544-8"},{"key":"B13","doi-asserted-by":"crossref","unstructured":"Correa JR, Cristi A, Epstein B, Soto JA (2020) The two-sided game of googol and sample-based prophet inequalities.\n                      Proc. ACM-SIAM Sympos. Discrete Algorithms\n                      (SIAM, Philadelphia), 2066\u20132081.","DOI":"10.1137\/1.9781611975994.127"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1167"},{"key":"B15","unstructured":"Correa JR, D\u00fctting P, Fischer FA, Schewior K, Ziliotto B (2021b) Unknown I.I.D. prophets: Better bounds, streaming algorithms and a new impossibility.\n                      Proc. Innovations Theoretical Comput. Sci. Conf.\n                      (Schloss Dagstuhl - Leibniz Zentrum f\u00fcr Informatik, Wadern, Germany), 86:1\u201386:1."},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2020.1105"},{"key":"B17","doi-asserted-by":"crossref","unstructured":"Deng Y, Mao J, Sivan B, Wang K (2022) Approximately efficient bilateral trade.\n                      Proc. ACM SIGACT Sympos. Theory Comput.\n                      (ACM, New York), 718\u2013721.","DOI":"10.1145\/3519935.3520054"},{"key":"B18","volume-title":"Stochastic Processes","author":"Doob JL","year":"1953"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1214\/009117906000000638"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1214\/08-AAP566"},{"key":"B21","doi-asserted-by":"crossref","unstructured":"D\u00fctting P, Fusco F, Lazos P, Leonardi S, Reiffenh\u00e4user R (2021) Efficient two-sided markets with limited information.\n                      Proc. ACM SIGACT Sympos. Theory Comput.\n                      (ACM, New York), 1452\u20131465.","DOI":"10.1145\/3406325.3451076"},{"key":"B22","doi-asserted-by":"crossref","unstructured":"Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids.\n                      Proc. ACM-SIAM Sympos. Discrete Algorithms\n                      (SIAM, Philadelphia), 700\u2013714.","DOI":"10.1137\/1.9781611975031.46"},{"key":"B23","doi-asserted-by":"crossref","unstructured":"Ekbatani F, Niazadeh R, Nuti P, Vondr\u00e1k J (2024) Prophet inequalities with cancellation costs.\n                      Proc. ACM Sympos. Theory Comput.\n                      (ACM, New York), 1247\u20131258.","DOI":"10.1145\/3618260.3649786"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1137\/15M1029394"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1137\/S0040585X97978075"},{"key":"B26","doi-asserted-by":"crossref","unstructured":"Kleinberg JM, Kleinberg R (2018) Delegated search approximates efficient search.\n                      Proc. ACM Conf. Econom. Comput.\n                      (ACM, New York), 287\u2013302.","DOI":"10.1145\/3219166.3219205"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"B28","first-page":"197","volume":"4","author":"Krengel U","year":"1978","journal-title":"Adv. Probability Related Topics"},{"issue":"3","key":"B29","first-page":"1","volume":"46","author":"Li B","year":"2014","journal-title":"ACM Comput. Survey"},{"key":"B30","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. ACM Conf. Econom. Comput.\n                      (ACM, New York), 692.","DOI":"10.1145\/3465456.3467598"},{"key":"B31","first-page":"1","volume":"1","author":"McAfee RP","year":"2008","journal-title":"Appl. Econom. Res. Bull."},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(83)90048-0"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1287\/opre.7.2.145"},{"key":"B34","unstructured":"Rubinstein A, Wang JZ, Weinberg SM (2020) Optimal single-choice prophet inequalities from samples.\n                      Proc. Innovations Theoretical Comput. Sci. Conf.\n                      (Schloss Dagstuhl - Leibniz Zentrum f\u00fcr Informatik, Wadern, Germany), 60:1\u201360:10."},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993150"},{"key":"B36","unstructured":"Singla S (2018) Combinatorial optimization under uncertainty: Probing and stopping-time algorithms. PhD thesis, Carnegie Mellon University, Pittsburgh, PA."}],"container-title":["Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/opre.2023.0593","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T09:20:36Z","timestamp":1768209636000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/opre.2023.0593"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["10.1287\/opre.2023.0593"],"URL":"https:\/\/doi.org\/10.1287\/opre.2023.0593","relation":{},"ISSN":["0030-364X","1526-5463"],"issn-type":[{"value":"0030-364X","type":"print"},{"value":"1526-5463","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1]]}}}