Abstract
This paper investigates the computational complexity of finding allocations of indivisible goods that are both fair (satisfying criteria like EF1 or PROP1) and maximize utilitarian welfare. While fair allocations are guaranteed to exist, finding those that also maximize total happiness is shown to be NP-hard in most cases. The authors provide a comprehensive complexity landscape and propose pseudopolynomial-time algorithms for scenarios with a fixed number of agents.
Introduction
In the field of multi-agent resource allocation, the challenge of distributing indivisible goods—items that cannot be shared or divided, such as tasks, equipment, or heirlooms—presents a fundamental tension between two desirable goals: efficiency and fairness. Efficiency is typically measured by utilitarian welfare, the sum of all agents' utilities. Fairness, on the other hand, is often defined through criteria like Envy-Freeness up to one item (EF1) or Proportionality up to one item (PROP1).
While it is well-established that EF1 and PROP1 allocations always exist and can be found efficiently, these allocations are not necessarily efficient in a utilitarian sense. Conversely, maximizing total welfare is computationally trivial (assign each item to the agent who values it most) but often results in highly unfair outcomes. This paper explores the "best of both worlds" problem: the computational complexity of finding the most efficient allocation among those that satisfy specific fairness constraints.
Methodology
The authors utilize a multi-faceted approach to map the complexity of this problem:
- Complexity Analysis: By employing mathematical reductions from known hard problems such as 3-Partition, Partition, and Knapsack, the authors establish the hardness of finding welfare-maximizing fair allocations under various conditions.
- Algorithm Design: For scenarios where the number of agents ($n$) is fixed, the authors develop Dynamic Programming (DP) algorithms. These algorithms utilize state-tracking of utility differences to find optimal fair allocations in pseudopolynomial time.
- Empirical Evaluation: To test practical performance, the authors implement their DP algorithms and compare them against Mixed Integer Linear Programming (MILP) formulations using the Gurobi solver. They evaluate these on synthetic datasets generated via the Mallows Model and Borda Utilities, simulating a range of preference correlations.
Key Results and the Complexity Landscape
The core contribution of the paper is a detailed "complexity landscape" that categorizes the difficulty of these problems based on the number of agents and the specific fairness criteria used.
As shown in the table above, the problem is generally intractable:
- Variable Number of Agents ($n$): Finding a fair utilitarian maximal (UM) allocation or maximizing welfare within fair allocations is strongly NP-hard.
- Fixed Number of Agents ($n \ge 3$): The problems remain NP-hard, though the authors' pseudopolynomial algorithms offer a theoretical path to solutions when utilities are bounded.
- The Two-Agent Case ($n=2$): This represents a unique boundary. While checking if a welfare-maximal allocation is fair is solvable in polynomial time, finding the best fair allocation remains NP-hard, as it mirrors the complexity of the Knapsack problem.
In empirical tests, the authors found that MILP solvers significantly outperformed Dynamic Programming. While DP is essential for establishing theoretical bounds, MILP scaled more effectively as the number of agents and items increased. Furthermore, their simulations revealed that while perfectly Envy-Free (EF) solutions existed in only 11.2% of cases, EF1 solutions were present in 100%, validating the practical importance of "up to one item" relaxations.
Theoretical Insights
The paper highlights a significant jump in complexity when moving from "up to one item" (EF1) to the stricter "up to any item" (EFx). For two agents, EF1 is computationally easy to verify, but EFx becomes NP-complete. This distinction is crucial for system designers who must choose between stricter fairness and computational feasibility.
Additionally, the authors address the "Efficiency vs. Fairness Gap." Because guaranteed fair allocations (like EF1) may only capture a fraction of potential utilitarian welfare, the search for algorithms that specifically target Utilitarian Maximal (UM) fair allocations is justified as a means to minimize this loss of efficiency.
Conclusion and Future Directions
This research provides a rigorous foundation for understanding the limits of computing fair and efficient allocations. However, several avenues remain open:
- Normalized Utilities: A persistent open problem is the complexity for two agents when utilities are normalized (e.g., summing to a constant like 1000).
- Algorithm Optimization: Future work may focus on faster algorithms for specific utility functions to reduce the exponential dependence on the number of agents.
- Real-World Data: Applying these models to human-generated utility data (such as from platforms like
spliddit.org) could reveal whether "human-like" preferences offer structures that are easier to solve than synthetic models.
Summary updated