Trading Prophets

The prophet inequality is a cornerstone of online decision making, comparing a sequential decision maker to a prophet who knows all outcomes in advance. In “Trading Prophets,” J. Correa, A. Cristi, P. Dütting, M. Hajiaghayi, J. Olkowski, and K. Schewior initiate the study of buy-and-sell prophet inequalities. Here, an online algorithm observes a sequence of prices, one after the other, to trade an item. At each time step, the algorithm can decide to buy and pay the current price if it does not already hold the item, or it can decide to sell and collect the current price as a reward if it holds the item. The authors identify settings where a constant-factor approximation to the all-knowing prophet benchmark can be achieved. Interestingly, these conditions differ from those required for standard prophet inequalities. Specifically, they show that no constant-factor inequality exists for arbitrary independent prices. In contrast, they prove that a constant factor is achievable when independent prices arrive in a random order.