# Existence of Fair and Efficient Allocation of Indivisible Chores

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2025.

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

- [Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO](https://mlsanity.com/paper/2607.23367/) (2026)
- [Simultaneous Envy and Equitability Guarantees](https://mlsanity.com/paper/2608.26410/) (2026)

## Abstract (arXiv)

We study the problem of allocating indivisible chores among agents with additive cost functions in a fair and efficient manner. A major open question in this area is whether there always exists an allocation that is envy-free up to one chore (EF1) and Pareto optimal (PO). Our main contribution is to provide a positive answer to this question by proving the existence of such an allocation for indivisible chores under additive cost functions. This is achieved by a novel combination of a fixed point argument and a discrete algorithm, providing a significant methodological advance in this area. Our additional key contributions are as follows. We show that there always exists an allocation that is EF1 and fractional Pareto optimal (fPO), where fPO is a stronger efficiency concept than PO. We also show that an EF1 and PO allocation can be computed in polynomial time when the number of agents is constant. Finally, we extend all of these results to the more general setting of weighted EF1 (wEF1), which accounts for the entitlements of agents.