How well can an online decision-maker perform compared to an all-knowing prophet? This question sits at the heart of prophet inequalities, a framework from optimal stopping theory that studies decision-making under uncertainty. A classical result guarantees that when information is revealed sequentially, a careful player can always secure at least half the expected reward of the benchmark - a surprisingly strong guarantee given the uncertainty involved. Stronger guarantees are known when future outcomes are drawn from identical distributions, but this assumption is often unrealistic in real-world applications such as online advertising auctions and hiring.

This project investigates how performance guarantees change when outcomes are drawn from non-identical distributions. We first study the simplest non-trivial case involving two distinct distributions, where the decision-maker may also choose the order in which outcomes are observed. Our methodology reduces continuous distributions to carefully chosen discrete cases and analyzes threshold-based decision strategies, enabling tractable worst-case analysis. Our main result shows that in the two-distribution setting, the worst-case performance guarantee improves to 0.8 - which exceeds the classical bound of 0.5 and falls short of the best-known guarantee in the identical-distribution case.

This suggests that distributional heterogeneity imposes a measurable cost on online decision-making. We are currently extending these techniques to three or more distributions, guided by the hypothesis that non-identically distributed guarantees are strictly worse than those under identical distributions. More broadly, this work helps bridge the gap between idealized theoretical models and the uneven conditions encountered in practical decision-making systems.