# Simultaneously Achieving Ex-ante and Ex-post Fairness

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

## Key facts

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

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

- [Two-Sided Matching Meets Fair Division](https://mlsanity.com/paper/2107.07404/) (2021)
- [Understanding EFX Allocations: Counting and Variants](https://mlsanity.com/paper/2504.03951/) (2025)
- [The Fairness Fair: Bringing Human Perception into Collective Decision-Making](https://mlsanity.com/paper/2312.14402/) (2023)
- [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)

## Abstract (arXiv)

We present a polynomial-time algorithm that computes an ex-ante envy-free lottery over envy-free up to one item (EF1) deterministic allocations. It has the following advantages over a recently proposed algorithm: it does not rely on the linear programming machinery including separation oracles; it is SD-efficient (both ex-ante and ex-post); and the ex-ante outcome is equivalent to the outcome returned by the well-known probabilistic serial rule. As a result, we answer a question raised by Freeman, Shah, and Vaish (2020) whether the outcome of the probabilistic serial rule can be implemented by ex-post EF1 allocations. In the light of a couple of impossibility results that we prove, our algorithm can be viewed as satisfying a maximal set of properties. Under binary utilities, our algorithm is also ex-ante group-strategyproof and ex-ante Pareto optimal. Finally, we also show that checking whether a given random allocation can be implemented by a lottery over EF1 and Pareto optimal allocations is NP-hard.