Stability in Distance Preservation Games on Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915803539963904 |
|---|---|
| author | Deligkas, Argyrios Eiben, Eduard Goldsmith, Tiger-Lily Knop, Dušan Schierreich, Šimon |
| author_facet | Deligkas, Argyrios Eiben, Eduard Goldsmith, Tiger-Lily Knop, Dušan Schierreich, Šimon |
| contents | We introduce a new class of network allocation games called graphical distance preservation games. Here, we are given a graph, called a topology, and a set of agents that need to be allocated to its vertices. Moreover, every agent has an ideal (and possibly different) distance in which to be from some of the other agents. Given an allocation of agents, each one of them suffers a cost that is the sum of the differences from the ideal distance for each agent in their subset. The goal is to decide whether there is a stable allocation of the agents, i.e., no agent would like to deviate from their location. Specifically, we consider three different stability notions: envy-freeness, swap stability, and jump stability. We perform a comprehensive study of the (parameterized) complexity of the problem in three different dimensions: the topology of the graph, the number of agents, and the structure of preferences of the agents. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_15784 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Stability in Distance Preservation Games on Graphs Deligkas, Argyrios Eiben, Eduard Goldsmith, Tiger-Lily Knop, Dušan Schierreich, Šimon Computer Science and Game Theory We introduce a new class of network allocation games called graphical distance preservation games. Here, we are given a graph, called a topology, and a set of agents that need to be allocated to its vertices. Moreover, every agent has an ideal (and possibly different) distance in which to be from some of the other agents. Given an allocation of agents, each one of them suffers a cost that is the sum of the differences from the ideal distance for each agent in their subset. The goal is to decide whether there is a stable allocation of the agents, i.e., no agent would like to deviate from their location. Specifically, we consider three different stability notions: envy-freeness, swap stability, and jump stability. We perform a comprehensive study of the (parameterized) complexity of the problem in three different dimensions: the topology of the graph, the number of agents, and the structure of preferences of the agents. |
| title | Stability in Distance Preservation Games on Graphs |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2602.15784 |