Fairly Allocating Goods and (Terrible) Chores

Hadi Hosseini, Aghaheybat Mammadov, Tomasz Was

Abstract

We study the fair allocation of mixtures of indivisible goods and chores under lexicographic preferences—a subdomain of additive preferences. A prominent fairness notion for allocating indivisible items is envy-freeness up to any item (EFX). Yet, its existence and computation has remained a notable open problem. By identifying a class of instances with "terrible chores", we show that determining the existence of an EFX allocation is NP-complete. This result immediately implies the intractability of EFX under additive preferences. Nonetheless, we propose a natural subclass of lexicographic preferences for which an EFX and Pareto optimal (PO) allocation is guaranteed to exist and can be computed efficiently for any mixed instance. Focusing on two weaker fairness notions, we investigate finding EF1 and PO allocations for special instances with terrible chores, and show that MMS and PO allocations can be computed efficiently for any mixed instance with lexicographic preferences.

Introduction

Fair division is the mathematical study of how to divide resources among agents with different preferences. While much work has traditionally focused on either "goods" (items agents desire) or "chores" (tasks agents wish to avoid), real-world scenarios—such as assigning peer-review papers or medical equipment—often involve a mixture of both.

The "gold standard" for fairness in the context of indivisible items is EFX (Envy-Free up to any item). An allocation is considered EFX if no agent envies another after removing any single item from the envied agent's bundle (if it is a good) or the envious agent's bundle (if it is a chore). Despite its theoretical appeal, the existence and computational feasibility of EFX allocations has remained a significant open problem in the field.

Preference Hierarchies and Methods

This research investigates these problems within a hierarchy of preference models, specifically focusing on lexicographic preferences where agents rank items by strict importance. This domain serves as a bridge between simple goods-only scenarios and complex mixed-item additive preferences.

Hierarchy of preference models for mixed items, showing the relationship between additive, lexicographic, and separable preferences.

The authors employ a combination of computational complexity analysis and algorithmic design:

  • Hardness Reductions: To prove NP-completeness, the study uses a reduction from the Exact Cover by 3-Sets (X3C) problem, constructing instances where an EFX allocation exists if and only if a perfect set cover exists.
  • Algorithmic Design: For positive results, the authors utilize variations of the Serial Dictatorship mechanism and Phase-based Allocation. These processes involve ordering agents to pick their most preferred items or least-hated chores according to specific quotas to maintain fairness across the distribution.

Key Insights: The "Terrible Chore"

A central contribution of this work is the identification of "terrible chores"—items so undesirable they are ranked as more important than any good. The authors demonstrate that the non-existence of EFX often hinges on the presence and distribution of these specific items.

Example of lexicographic preferences where agents rank chores (-) and goods (+). Underlined items represent specific assignments in a proof context.

Key Results

  • EFX Complexity: Determining the existence of an EFX allocation is NP-complete for lexicographic mixed instances. This provides the first computational intractability result for EFX in a domain that includes additive valuations.
  • Separability as a Solution: By restricting preferences to be "separable" (where either all chores are worse than all goods, or vice versa), EFX and Pareto Optimal (PO) allocations are guaranteed to exist and are computable in polynomial time.
  • MMS Robustness: While EFX and EF1 struggle with efficiency in mixed settings, the authors show that a Maximin Share (MMS) + PO allocation always exists and can be found in polynomial time, regardless of the number of terrible chores.
  • EF1 + PO: If an instance has at least $n-1$ common terrible chores (where $n$ is the number of agents), an EF1+PO allocation can be computed efficiently.

Conclusion and Future Work

This paper settles a major open question by proving the NP-completeness of EFX existence in mixed settings. While EFX is computationally hard, the research highlights that MMS remains a robust and achievable fairness notion.

Future work remains in closing the gap for EF1+PO results. While the case for $n-1$ common terrible chores is solved, existence and computation for instances with fewer chores remains an open challenge. Additionally, exploring if other restricted preference domains (such as bivalued utilities) offer easier paths to EFX could provide further insights into the boundaries of fair allocation.

Summary updated

Abstract

We study the fair allocation of mixtures of indivisible goods and chores under lexicographic preferences$\unicode{x2014}$a subdomain of additive preferences. A prominent fairness notion for allocating indivisible items is envy-freeness up to any item (EFX). Yet, its existence and computation has remained a notable open problem. By identifying a class of instances with "terrible chores", we show that determining the existence of an EFX allocation is NP-complete. This result immediately implies the intractability of EFX under additive preferences. Nonetheless, we propose a natural subclass of lexicographic preferences for which an EFX and Pareto optimal (PO) allocation is guaranteed to exist and can be computed efficiently for any mixed instance. Focusing on two weaker fairness notions, we investigate finding EF1 and PO allocations for special instances with terrible chores, and show that MMS and PO allocations can be computed efficiently for any mixed instance with lexicographic preferences.
BibTeX
@inproceedings{hosseini2023fairly,
  author = {Hadi Hosseini and Aghaheybat Mammadov and Tomasz Was},
  title = {{Fairly Allocating Goods and (Terrible) Chores}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=eUbZATjdnQ},
}
Figure