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.