# First-Choice Maximality Meets Ex-ante and Ex-post Fairness

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 59 references that are in the map.
- First posted on arXiv 8 May 2023.

## Builds on (most cited first, 11 of 11)

- [Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation](https://mlsanity.com/paper/2005.14122/) (2020)
- [Fair Division Under Cardinality Constraints](https://mlsanity.com/paper/1804.09521/) (2018)
- [Best-of-Both-Worlds Fair-Share Allocations](https://mlsanity.com/paper/2102.04909/) (2021)
- [Simultaneously Achieving Ex-ante and Ex-post Fairness](https://mlsanity.com/paper/2004.02554/) (2020)
- [Fair and Efficient Allocations under Lexicographic Preferences](https://mlsanity.com/paper/2012.07680/) (2020)
- [Efficient, Fair, and Incentive-Compatible Healthcare Rationing](https://mlsanity.com/paper/2102.04384/) (2021)
- [On Fair Division under Heterogeneous Matroid Constraints](https://mlsanity.com/paper/2010.07280/) (2020)
- [Best of Both Worlds: Agents with Entitlements](https://mlsanity.com/paper/2209.03908/) (2022)
- [Subgame Perfect Equilibria of Sequential Matching Games](https://mlsanity.com/paper/1804.10353/) (2018)
- [The Vigilant Eating Rule: A General Approach for Probabilistic Economic Design with Constraints](https://mlsanity.com/paper/2008.08991/) (2020)
- [Favoring Eagerness for Remaining Items: Designing Efficient, Fair, and Strategyproof Mechanisms](https://mlsanity.com/paper/2109.08856/) (2021)

## Abstract (arXiv)

For the assignment problem where multiple indivisible items are allocated to a group of agents given their ordinal preferences, we design randomized mechanisms that satisfy first-choice maximality (FCM), i.e., maximizing the number of agents assigned their first choices, together with Pareto efficiency (PE). Our mechanisms also provide guarantees of ex-ante and ex-post fairness. The generalized eager Boston mechanism is ex-ante envy-free, and ex-post envy-free up to one item (EF1). The generalized probabilistic Boston mechanism is also ex-post EF1, and satisfies ex-ante efficiency instead of fairness. We also show that no strategyproof mechanism satisfies ex-post PE, EF1, and FCM simultaneously. In doing so, we expand the frontiers of simultaneously providing efficiency and both ex-ante and ex-post fairness guarantees for the assignment problem.