  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 so 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 two measures for the robustness of equilibria in Schelling games
in terms of the minimum number of edges or the minimum number of vertices that
need to be deleted to make an equilibrium unstable. We prove tight lower and
upper bounds on the edge- and vertex-robustness of swap-equilibria in Schelling
games on different graph classes.
