Trading Prophets

Jose Correa, Andrés Cristi, Paul Duetting, Mohammad Taghi Hajiaghayi, Jan Olkowski, Kevin Schewior

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

19 Downloads (Pure)


In this work we initiate the study of buy-and-sell prophet inequalities. We start by considering what is arguably the most fundamental setting. In this setting the online algorithm observes a sequence of prices one after the other. At each time step, the online algorithm can decide to buy and pay the current price if it does not hold the item already; or it can decide to sell and collect the current price as a reward if it holds the item.We show that for i.i.d. prices a single-threshold online algorithm achieves at least 1/2 of the expected profit of the the optimal offline algorithm, and that this is the best possible ratio achievable by any online algorithm. For non-i.i.d. prices in random order, where prices are no longer independent, we give a single-threshold online algorithm that achieves at least a 1/16 fraction of the expected profit of the optimal offline algorithm. We also show that for this setting no online algorithm can yield a better than 1/3 approximation, and thus establish a formal separation from the i.i.d. case. On the other hand, we present a threshold-based online algorithm for this setting that yields a 1/2 - o(1) approximation. For non-i.i.d. prices (and arbitrarily correlated distributions) no approximation is possible.We use the results for these base cases to solve a variety of more complex settings. For instance, we show a 1/2 - o(1) approximation for settings where prices are affiliated and the online algorithm has only access to a single sample. We also extend our upper and lower bounds for the single item case to k items, and thus in particular show that unlike in the classic prophet inequality problem with k items it is impossible to achieve 1 - o(1) approximations. We also consider a budgeted version where the online algorithm can buy fractions of an item and re-invest gains, and show that it's possible to achieve constant-factor approximations to the growth rate of the optimal offline algorithm. For a setting with k types of items and streams of prices for each type of item, we show that for the unit-capacity case it is possible to achieve a ω(1/k) approximation, and that this is best possible.

Original languageEnglish
Title of host publicationEC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery
Publication dateJul 2023
ISBN (Electronic)9798400701047
Publication statusPublished - Jul 2023
Event24th ACM Conference on Economics and Computation, EC 2023 - London, United Kingdom
Duration: 9. Jul 202312. Jul 2023


Conference24th ACM Conference on Economics and Computation, EC 2023
Country/TerritoryUnited Kingdom
Sponsora16zcrypto, et al., Google Inc., Meta, OneChonos, XTX Markets


  • online trading
  • optimal stopping
  • prophet inequalities


Dive into the research topics of 'Trading Prophets'. Together they form a unique fingerprint.

Cite this