Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility
summary
Revisits the unknown-IID prophet problem and gives three concrete results: a class of MRS algorithms analyzed via variational calculus that raises the large-n guarantee from 1−1/e≈0.632 to about 0.6534 (and 0.649 under a storage constraint), tight for beta up to ≈0.58 and implementable as a streaming version that uses up to ≈1.443n samples; and a new impossibility extending the 1/e lower bound to exchangeable variables using Ramsey-type constructions and Kuhn's theorem.
AI-written summary · about
chapters (10)
- 0:00Intro
- 0:30The LI.D. Prophet Inequality
- 7:58LID. Prophet Inequalities w/ Samples: State of the Art
- 11:27Our Contribution
- 13:52First Contribution: Improved Bounds
- 14:27The Baseline for Our Approach
- 20:43Which function f should we choose (when k= n - 1)?
- 23:05Getting 1-1/e + E with MRS Algorithms
- 26:35MRS Algorithms using Continuous Functions
- 28:00Computing the Best MRS Algorithm