New Paper Reveals Stability Dichotomies in Anonymous Network Allocation Games

In a new paper accepted at SAGT '26, researchers Argyrios Deligkas, Eduard Eiben, Šimon Schierreich, and Alexandros A. Voudouris tackle the problem of allocating anonymous, strategic agents to vertices of a graph. Each agent's utility depends only on the number of neighbors at their allocated vertex, not on identity. The team explored two notions of stability: swap stability (agents can exchange locations) and jump stability (agents can move to an empty vertex). They found that existence of stable allocations depends critically on the shape of utility functions and graph topology, often yielding sharp dichotomies—either stable allocations always exist or determining them is intractable.

Beyond stability, the paper proves strong intractability results: computing a welfare-maximizing allocation is NP-hard, and even verifying whether a given allocation is Pareto optimal is computationally hard. These results have direct implications for distributed systems, social networks, and resource allocation in decentralized environments where agents act selfishly. The study formalizes when simple local moves (swaps or jumps) can lead to equilibrium without central coordination, providing a theoretical backbone for designing efficient, stable mechanisms in anonymous multi-agent systems.