Trading Prophets

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

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

20 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.

TitelEC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation
ForlagAssociation for Computing Machinery
Publikationsdatojul. 2023
ISBN (Elektronisk)9798400701047
StatusUdgivet - jul. 2023
Begivenhed24th ACM Conference on Economics and Computation, EC 2023 - London, Storbritannien
Varighed: 9. jul. 202312. jul. 2023


Konference24th ACM Conference on Economics and Computation, EC 2023
Sponsora16zcrypto, et al., Google Inc., Meta, OneChonos, XTX Markets

Bibliografisk note

Funding Information:
This work was initiated during the Fall 2021 Virtual Chair Semester on Prophet Inequalities [Correa et al., 2022]. We would like to thank the organizers and the participants of the semester for their feedback. Kevin Schewior was in part supported by Independent Research Fund Denmark, Natural Sciences under Grant No. DFF-0135-00018B. MohammadTaghi Hajiaghayi and Jan Olkowski are partially supported by DARPA QuICC, NSF AF:Small 2218678, and NSF AF:Small 2114269.

Publisher Copyright:
© 2023 Owner/Author(s).


Dyk ned i forskningsemnerne om 'Trading Prophets'. Sammen danner de et unikt fingeraftryk.