# On the Existence of EFX (and Pareto-Optimal) Allocations for Binary Chores

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Aug 2023.

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

- [Simultaneous Envy and Equitability Guarantees](https://mlsanity.com/paper/2608.26410/) (2026)

## Abstract (arXiv)

We study the problem of allocating a group of indivisible chores among agents while each chore has a binary marginal. We focus on the fairness criteria of envy-freeness up to any item (EFX) and investigate the existence of EFX allocations. We show that when agents have additive binary cost functions, there exist EFX and Pareto-optimal (PO) allocations that can be computed in polynomial time. To the best of our knowledge, this is the first setting of a general number of agents that admits EFX and PO allocations, before which EFX and PO allocations have only been shown to exist for three bivalued agents. We further consider more general cost functions: cancelable and general monotone (both with binary marginal). We show that EFX allocations exist and can be computed for binary cancelable chores, but EFX is incompatible with PO. For general binary marginal functions, we propose an algorithm that computes (partial) envy-free (EF) allocations with at most n-1 unallocated items.