Neighborhood Stability in Assignments on Graphs

Jeremy Vollen, Mashbat Suzuki, Grzegorz Lisowski, Haris Aziz

TL;DR

This paper introduces and explores neighborhood stability, a relaxed version of stability for assigning agents to positions on a graph (like seating arrangements or role assignments). The authors prove that while stable assignments aren't guaranteed for all graphs, they always exist and can be found in polynomial time for cycles and paths, and they provide a general condition for existence based on the "leafiness" of the seat graph relative to the complexity of agent preferences.

What Problem Does This Paper Address?

Imagine you are organizing a dinner party or assigning employees to project roles. Each person has preferences: they like some colleagues (binary "approval") and are indifferent toward others. Their happiness (utility) depends on how many people they like are sitting next to them.

In classic "stable" assignment models, no two people in the entire group should want to swap places. However, global stability is often impossible to achieve. This paper tackles a more realistic constraint: Neighborhood Stability. It assumes that swaps only happen between people who are already neighbors on the graph (e.g., sitting next to each other). This is motivated by the idea that people usually only have enough information or interaction to coordinate a swap with their immediate neighbors.

The core question is: Under what graph structures and preference profiles is a neighborhood stable assignment guaranteed to exist?

Methods

The authors focus on binary preferences, where an agent's preference is represented as a directed graph (if $i \to j$, agent $i$ approves of agent $j$).

Key methodological approaches include:

  • Path Partitions: For cycle graphs, the authors develop a novel algorithm that partitions the preference graph into paths and maps them onto the cycle. They use a progress measure (the number of agents who approve of their neighbor to the "right") to prove the algorithm eventually terminates at a stable state.
  • Greedy Construction: For path graphs, they use a sequential assignment strategy to ensure no blocking pairs exist within a distance of two.
  • Graph Theory Metrics: For general graphs, they employ the Directed Feedback Vertex Set (DFVS)—a measure of how "cyclic" the preference graph is—and compare it to the number of leaf nodes (degree-one vertices) in the seat graph.

Datasets

Not discussed in the paper. As a theoretical contribution to computational game theory and graph theory, the paper relies on mathematical proofs and algorithmic analysis rather than empirical datasets or benchmarks.

Key Insights and Ideas

  • The Power of Locality: Restricting swaps to neighbors significantly expands the set of graphs that admit stable outcomes. While previous research showed that even simple paths might not have "globally" stable assignments, this paper shows they always have neighborhood stable ones.
  • Cycles are Surprisingly Stable: One of the most significant "aha" moments is the proof that cycles always admit neighborhood stable assignments under binary preferences. This is surprising because even slightly more complex preferences (like cardinal utilities) or slightly stronger stability requirements (blocking pairs at distance 2) lead to non-existence.
  • The Leaf-to-DFVS Ratio: The authors find a beautiful link between the "messiness" of preferences and the "openness" of the seat graph. If a seat graph has enough "ends" (leaves) to "absorb" the agents who are part of cycles in the preference graph (the DFVS), stability is guaranteed.

Key Results

  • Cycles and Paths: The authors provide algorithms with $O(n^3)$ time complexity to compute neighborhood stable assignments for any cycle or path graph.
  • General Existence Condition: A neighborhood stable assignment is guaranteed if the number of leaves in the seat graph is greater than or equal to the DFVS number of the preference graph.
  • Planar Preference Bonus: As a corollary, if the preference graph is planar, any seat graph where at least 60% of the nodes are leaves will always have a neighborhood stable assignment.
  • Counterexamples: The paper proves that neighborhood stability is not guaranteed for all graphs; they provide a specific counterexample using a balanced complete bipartite graph ($K_{3,3}$) with six agents where no stable assignment exists.

Limitations and Future Work

  • Binary Preferences: The positive results for cycles and paths rely on binary (approve/disapprove) preferences. The authors note that if preferences are "cardinal" (e.g., assigning different numerical values to different friends), stability is no longer guaranteed on a cycle.
  • Graph Restrictions: While paths and cycles are solved, the status of other common structures like grids or trees remains an open question.
  • Efficiency vs. Stability: The paper focuses on the existence of stability but doesn't explore the "price of stability"—how much total social welfare (the sum of all agents' utilities) is sacrificed to ensure no one wants to swap.
  • Incomplete Information: The authors suggest that future models could more explicitly incorporate limited information, where agents only know the preferences of their immediate neighbors.

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{vollen2024neighborhood,
  author = {Jeremy Vollen and Mashbat Suzuki and Grzegorz Lisowski and Haris Aziz},
  title = {{Neighborhood Stability in Assignments on Graphs}},
  year = {2024},
  eprint = {2407.05240},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.05240},
}

Loading related content...

Figure