## Abstract

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 language | English |
---|---|

Title of host publication | EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation |

Publisher | Association for Computing Machinery |

Publication date | Jul 2023 |

Pages | 490-510 |

ISBN (Electronic) | 9798400701047 |

DOIs | |

Publication status | Published - Jul 2023 |

Event | 24th ACM Conference on Economics and Computation, EC 2023 - London, United Kingdom Duration: 9. Jul 2023 → 12. Jul 2023 |

### Conference

Conference | 24th ACM Conference on Economics and Computation, EC 2023 |
---|---|

Country/Territory | United Kingdom |

City | London |

Period | 09/07/2023 → 12/07/2023 |

Sponsor | a16zcrypto, et al., Google Inc., Meta, OneChonos, XTX Markets |

## Keywords

- online trading
- optimal stopping
- prophet inequalities