# Breaking the Envy Cycle: Best-of-Both-Worlds Guarantees for Subadditive Valuations

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

## Key facts

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

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

- [Stable Matching with Ties: Approximation Ratios and Learning](https://mlsanity.com/paper/2411.03270/) (2024)
- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)
- [Simultaneous Envy and Equitability Guarantees](https://mlsanity.com/paper/2608.26410/) (2026)

## Abstract (arXiv)

We study best-of-both-worlds guarantees for the fair division of indivisible items among agents with subadditive valuations. Our main result establishes the existence of a random allocation that is simultaneously ex-ante frac12-envy-free, ex-post frac12-EFX and ex-post EF1, for every instance with subadditive valuations. We achieve this result by a novel polynomial-time algorithm that randomizes the well-established envy cycles procedure in a way that provides ex-ante fairness. Notably, this is the first best-of-both-worlds fairness guarantee for subadditive valuations, even when considering only EF1 without EFX.