Swap Stability in Schelling Games on Graphs


  • Aishwarya Agarwal University of Oxford
  • Edith Elkind University of Oxford
  • Jiarui Gan University of Oxford
  • Alexandros Voudouris University of Oxford




We study a recently introduced class of strategic games that is motivated by and generalizes Schelling's well-known residential segregation model. These games are played on undirected graphs, with the set of agents partitioned into multiple types; each agent either occupies a node of the graph and never moves away or aims to maximize the fraction of her neighbors who are of her own type. We consider a variant of this model that we call swap Schelling games, where the number of agents is equal to the number of nodes of the graph, and agents may swap positions with other agents to increase their utility. We study the existence, computational complexity and quality of equilibrium assignments in these games, both from a social welfare perspective and from a diversity perspective.




How to Cite

Agarwal, A., Elkind, E., Gan, J., & Voudouris, A. (2020). Swap Stability in Schelling Games on Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1758-1765. https://doi.org/10.1609/aaai.v34i02.5541



AAAI Technical Track: Game Theory and Economic Paradigms