Swap Stability in Schelling Games on Graphs

Authors

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

DOI:

https://doi.org/10.1609/aaai.v34i02.5541

Abstract

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.

Downloads

Published

2020-04-03

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

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms