License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.15
URN: urn:nbn:de:0030-drops-126841
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12684/
Go to the corresponding LIPIcs Volume Portal


Bilò, Davide ; Bilò, Vittorio ; Lenzner, Pascal ; Molitor, Louise

Topological Influence and Locality in Swap Schelling Games

pdf-format:
LIPIcs-MFCS-2020-15.pdf (0.7 MB)


Abstract

Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling’s famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i.e., if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling’s model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i.e., if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are commonly used in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.

BibTeX - Entry

@InProceedings{bil_et_al:LIPIcs:2020:12684,
  author =	{Davide Bil{\`o} and Vittorio Bil{\`o} and Pascal Lenzner and Louise Molitor},
  title =	{{Topological Influence and Locality in Swap Schelling Games}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ľ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12684},
  URN =		{urn:nbn:de:0030-drops-126841},
  doi =		{10.4230/LIPIcs.MFCS.2020.15},
  annote =	{Keywords: Residential Segregation, Schelling’s Segregation Model, Non-cooperative Games, Price of Anarchy, Game Dynamics}
}

Keywords: Residential Segregation, Schelling’s Segregation Model, Non-cooperative Games, Price of Anarchy, Game Dynamics
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI