# Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation

arXiv: https://arxiv.org/abs/2005.14122 · HTML: https://mlsanity.com/paper/2005.14122/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2020.

## Built on by (most cited first, 15 of 15)

- [FairNeuron: Improving Deep Neural Network Fairness with Adversary Games on Selective Neurons](https://mlsanity.com/paper/2204.02567/) (2022)
- [Learning in Multi-Stage Decentralized Matching Markets](https://mlsanity.com/paper/2102.06988/) (2021)
- [Two-Sided Matching Meets Fair Division](https://mlsanity.com/paper/2107.07404/) (2021)
- [Fair and Efficient Resource Allocation with Partial Information](https://mlsanity.com/paper/2105.10064/) (2021)
- [Fair Division with Market Values](https://mlsanity.com/paper/2410.23137/) (2024)
- [Understanding EFX Allocations: Counting and Variants](https://mlsanity.com/paper/2504.03951/) (2025)
- [Fairness in Contextual Resource Allocation Systems: Metrics and Incompatibility Results](https://mlsanity.com/paper/2212.01725/) (2022)
- [The Fairness Fair: Bringing Human Perception into Collective Decision-Making](https://mlsanity.com/paper/2312.14402/) (2023)
- [Stable Matching with Ties: Approximation Ratios and Learning](https://mlsanity.com/paper/2411.03270/) (2024)
- [Harm Ratio: A Novel and Versatile Fairness Criterion](https://mlsanity.com/paper/2410.02977/) (2024)
- [Individual Fairness under Varied Notions of Group Fairness in Bipartite Matching - One Framework to Approximate Them All](https://mlsanity.com/paper/2208.09951/) (2022)
- [Fair Grading Algorithms for Randomized Exams](https://mlsanity.com/paper/2304.06254/) (2023)
- [First-Choice Maximality Meets Ex-ante and Ex-post Fairness](https://mlsanity.com/paper/2305.04589/) (2023)
- [Simultaneous Envy and Equitability Guarantees](https://mlsanity.com/paper/2608.26410/) (2026)
- [Fair Policy Optimization in Major-Minor Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2609.36174/) (2026)

## Abstract (arXiv)

We study the problem of allocating indivisible goods among agents with additive valuations. When randomization is allowed, it is possible to achieve compelling notions of fairness such as envy-freeness, which states that no agent should prefer any other agent's allocation to her own. When allocations must be deterministic, achieving exact fairness is impossible but approximate notions such as envy-freeness up to one good can be guaranteed. Our goal in this work is to achieve both simultaneously, by constructing a randomized allocation that is exactly fair ex-ante and approximately fair ex-post. The key question we address is whether ex-ante envy-freeness can be achieved in combination with ex-post envy-freeness up to one good. We settle this positively by designing an efficient algorithm that achieves both properties simultaneously. If we additionally require economic efficiency, we obtain an impossibility result. However, we show that economic efficiency and ex-ante envy-freeness can be simultaneously achieved if we slightly relax our ex-post fairness guarantee. On our way, we characterize the well-known Maximum Nash Welfare allocation rule in terms of a recently introduced fairness guarantee that applies to groups of agents, not just individuals.