# Fair and Efficient Allocations of Chores under Bivalued Preferences

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Oct 2021.

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

- [Temporal Fair Division of Indivisible Items](https://mlsanity.com/paper/2410.14593/) (2024)
- [Online Fair Division for Personalized 2-Value Instances](https://mlsanity.com/paper/2505.22174/) (2025)
- [(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna](https://mlsanity.com/paper/2202.02672/) (2022)
- [Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations](https://mlsanity.com/paper/2302.03087/) (2023)

## Abstract (arXiv)

We study the problem of fair and efficient allocation of a set of indivisible chores to agents with additive cost functions. We consider the popular fairness notion of envy-freeness up to one good (EF1) with the efficiency notion of Pareto-optimality (PO). While it is known that an EF1+PO allocation exists and can be computed in pseudo-polynomial time in the case of goods, the same problem is open for chores. Our first result is a strongly polynomial-time algorithm for computing an EF1+PO allocation for bivalued instances, where agents have (at most) two disutility values for the chores. To the best of our knowledge, this is the first non-trivial class of indivisible chores to admit an EF1+PO allocation and an efficient algorithm for its computation. We also study the problem of computing an envy-free (EF) and PO allocation for the case of divisible chores. While the existence of an EF+PO allocation is known via competitive equilibrium with equal incomes, its efficient computation is open. Our second result shows that for bivalued instances, an EF+PO allocation can be computed in strongly polynomial-time.