# Simultaneous Envy and Equitability Guarantees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 47 references that are in the map.
- First posted on arXiv 26 Aug 2026.

## Builds on (most cited first, 30 of 31)

- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [Fair Division of Indivisible Goods: Recent Progress and Open Questions](https://mlsanity.com/paper/2208.08782/) (2022)
- [Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation](https://mlsanity.com/paper/2005.14122/) (2020)
- [EFX Exists for Three Agents](https://mlsanity.com/paper/2002.05119/) (2020)
- [Maximum Nash Welfare and Other Stories About EFX](https://mlsanity.com/paper/2001.09838/) (2020)
- [Fair and Truthful Mechanisms for Dichotomous Valuations](https://mlsanity.com/paper/2002.10704/) (2020)
- [Fair Division with Binary Valuations: One Rule to Rule Them All](https://mlsanity.com/paper/2007.06073/) (2020)
- [Almost Envy-Freeness in Group Resource Allocation](https://mlsanity.com/paper/1901.08463/) (2019)
- [Equitable Allocations of Indivisible Goods](https://mlsanity.com/paper/1905.10656/) (2019)
- [Best-of-Both-Worlds Fair-Share Allocations](https://mlsanity.com/paper/2102.04909/) (2021)
- [Fair and Efficient Online Allocations with Normalized Valuations](https://mlsanity.com/paper/2009.12405/) (2020)
- [Greedy Algorithms for Maximizing Nash Social Welfare](https://mlsanity.com/paper/1801.09046/) (2018)
- [A General Framework for Fair Allocation under Matroid Rank Valuations](https://mlsanity.com/paper/2208.07311/) (2022)
- [Weighted Fair Division with Matroid-Rank Valuations: Monotonicity and Strategyproofness](https://mlsanity.com/paper/2303.14454/) (2023)
- [Breaking the Envy Cycle: Best-of-Both-Worlds Guarantees for Subadditive Valuations](https://mlsanity.com/paper/2304.03706/) (2023)
- [EFX Allocations Exist for Binary Valuations](https://mlsanity.com/paper/2308.05503/) (2023)
- [The Fairness Fair: Bringing Human Perception into Collective Decision-Making](https://mlsanity.com/paper/2312.14402/) (2023)
- [Best-of-Both-Worlds Fair Allocation of Indivisible and Mixed Goods](https://mlsanity.com/paper/2410.06877/) (2024)
- [Exploring Relations among Fairness Notions in Discrete Fair Division](https://mlsanity.com/paper/2502.02815/) (2025)
- [Existence of Fair and Efficient Allocation of Indivisible Chores](https://mlsanity.com/paper/2507.09544/) (2025)
- [On Pareto-Optimal and Fair Allocations with Personalized Bi-Valued Utilities](https://mlsanity.com/paper/2507.18251/) (2025)
- [Equitable Allocations of Indivisible Chores](https://mlsanity.com/paper/2002.11504/) (2020)
- [On the Existence of EFX (and Pareto-Optimal) Allocations for Binary Chores](https://mlsanity.com/paper/2308.12177/) (2023)
- [Randomized Strategyproof Mechanisms with Best of Both Worlds Fairness and Efficiency](https://mlsanity.com/paper/2408.01027/) (2024)
- [Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously](https://mlsanity.com/paper/2409.01963/) (2024)
- [Best of Both Worlds Guarantees for Equitable Allocations](https://mlsanity.com/paper/2505.05809/) (2025)
- [Achieving Equitability with Subsidy](https://mlsanity.com/paper/2505.23251/) (2025)
- [Centralized Group Equitability and Individual Envy-Freeness in the Allocation of Indivisible Items](https://mlsanity.com/paper/2511.07984/) (2025)
- [Simultaneous Ordinal Maximin Share and Envy-Based Guarantees](https://mlsanity.com/paper/2602.15566/) (2026)
- [Counterexamples to EFX for Submodular and Subadditive Valuations](https://mlsanity.com/paper/2605.06451/) (2026)

## Abstract (arXiv)

Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations, revealing sharp contrasts between the two settings. For normalized binary goods, we give a polynomial-time algorithm for computing an EF1+EQ1 allocation with at most seven agents, but also construct a normalized instance with a larger number of agents for which no such allocation exists. In sharp contrast, binary chores admit the stronger EFX+EQX guarantee for any number of agents, even without normalization. We further initiate the study of cross-notion ex-ante and ex-post guarantees, asking whether randomized allocations can provide ex-ante guarantees for one notion while preserving ex-post guarantees for another.