Constrained-Order Prophet Inequalities

Free order 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 is free to choose the order in which to observe the values but must select one of them immediately after observing it, without knowing what values will be sampled for the unobserved variables. It is known that the gambler can always ensure an expected payoff at least 0.669. . . times as great as that of the prophet. In fact, even if the gambler uses a threshold stopping rule, meaning there is a fixed threshold value such that the gambler rejects every sample below the threshold and accepts every sample above it, the threshold can always be chosen so that the gambler-to-prophet ratio is at least 1 -1 e ≈ 0.632 . . .. In contrast, if the gambler must observe the values in a predetermined order, the tight bound for the gambler-to-prophet ratio is 1/2.

In this work we investigate a model that interpolates between these two extremes. 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 to ϕ -1 = 1 2 ( √ 5 -1) = 0.618 . . ., the inverse of the golden ratio. As the number of allowed permutations grows beyond 2, a striking "double plateau" phenomenon emerges: after increasing from 0.5 to ϕ -1 when two permutations are allowed, the gambler-to-prophet ratio achievable by threshold stopping rules does not exceed ϕ -1 + o(1) until the number of allowed permutations grows to O(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.