Stability in Distance Preservation Games on Graphs An extended abstract of this work has been published in the Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’26 ( Deligkas et al. 2026 ) .
Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith, Dušan Knop, Šimon Schierreich · 2026
Read Stability in Distance Preservation Games on Graphs An extended abstract of this work has been published in the Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’26 ( Deligkas et al. 2026 ) . by Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith, Dušan Knop, Šimon Schierreich (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-15784.txt.
Description
Deligkas and colleagues introduce graphical distance preservation games, a new class of network allocation games. A graph, called a topology, hosts agents that must be placed at vertices, and each agent has an ideal distance, possibly different, at which to sit from some other agents. Given an allocation, each agent suffers a cost equal to the sum of differences from ideal distances for agents in their subset. The question is whether a stable allocation exists, where no agent wants to move.
Three stability notions are studied: envy-freeness, swap stability, and jump stability. The paper performs a full study of complexity by parameter along three dimensions: graph topology, agent count, and tastes. Game theorists gain a new placement game that ties stable placements to geometry, with complexity mapped across shape, numbers, and tastes.
Catalog record
| CREATOR | Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith, Dušan Knop, Šimon Schierreich |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 105 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-15784