# Polynomial-Time Algorithms for Fair Orientations of Chores

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 20 references that are in the map.
- First posted on arXiv 23 Jan 2025.

## Builds on (most cited first, 7 of 7)

- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [EFX Exists for Three Agents](https://mlsanity.com/paper/2002.05119/) (2020)
- [A Complete Landscape of EFX Allocations on Graphs: Goods, Chores and Mixed Manna](https://mlsanity.com/paper/2409.03594/) (2024)
- [EFX Orientations of Multigraphs](https://mlsanity.com/paper/2410.12039/) (2024)
- [EFX Allocations on Some Multi-graph Classes](https://mlsanity.com/paper/2412.06513/) (2024)
- [Fairly Dividing Mixtures of Goods and Chores under Lexicographic Preferences](https://mlsanity.com/paper/2203.07279/) (2022)
- [EF1 and EFX Orientations](https://mlsanity.com/paper/2409.13616/) (2024)

## Abstract (arXiv)

This paper addresses the problem of finding fair orientations of graphs of chores, in which each vertex corresponds to an agent, each edge corresponds to a chore, and a chore has zero marginal utility to an agent if its corresponding edge is not incident to the vertex corresponding to the agent. Recently, Zhou et al. (IJCAI, 2024) analyzed the complexity of deciding whether graphs containing a mixture of goods and chores have EFX orientations, and conjectured that deciding whether graphs containing only chores have EFX orientations is NP-complete. We resolve this conjecture by giving polynomial-time algorithms that find EF1 and EFX orientations of graphs containing only chores if they exist, even if there are self-loops. Remarkably, our result demonstrates a surprising separation between the case of goods and the case of chores, because deciding whether graphs containing only goods have EFX orientations was shown to be NP-complete by Christodoulou et al. (EC, 2023). In addition, we show the EF1 and EFX orientation problems for multigraphs to be NP-complete.