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

CREATORArgyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith, Dušan Knop, Šimon Schierreich
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE105 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-15784

Browse the full library · About the Tower of Babel