Sample-Driven Optimal Stopping: From the Secretary Problem to the i.i.d. Prophet Inequality I: Feasible Solutions of the Continuous Stopping LP Can Be Improved to Threshold FormResearch Paper
Two classical online selection problems sit at opposite ends of an information spectrum. In the secretary problem items arrive in uniformly random order, only their relative ranks are observed, and the best possible probability of stopping on the best item tends to . In the i.i.d. prophet inequality the values are independent draws from a known distributi…