Neighborhood Stability in Assignments on Graphs

Haris Aziz, Grzegorz Lisowski, Mashbat Suzuki, Jeremy Vollen

Abstract

We study the problem of assigning agents to the vertices of a graph such that no pair of neighbors can benefit from swapping assignments—a property we term neighborhood stability. We further assume that agents' utilities are based solely on their preferences over the assignees of adjacent vertices and that those preferences are binary. Having shown that even this very restricted setting does not guarantee neighborhood stable assignments, we focus on special cases that provide such guarantees. We show that when the graph is a cycle or a path, a neighborhood stable assignment always exists for any preference profile. Furthermore, we give a general condition under which neighborhood stable assignments always exist. For each of these results, we give a polynomial-time algorithm to compute a neighborhood stable assignment.

Introduction

The problem of assigning agents to positions—such as seating at a dinner party or roles in a project—is a fundamental challenge in computational social choice. Traditionally, stability in such assignments requires that no two agents in the entire system wish to swap places. However, global stability is often unattainable. This paper introduces neighborhood stability, a relaxation where swaps are only considered between agents who are adjacent in the underlying "seat graph." This model is motivated by the reality that agents often only have the information or social proximity to coordinate swaps with their immediate neighbors.

Problem Formulation and Binary Preferences

We consider a set of agents to be assigned to the vertices of a graph. Each agent has binary preferences, represented by a directed preference graph where an edge from agent $i$ to agent $j$ indicates that $i$ approves of $j$. An agent's utility is the number of their neighbors in the seat graph whom they approve. An assignment is neighborhood stable if no two adjacent agents can both increase their utility (or one increases while the other stays the same) by swapping positions.

Example of a preference graph and an assignment on a path.

Stability on Paths and Cycles

A primary contribution of this work is proving that neighborhood stable assignments are guaranteed to exist for specific graph topologies. For paths and cycles, the authors demonstrate that a stable assignment can always be found in $O(n^3)$ time.

For cycles, the proof utilizes a novel algorithm that partitions the preference graph into paths and maps them onto the cycle. The existence of stability in cycles is particularly noteworthy, as even slight increases in preference complexity (e.g., moving from binary to cardinal utilities) or stronger stability requirements (like blocking pairs at distance 2) can lead to cases where no stable assignment exists.

General Conditions and Counterexamples

Beyond simple structures, the paper establishes a general condition for existence based on the relationship between the seat graph's "openness" and the preference graph's "cyclicity." Specifically, a neighborhood stable assignment is guaranteed if the number of leaf nodes (degree-one vertices) in the seat graph is at least as large as the Directed Feedback Vertex Set (DFVS) of the preference graph. This suggests that "leafy" graphs are better at absorbing the tensions created by cycles in agent preferences.

However, neighborhood stability is not universal. The authors provide a counterexample using a balanced complete bipartite graph ($K_{3,3}$) and a specific preference profile where no assignment is stable.

A preference graph and the $K_{3,3}$ seat graph used as a counterexample for the existence of neighborhood stability.

Conclusion

While neighborhood stability is a weaker requirement than global stability, it remains a robust and computationally tractable solution for many common graph structures. Future work may explore the "price of stability" in these contexts and extend these results to more complex graph families like trees or grids.

Summary updated

Abstract

We study the problem of assigning agents to the vertices of a graph such that no pair of neighbors can benefit from swapping assignments -- a property we term neighborhood stability. We further assume that agents' utilities are based solely on their preferences over the assignees of adjacent vertices and that those preferences are binary. Having shown that even this very restricted setting does not guarantee neighborhood stable assignments, we focus on special cases that provide such guarantees. We show that when the graph is a cycle or a path, a neighborhood stable assignment always exists for any preference profile. Furthermore, we give a general condition under which neighborhood stable assignments always exist. For each of these results, we give a polynomial-time algorithm to compute a neighborhood stable assignment.
BibTeX
@misc{aziz2024neighborhood,
  author = {Haris Aziz and Grzegorz Lisowski and Mashbat Suzuki and Jeremy Vollen},
  title = {{Neighborhood Stability in Assignments on Graphs}},
  year = {2024},
  eprint = {2407.05240},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.05240},
}
Figure