Elkind, Edith and Gan, Jiaru and Igarashi, Ayumi and Suksompong, Warut and Voudouris, Alexandros A (2019) Schelling games on graphs. In: Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19), 2019-08-10 - 2019-08-16, Macao.
Elkind, Edith and Gan, Jiaru and Igarashi, Ayumi and Suksompong, Warut and Voudouris, Alexandros A (2019) Schelling games on graphs. In: Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19), 2019-08-10 - 2019-08-16, Macao.
Elkind, Edith and Gan, Jiaru and Igarashi, Ayumi and Suksompong, Warut and Voudouris, Alexandros A (2019) Schelling games on graphs. In: Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19), 2019-08-10 - 2019-08-16, Macao.
Abstract
We consider strategic games that are inspired by Schelling's model of residential segregation. In our model, the agents are partitioned into k types and need to select locations on an undirected graph. Agents can be either stubborn, in which case they will always choose their preferred location, or strategic, in which case they aim to maximize the fraction of agents of their own type in their neighborhood. We investigate the existence of equilibria in these games, study the complexity of finding an equilibrium outcome or an outcome with high social welfare, and also provide upper and lower bounds on the price of anarchy and stability. Some of our results extend to the setting where the preferences of the agents over their neighbors are defined by a social network rather than a partition into types.
Item Type: | Conference or Workshop Item (Paper) |
---|---|
Additional Information: | Published proceedings: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence |
Uncontrolled Keywords: | Schelling games; Equilibrium analysis; Price of anarchy; Computational complexity |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 20 May 2020 13:01 |
Last Modified: | 30 Oct 2024 16:30 |
URI: | http://repository.essex.ac.uk/id/eprint/27264 |
Available files
Filename: 1902.07937v1.pdf