Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility

José Correa, Paul Dütting, Felix Fischer +2

A prophet inequality states, for some $\alpha \in [0,1]$, that the expected value achievable by a gambler who sequentially observes random variables $X_1,\dots ,X_n$ and selects one of the…