Swap Stability in Schelling Games on Graphs

We study a recently introduced class of strategic games thatis motivated by and generalizes Schelling’s well-known resi-dential segregation model. These games are played on undi-rected graphs, with the set of agents partitioned into multi-ple types; each agent either occupies a node of the graph andnever moves away or aims to maximize the fraction of herneighbors who are of her own type. We consider a variant ofthis model that we call swap Schelling games, where the num-ber of agents is equal to the number of nodes of the graph, andagents mayswappositions with other agents to increase theirutility. We study the existence, computational complexity andquality of equilibrium assignments in these games, both froma social welfare perspective and from a diversity perspective.