New fairness measures reshape prophet inequalities in decision making
Fair Prophets
Computer Science and Game TheoryData Structures and Algorithms
Summary
This work studies how to fairly decide when to stop and select options with uncertain outcomes, like in games or auctions. It introduces a way to measure fairness that balances different fairness goals, from average happiness to fairness for the least well-off. The authors find that depending on how fairness is measured, having full knowledge or just samples of outcomes changes how well you can do. Their results highlight limits and possibilities for fair decision-making under uncertainty.
What this means in practice
- •For auction designers: Design auction rules that fairly balance overall value and individual fairness when bidders have uncertain valuations.
- •For resource allocation teams: Improve allocation systems by understanding limits of fairness guarantees when only samples of data are available.
A theory result. No direct application yet.
Authors
Paul Duetting, Michal Feldman, Mathieu Molina
Abstract
We initiate the study of $α$-fair prophet inequalities. This interpolates between utilitarian welfare $(α=0)$, Nash welfare $(α=1)$, and Rawlsian max-min fairness $(α\to\infty)$. Given the non-linearity of the objective, it matters when the expectation is applied. For instance, for the Rawlsian objective, it matters whether we aim to maximize $\min \mathbb{E}[u_i]$ or $\mathbb{E}[\min u_i]$. We refer to the former as the ex-ante model, and the latter as the ex-post model. For ex-ante fairness, full distributional knowledge yields a tight competitive ratio of exactly $1/2$ for every $α\ge 0$. Under sample access, $O(n\log n)$ samples per distribution suffice for a constant competitive ratio when $α\in(0,1]$. In contrast, for every $α>1$, no finite number of samples improves upon the trivial $1/n$ guarantee. Thus, unlike in the utilitarian setting, full-information and sample-access prophet inequalities become fundamentally separated. For ex-post fairness, under full information, we obtain a uniform constant ratio for all $α\in(0,1)$, while for every $α>1$ the competitive ratio collapses to $1/n$. In the sample-access model, one sample per distribution suffices for each fixed $α<1$, but no sample budget depending only on $n$ yields a uniform constant guarantee as $α\to 1$. Beyond these phase transitions for $α$-fairness, our results open the door to a broader theory of prophet inequalities for non-linear welfare objectives.