Kavli Affiliate: Felix Fischer | First 5 Authors: José Correa, Paul Dütting, Felix Fischer, Kevin Schewior, Bruno Ziliotto | Summary: A prophet inequality states, for some $alphain[0,1]$, that the expected value achievable by a gambler who sequentially observes random variables $X_1,dots,X_n$ and selects one of them is at least an $alpha$ fraction of the maximum […]
Continue.. Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility