Neighborhood Stability in Assignments on Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911948140969984 |
|---|---|
| author | Aziz, Haris Lisowski, Grzegorz Suzuki, Mashbat Vollen, Jeremy |
| author_facet | Aziz, Haris Lisowski, Grzegorz Suzuki, Mashbat Vollen, Jeremy |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_05240 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Neighborhood Stability in Assignments on Graphs Aziz, Haris Lisowski, Grzegorz Suzuki, Mashbat Vollen, Jeremy Computer Science and Game Theory 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. |
| title | Neighborhood Stability in Assignments on Graphs |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2407.05240 |