Abstract
In many real-world fair division scenarios, such as the allocation of land parcels or contiguous time slots, items possess an underlying spatial or temporal structure. This paper investigates the computational complexity of finding Pareto-optimal (PO) allocations when each agent's bundle must form a connected subgraph of a given graph $G$. We demonstrate that while finding PO allocations is computationally efficient for simple topologies like paths and stars, the problem becomes NP-hard for trees. Furthermore, we explore the compatibility of Pareto-optimality with standard fairness notions like Envy-Freeness up to one item (EF1) and Maximin Share (MMS), identifying significant computational hurdles even on simple graph structures.
What Problem Does This Paper Address?
In the traditional fair division literature, it is often assumed that any subset of items can be assigned to any agent. However, real-world constraints often dictate that items must be contiguous or connected to be useful—for example, classroom hours must be consecutive, or land plots must be adjacent.
While finding a Pareto-optimal (PO) allocation—one where no agent can be made better off without making another worse off—is trivial in unconstrained settings, adding connectivity constraints fundamentally changes the computational landscape. This paper seeks to map the boundaries of tractability for finding PO allocations across different graph structures and examines whether these efficient allocations can simultaneously satisfy fairness criteria like Envy-Freeness up to one item (EF1) or Maximin Share (MMS).
Methods
The authors employ a combination of algorithmic design and computational complexity analysis:
- Algorithmic Design: For simple graph topologies, the authors provide polynomial-time algorithms. For stars, the problem is reduced to a maximum weight bipartite matching problem. For paths, they utilize a recursive "left-to-right" allocation strategy.
- Complexity Theory: To establish hardness for more complex structures, the authors use Turing reductions from Exact-3-Cover (X3C). They construct sophisticated "gadget" graphs where the existence of a PO allocation with specific properties implies a solution to an NP-complete problem.
- Fairness Integration: The study adapts the "moving-knife" algorithm, typically used in divisible cake-cutting, to the discrete setting of indivisible items on a path under specific valuation constraints.
Key Insights and Ideas
- The Complexity Leap: Connectivity constraints break the "greedy" efficiency of standard allocation. In unconstrained settings, one simply gives each item to the agent who values it most. With connectivity, this approach can leave behind isolated fragments that cannot be assigned to any agent, leading to Pareto-inefficiency.
- Topology is Destiny: The computational difficulty is strictly tied to the shape of the graph $G$. Paths and stars remain tractable, but trees—even those with low degree or small diameter—render the problem NP-hard.
- Fairness-Efficiency Trade-off: On a path, while an EF1 allocation is guaranteed to exist and a PO allocation is easy to find, determining if an allocation exists that is both PO and EF1 is NP-hard.
- Non-Nested Valuations: A notable exception occurs with "non-nested" interval valuations on a path, where agents' interests are roughly the same length and ordered. In this specific case, a moving-knife variant can successfully find an allocation that is both efficient and fair.
Key Results
The paper's findings are summarized in the following table of complexity results:
- Positive Results: Finding a PO allocation on a path or star is achievable in polynomial time. Furthermore, for agents with identical additive valuations on a path, a PO and EF1 allocation can always be found efficiently.
- Negative Results: Finding a PO allocation on a tree is NP-hard, even with binary (0/1) valuations. On a path, there are instances where no allocation is simultaneously PO and EF1, and finding a PO+MMS allocation is NP-hard even though its existence is guaranteed.
Limitations and Future Work
While the boundaries for trees and paths are now well-defined, several intermediate graph structures remain unexplored. Specifically, the authors identify caterpillar graphs and cycles as open problems for future research. Additionally, the current work focuses on "goods" (positive value); extending these connectivity constraints to "chores" (negative value, such as undesirable shifts) represents a promising future direction where connectivity might represent a continuous block of labor.
Summary updated