Abstract: We study the fair allocation of mixture 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 Pareto optimal 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
Dividing a cake is easy; dividing a pile of laundry and a box of chocolates among friends is much harder. This research, presented at IJCAI-23, explores the computational boundaries of "fairness" when we have to allocate a mixture of indivisible goods (things people want) and chores (things people hate).
In the world of multi-agent systems, "fair division" is a classic problem. Most research focuses on either all goods or all chores. Real-world scenarios, however, are often "mixed." Think of peer review: a reviewer might see a paper in their niche as a good (interesting to read) but a paper outside their expertise as a chore (painful to read).
Understanding Preference Domains
The authors focus on lexicographic preferences, where agents rank items by importance. A single "terrible chore" at the top of an agent's list is so undesirable that no amount of goods can compensate for it.
As illustrated in the hierarchy above, lexicographic preferences represent a specific subdomain of additive preferences. The paper investigates whether we can achieve three main fairness notions alongside Pareto Optimality (PO) (meaning you can't make someone better off without making someone else worse off):
- EFX (Envy-Freeness up to Any Item): The "gold standard" of relaxation. No agent envies another after removing any single item from the bundles.
- EF1 (Envy-Freeness up to One Item): A weaker version where envy is eliminated by removing some single item.
- MMS (Maximin Share): A guarantee that each agent gets a bundle they prefer at least as much as what they would get if they divided the items into $n$ piles themselves and were forced to take the worst one.
The Hardness of EFX
The most significant finding is the proof that EFX existence is NP-complete for mixed items. This settles a major question: it's not just that EFX might not exist in mixed settings; it's that even checking if it does exist is computationally grueling. The paper identifies that the non-existence of EFX is driven by "terrible chores"—highly undesirable items at the top of importance rankings. To prove this hardness, the authors used a reduction from the Exact Cover by 3-Sets (X3C) problem.
Algorithmic Solutions and Silver Linings
Despite the hardness of EFX, the authors provide several positive results for specific preference structures and fairness notions:
- Separable Success: If agents have "separable" preferences (where an agent either views all chores as more important than all goods, or vice versa), the conflict between chores and goods is simplified. For these cases, EFX + PO allocations are guaranteed to exist and can be computed in polynomial time using a modified Serial Dictatorship algorithm.
- MMS is Always Possible: The authors show that MMS + PO is always achievable in polynomial time for any mixed instance under lexicographic preferences. They developed an algorithm that identifies the "most important" chore and carefully assigns it to ensure everyone meets their Maximin Share threshold while maintaining Pareto efficiency.
- EF1 Constraints: While finding a general algorithm for EF1 + PO in mixed lexicographic settings remains an open challenge, the authors provide efficient algorithms for special instances, such as those with at least $n-1$ common terrible chores.
Conclusion
This work maps the computational landscape of fair division for mixed items. While the "gold standard" of EFX is computationally intractable in the general case, the existence of efficient algorithms for MMS and separable preferences provides practical fallbacks for system designers. Future work may extend these insights to broader additive preferences, though the NP-completeness found here already suggests significant hurdles in that domain.
Summary updated