The Rawlsian Prophet: Max-Min Fair Online Allocation.

Abstract: 

Prophet inequalities are a central framework in online stochastic decision making, comparing online algorithms to an omniscient benchmark. The utilitarian objective of maximizing expected total value is well understood, with tight competitive ratios across full-information, sample-based, and combinatorial settings.

We study prophet inequalities under Rawlsian max-min fairness objectives, and distinguish between two natural notions of fairness: ex-ante and ex-post. The former aims to maximize the minimum expected value, while the latter seeks to maximize the expected minimum value. For the ex-ante objective, we show that with full distributional knowledge, the optimal competitive ratio is 1/2 even for combinatorial XOS valuations, matching the guarantee for the utilitarian objective. However, in sharp contrast to utilitarian prophet inequalities, for which a single sample per distribution suffices to attain the optimal competitive ratio, we show that in the worst-case, no finite number of samples provides any improvement over the performance achievable without sample access (namely, 1/n). For the ex-post objective, we establish that the competitive ratio is Θ(1/n), even with full knowledge of the distributions, implying that no positive constant guarantee is achievable. This result separates ex-post fairness from both utilitarian and ex-ante objectives, each of which admits a constant-factor prophet inequality.

Finally, we show that under mild bounded-moment assumptions, this hierarchy reverses: a simple online algorithm for the ex-post objective asymptotically matches the prophet’s performance as the horizon grows, while both the utilitarian and ex-ante objectives remain strictly bounded away from the prophet benchmark

Posted on Apr 6, 2026 in ACGO, Seminars