Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints

Ayumi Igarashi, Dominik Peters

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.
Figure 1: Visualization of graph structures analyzed, including paths, stars, and the complex gadgets used to prove NP-hardness for trees.
  • 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:

Figure 5: Summary of computational complexity for finding allocations that are Pareto-optimal (PO) and satisfy fairness constraints (MMS, EF1) across different graph types.
  • 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

Abstract

We study the problem of allocating indivisible items to agents with additive valuations, under the additional constraint that bundles must be connected in an underlying item graph. Previous work has considered the existence and complexity of fair allocations. We study the problem of finding an allocation that is Pareto-optimal. While it is easy to find an efficient allocation when the underlying graph is a path or a star, the problem is NP-hard for many other graph topologies, even for trees of bounded pathwidth or of maximum degree 3. We show that on a path, there are instances where no Pareto-optimal allocation satisfies envy-freeness up to one good, and that it is NP-hard to decide whether such an allocation exists, even for binary valuations. We also show that, for a path, it is NP-hard to find a Pareto-optimal allocation that satisfies maximin share, but show that a moving-knife algorithm can find such an allocation when agents have binary valuations that have a non-nested interval structure.
BibTeX
@inproceedings{igarashi2019pareto,
  author = {Ayumi Igarashi and Dominik Peters},
  title = {{Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012045},
}
Figure