Abstract
We study strategic games inspired by Schelling's seminal model of residential segregation. These games are played on undirected graphs, with the set of agents partitioned into multiple types; each agent either aims to maximize the fraction of her neighbors who are of her own type, or occupies a node of the graph and never moves away. We consider two natural variants of this model: in jump games agents can jump to empty nodes of the graph to increase their utility, while in swap games they can swap positions with other agents. We investigate the existence, computational complexity, and quality of equilibrium assignments in these games, both from a social welfare perspective and from a diversity perspective. Some of our results extend to a more general setting where the preferences of the agents over their neighbors are defined by a social network rather than a partition into types.
| Original language | English (US) |
|---|---|
| Article number | 103576 |
| Journal | Artificial Intelligence |
| Volume | 301 |
| DOIs | |
| State | Published - Dec 2021 |
Funding
This work has been supported by the European Research Council (ERC) under grant number 639945 (ACCORD), by the EPSRC International Doctoral Scholars Grant EP/N509711/1 , by the KAKENHI Grant-in-Aid for JSPS Fellows number 18J00997 , by JST ACT-X, JST PRESTO, and by an NUS Start-up Grant. We are grateful to the reviewers of IJCAI 2019, AAAI 2020 and AIJ for their valuable comments.
Keywords
- Computational complexity
- Equilibrium analysis
- Price of anarchy
- Schelling games
ASJC Scopus subject areas
- Language and Linguistics
- Linguistics and Language
- Artificial Intelligence
