# Fair Allocation of Two Types of Chores

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

## Key facts

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

## 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)
- [Fairness in Repeated Matching: A Maximin Perspective](https://mlsanity.com/paper/2510.04624/) (2025)
- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)

## Abstract (arXiv)

We consider the problem of fair allocation of indivisible chores under additive valuations. We assume that the chores are divided into two types and under this scenario, we present several results. Our first result is a new characterization of Pareto optimal allocations in our setting, and a polynomial-time algorithm to compute an envy-free up to one item (EF1) and Pareto optimal allocation. We then turn to the question of whether we can achieve a stronger fairness concept called envy-free up any item (EFX). We present a polynomial-time algorithm that returns an EFX allocation. Finally, we show that for our setting, it can be checked in polynomial time whether an envy-free allocation exists or not.