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 identify settings in which a constant-factor buy-and-sell prophet inequality can be achieved. Interestingly, these settings are different from those in which a constant-factor standard prophet inequality can be achieved. In particular, no constant-factor buy-and-sell prophet inequality can be achieved in the case of arbitrary independent prices. In contrast, we show that in the case of independent prices arriving in random order a constant factor can be achieved. This in particular implies a constant-factor buy-and-sell prophet inequality for i.i.d. prices, for which we also show a tight ratio of 1=2, using a single-threshold algorithm. We use the results for these base cases to solve a variety of more complex settings: affiliated prices, the single-sample setting, the case of k items and that of k item types, and a budgeted version where gains can be reinvested. We experimentally validate our results by assessing our algorithms' performance on a used car auction data set and synthetic data.