arXiv preprint ·
Fair Prophets
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Cross-Platform vs Native Mobile Development: An Empirical Study of Software Quality Trade-offs
Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria
A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games
Guiding Agents of Quantum Games to Equilibrium using Matrix Exponential Fixed-Point Iteration
Optimal High-Order Methods for Solving Monotone Variational Inequalities
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.