Consider a gambler who observes the realizations of n independent, non-negative, distribution-labeled random variables arriving in a uniform random order and can stop the sequence at any time to obtain a reward of the most recent observation. In 2017, Correa et al. showed that when all distributions are identical, it is possible to design a stopping time that achieves a \beta \approx 0.745 fraction of the maximum value (the ``prophet'' benchmark), matching an upper bound of Hill and Kertz. In 2019, Correa et al. showed that when the distributions differ, it is no longer possible to achieve this bound: they prove an upper bound of \sqrt{3 - 1 < 0.74 on the best approximation ratio. We show that  it is possible to asymptotically achieve the \beta \approx 0.745 bound even in the case of non-identical distributions, as long as we are allowed to remove a small constant number of distributions. Formally, we show that for any \varepsilon, there exists a constant C_{\varepsilon = poly(1/\varepsilon) (independent of n)such that after removing C_{\varepsilon} distributions of our choice, we can achieve a (\beta - \varepsilon)-approximation to the resulting maximum. We additionally show }  it is possible to asymptotically achieve an exact \beta approximation ratio for several natural classes of problem instances, including small prophets (where each distribution is concentrated near zero) and frequent prophets (where each distribution occurs at least some number of times) .
We introduce a new decomposition technique for random variables that maps a generic instance of the prophet inequalities problem to a new instance where all but a constant number of variables have a tractable structure that we refer to as (\varepsilon, \delta)-smallness. Using this technique, we make progress on several outstanding problems in the area: - We show that , even in the case of non-identical distributions, it is possible to achieve (arbitrarily close to) the optimal approximation ratio of \beta \approx 0.745 as long as we are allowed to remove a small constant number of distributions. - We show that for = poly(1/\varepsilon) (independent of n)such that after removing C_{\varepsilon} distributions of our choice, we can achieve a (\beta - \varepsilon)-approximation to the resulting maximum. We additionally show } frequent instances of prophet inequalities (where each distribution reoccurs some number of times), it is possible to achieve the optimal approximation ratio of \beta (improving over the previous best-known bound of 0.738). - We give a new, simpler proof of Kertz's optimal approximation guarantee of \beta \approx 0.745 for prophet inequalities with i.i.d. distributions. The proof is primal-dual and simultaneously produces upper and lower bounds. - Using this decomposition in combination with a novel convex programming formulation, we construct the first Efficient PTAS for the Optimal Ordering problem .
R
Consider a gambler who observes the realizations of n independent, non-negative, distribution-labeled random variables arriving in a uniform random order and can stop the sequence at any time to obtain a reward of the most recent observation. In 2017, Correa et al. showed that when all distributions are identical, it is possible to design a stopping time that achieves a \beta \approx 0.745 fraction of the maximum value (the ``prophet'' benchmark), matching an upper bound of Hill and Kertz. In 2019, Correa et al. showed that when the distributions differ, it is no longer possible to achieve this bound: they prove an upper bound of \sqrt{3
We introduce a new decomposition technique for random variables that maps a generic instance of the prophet inequalities problem to a new instance where all but a constant number of variables have a tractable structure that we refer to as (\varepsilon, \delta)-smallness. Using this technique, we make progress on several outstanding problems in the area:
D
1 < 0.74 on the best approximation ratio.
A
, even in the case of non-identical distributions,
R
asymptotically achieve the
achieve (arbitrarily close to) the optimal approximation ratio of
D
bound even in the case of non-identical distributions,
R
Formally, we
- We
D
any \varepsilon, there exists a constant C_{\varepsilon
A
frequent instances of prophet inequalities (where each distribution reoccurs some number of times),
R
asymptotically achieve an exact \beta approximation ratio for several natural classes of problem instances, including small prophets (where each distribution is concentrated near zero) and frequent prophets (where each distribution occurs at least some number of times)
achieve the optimal approximation ratio of \beta (improving over the previous best-known bound of 0.738). - We give a new, simpler proof of Kertz's optimal approximation guarantee of \beta \approx 0.745 for prophet inequalities with i.i.d. distributions. The proof is primal-dual and simultaneously produces upper and lower bounds. - Using this decomposition in combination with a novel convex programming formulation, we construct the first Efficient PTAS for the Optimal Ordering problem