Trading Prophets

References

• Abolhassani M, Ehsani S, Esfandiari H, Hajiaghayi M, Kleinberg RD, Lucier B (2017) Beating 1−1/e for ordered prophets. Proc. ACM SIGACT Sympos. Theory Comput. (ACM, New York), 61–71.Google Scholar
• Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2):930–972.Crossref, Google Scholar
• Borodin A, El-Yaniv R (1998) Online Computation and Competitive Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• Braun A, Kesselheim T (2021) Truthful mechanisms for two-sided markets via prophet inequalities. Proc. ACM Conf. Econom. Comput. (ACM, New York), 202–203.Google Scholar
• Brustle J, Cai Y, Wu F, Zhao M (2017) Approximating gains from trade in two-sided markets via simple mechanisms. Proc. ACM Conf. Econom. Comput. (ACM, New York), 589–590.Google Scholar
• Caramanis C, Dütting P, Faw M, Fusco F, Lazos P, Leonardi S, Papadigenopoulos O, et al. (2022) Single-sample prophet inequalities via greedy-ordered selection. Proc. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1298–1325.Google Scholar
• Charnes A, Drèze J, Miller M (1966) Decision and horizon rules for stochastic planning problems: A linear example. Econometrica 34(2):307–330.Crossref, Google Scholar
• Colini-Baldeschi R, de Keijzer B, Leonardi S, Turchetta S (2016) Approximately efficient double auctions with strong budget balance. Proc. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1424–1443.Google Scholar
• Colini-Baldeschi R, Goldberg PW, de Keijzer B, Leonardi S, Turchetta S (2017a) Fixed price approximability of the optimal gain from trade. Proc. Internat. Conf. Web Internet Econom. (Springer, Heidelberg, Berlin), 146–160.Google Scholar
• Colini-Baldeschi R, Goldberg PW, de Keijzer B, Leonardi S, Roughgarden T, Turchetta S (2017b) Approximately efficient two-sided combinatorial auctions. Proc. ACM Conf. Econom. Comput. (ACM, New York), 591–608.Google Scholar
• 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.Google Scholar
• Correa JR, Saona R, Ziliotto B (2021a) Prophet secretary through blind strategies. Math. Programming 190(1):483–521.Crossref, Google Scholar
• Correa JR, Cristi A, Epstein B, Soto JA (2020) The two-sided game of googol and sample-based prophet inequalities. Proc. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2066–2081.Google Scholar
• Correa J, Dütting P, Fischer FA, Schewior K (2022b) Prophet inequalities for independent and identically distributed random variables from an unknown distribution. Math. Oper. Res. 47(2):1287–1309.Link, Google Scholar
• Correa JR, Dütting P, Fischer FA, Schewior K, Ziliotto B (2021b) Unknown I.I.D. prophets: Better bounds, streaming algorithms and a new impossibility. Proc. Innovations Theoretical Comput. Sci. Conf. (Schloss Dagstuhl - Leibniz Zentrum für Informatik, Wadern, Germany), 86:1–86:1.Google Scholar
• Correa JR, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2021c) Posted price mechanisms and optimal threshold strategies for random arrivals. Math. Oper. Res. 46(4):1452–1478.Link, Google Scholar
• Deng Y, Mao J, Sivan B, Wang K (2022) Approximately efficient bilateral trade. Proc. ACM SIGACT Sympos. Theory Comput. (ACM, New York), 718–721.Google Scholar
• Doob JL (1953) Stochastic Processes (Wiley, Hoboken, NJ).Google Scholar
• Du Toit J, Peskir G (2007) The trap of complacency in predicting the maximum. Ann. Probability 35(1):340–365.Crossref, Google Scholar
• Du Toit J, Peskir G (2009) Selling a stock at the ultimate maximum. Ann. Appl. Probability 19(3):983–1014.Crossref, Google Scholar
• Dütting P, Fusco F, Lazos P, Leonardi S, Reiffenhäuser R (2021) Efficient two-sided markets with limited information. Proc. ACM SIGACT Sympos. Theory Comput. (ACM, New York), 1452–1465.Google Scholar
• Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids. Proc. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 700–714.Google Scholar
• Ekbatani F, Niazadeh R, Nuti P, Vondrák J (2024) Prophet inequalities with cancellation costs. Proc. ACM Sympos. Theory Comput. (ACM, New York), 1247–1258.Google Scholar
• Esfandiari H, Hajiaghayi M, Liaghat V, Monemizadeh M (2017) Prophet secretary. SIAM J. Discrete Math. 31(3):1685–1701.Crossref, Google Scholar
• Graversen SE, Peskir G, Shiryaev AN (2006) Stopping Brownian motion without anticipation as close as possible to its ultimate maximum. Theory Probability Appl. 45(1):41–50.Crossref, Google Scholar
• Kleinberg JM, Kleinberg R (2018) Delegated search approximates efficient search. Proc. ACM Conf. Econom. Comput. (ACM, New York), 287–302.Google Scholar
• Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. 83(4):745–747.Crossref, Google Scholar
• Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Adv. Probability Related Topics 4:197–266.Google Scholar
• Li B, Hoi SC (2014) Online portfolio selection: A survey. ACM Comput. Survey 46(3):1–33.Google Scholar
• Liu A, Leme RP, Pál M, Schneider J, Sivan B (2021) Variable decomposition for prophet inequalities and optimal ordering. Proc. ACM Conf. Econom. Comput. (ACM, New York), 692.Google Scholar
• McAfee RP (2008) The gains from trade under fixed price mechanisms. Appl. Econom. Res. Bull. 1:1–10.Google Scholar
• Myerson RB, Satterthwaite MA (1983) Efficient mechanisms for bilateral trading. J. Econom. Theory 29(2):265–281.Crossref, Google Scholar
• Osborne MFM (1959) Brownian motion in the stock market. Oper. Res. 7(2):145–173.Link, Google Scholar
• Rubinstein A, Wang JZ, Weinberg SM (2020) Optimal single-choice prophet inequalities from samples. Proc. Innovations Theoretical Comput. Sci. Conf. (Schloss Dagstuhl - Leibniz Zentrum für Informatik, Wadern, Germany), 60:1–60:10.Google Scholar
• Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probability 12(4):1213–1216.Crossref, Google Scholar
• Singla S (2018) Combinatorial optimization under uncertainty: Probing and stopping-time algorithms. PhD thesis, Carnegie Mellon University, Pittsburgh, PA.Google Scholar