  Free order prophet inequalities bound the ratio between the expected value
obtained by two parties each selecting a 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\dots$ times as great as that of the prophet. In fact, there exists a
threshold stopping rule which guarantees a gambler-to-prophet ratio of at least
$1-\frac1e=0.632\dots$. 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, 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 $\varphi^{-1}=0.618\dots$, 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 $\varphi^{-1}$, the
gambler-to-prophet ratio achievable by threshold stopping rules does not exceed
$\varphi^{-1}+o(1)$ until the number of allowed permutations grows to $O(\log
n)$. The ratio reaches $1-\frac1e-\varepsilon$ for a suitably chosen set of
$O(\text{poly}(\varepsilon^{-1})\cdot\log n)$ permutations and does not exceed
$1-\frac1e$ even when the full set of $n!$ permutations is allowed.
