Corelab Seminar
2020-2021

Makis Arsenis
Constrained-Order Prophet Inequalities

Abstract.
Prophet inequalities bound the ratio between the expected value obtained by two parties each selecting one value from a set of independent random variables: a "prophet" who knows the value of each variable and may select the maximum one, and a "gambler" who observes the values in a particular order but must select one of them immediately after observing it, without knowing what values will be sampled for the unobserved variables.
In this talk we will be investigating a novel variation of the prophet inequality setting which interpolates between two well-known extremes: the free order and the adversarial order variant. We assume there is a predefined set of permutations of the set indexing the random variables, and the gambler is free to choose the order of observation to be any one of these predefined permutations. Surprisingly, we show that even when only two orderings are allowed (namely, the forward and reverse orderings) the gambler-to-prophet ratio improves from 1/2 to φ^{-1} = (\sqrt{5} - 1) / 2 = 0.618... the inverse of the golden ratio. As the number of allowed permutations grows beyond 2, a striking "double plateau" phenomenon emerges: after reaching φ^{-1}, the gambler-to-prophet ratio achievable by uniform-threshold stopping rules does not exceed φ^{-1} + o(1) until the number of allowed permutations grows to Θ(log n). The ratio reaches 1 - 1/e - ε for a suitably chosen set of O( poly(ε^{-1}) log n) permutations and does not exceed 1 - 1/e even when the full set of n! permutations is allowed.

This talk is based on joint work with Odysseas Drosis (EPFL) and Robert Kleinberg (Cornell) and will appear in SODA '21.

back