Equilibria in Schelling Games: Computational Complexity and Robustness

In the simplest game-theoretic formulation of Schelling's model of segregation on graphs, agents of two different types each select their own vertex in a given graph such as to maximize the fraction of agents of their type in their occupied neighborhood. Two ways of modeling agent movement here are either to allow two agents to swap their vertices or to allow an agent to jump to a free vertex. The contributions of this paper are twofold. First, we prove that deciding the existence of a swap-equilibrium and a jump-equilibrium in this simplest model of Schelling games is NP-hard, thereby answering questions left open by Agarwal et al. [AAAI '20] and Elkind et al. [IJCAI '19]. Second, we introduce a measure for the robustness of equilibria in Schelling games in terms of the minimum number of edges that need to be deleted to make an equilibrium unstable. We prove tight lower and upper bounds on the robustness of swap-equilibria in Schelling games on different graph classes.