Stability in Distance Preservation Games on Graphs
2026-02-17 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors introduce a new type of game where agents are assigned to spots on a network, and each agent wants to be a certain distance away from others. They study how to arrange agents so that no one wants to move (a stable arrangement) based on different ideas of stability. Their work looks at how hard it is to find stable arrangements depending on the network shape, number of agents, and their distance preferences. This helps understand when stable setups are possible and when they are not.
network allocation gamegraph topologyagent preferencesdistance preservationstability notionsenvy-freenessswap stabilityjump stabilityparameterized complexity
Authors
Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith, Dušan Knop, Šimon Schierreich
Abstract
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.