Exploring Game-theoretic Schelling Segregation

Master Project - Winter 2018/19

People: Prof. Dr. Tobias Friedrich, Dr. Pascal Lenzner, Louise Molitor
Link: Master Projects IT System Engineering

Residential segregation along racial lines in urban areas in the US. The data is taken from the 2010 US Census as illustrated in the racial dot map.

Motivation

In order to explain the emergence of segregation, Economics Nobel Prize winner Thomas Schelling proposed a very simple and elegant agent-based model where two types of agents are placed on a grid. Each agent is aware of its neighboring agents and is content with her current position if at least a \(\tau\) fraction of neighboring agents is of her type, for some \(0\leq \tau \leq 1\). If this condition is not met, then the agent becomes discontent with her current position and exchanges positions with a randomly chosen discontent agent of the other type or jumps to a randomly chosen empty spot. Schelling showed with simple experiments that even with \(\tau \leq \frac{1}{2}\), i.e., with tolerant agents, the society of agents will eventually segregate into almost homogeneous communities.

This surprising observation caught the attention of many researchers who studied various models and verified Schelling's predictions experimentally. However, all these models are essentially random processes where discontent agents choose their new location at random. To address this drawback, we have introduced a game-theoretic version, where agents choose their location strategically.

Illustration of Schelling's segregation model. Left: Agents are placed randomly. Right: Resulting segregated state for \(\tau = \frac{1}{3}\). Pictures are taken from the playful demonstration.

Purpose of the project

We want to study (variants of) our game-theoretic model in depth. This includes a theoretical analysis of the induced graph-theoretic process and its outcomes as well as an extensive empirical study to compare our model with existing models.

What we expect from you. We expect basic proficiency with graph-theoretic concepts and general interest in Algorithmic Game Theory. You should bring the curiosity and willingness to delve into an interesting interdisciplinary research topic within Theoretical Computer Science. Our main goal is a rigorous mathematical understanding of game-theoretic Schelling segregation, and we expect you to contribute theoretical results to that ambitious endeavor.

What you can expect from us. We will gently introduce you to the field and accompany you all along this interesting journey. This will be a team effort, and we aim at publishing our results at a renowned international conference.

Publication

The results of this master project have been accepted for publication at the 15th Conference on Web and Internet Economics (WINE) .

Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Pappik, Marcus; Schöne, Friedrich; Sommer, Fabian; Stangl, DavidConvergence and Hardness of Strategic Schelling Segregation. Web and Internet Economics (WINE) 2019: 156-170
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]

The phenomenon of residential segregation was captured by Schelling's famous segregation model where two types of agents are placed on a grid and an agent is content with her location if the fraction of her neighbors which have the same type as her is at least \(\tau\), for some \(0<\tau<1\). Discontent agents simply swap their location with a randomly chosen other discontent agent or jump to a random empty cell. We analyze a generalized game-theoretic model of Schelling segregation which allows more than two agent types and more general underlying graphs modeling the residential area. For this we show that both aspects heavily influence the dynamic properties and the tractability of finding an optimal placement. We map the boundary of when improving response dynamics (IRD), i.e., the natural approach for finding equilibrium states, are guaranteed to converge. For this we prove several sharp threshold results where guaranteed IRD convergence suddenly turns into the strongest possible non-convergence result: a violation of weak acyclicity. In particular, we show such threshold results also for Schelling's original model, which is in contrast to the standard assumption in many empirical papers. Furthermore, we show that in case of convergence, IRD find an equilibrium in \(O(m)\) steps, where \(m\) is the number of edges in the underlying graph and show that this bound is met in empirical simulations starting from random initial agent placements.
@inproceedings{echzell2019convergence, abstract = {The phenomenon of residential segregation was captured by Schelling's famous segregation model where two types of agents are placed on a grid and an agent is content with her location if the fraction of her neighbors which have the same type as her is at least \(\tau\), for some \(0<\tau<1\). Discontent agents simply swap their location with a randomly chosen other discontent agent or jump to a random empty cell. We analyze a generalized game-theoretic model of Schelling segregation which allows more than two agent types and more general underlying graphs modeling the residential area. For this we show that both aspects heavily influence the dynamic properties and the tractability of finding an optimal placement. We map the boundary of when improving response dynamics (IRD), i.e., the natural approach for finding equilibrium states, are guaranteed to converge. For this we prove several sharp threshold results where guaranteed IRD convergence suddenly turns into the strongest possible non-convergence result: a violation of weak acyclicity. In particular, we show such threshold results also for Schelling's original model, which is in contrast to the standard assumption in many empirical papers. Furthermore, we show that in case of convergence, IRD find an equilibrium in \(O(m)\) steps, where \(m\) is the number of edges in the underlying graph and show that this bound is met in empirical simulations starting from random initial agent placements.}, author = {Echzell, Hagen and Friedrich, Tobias and Lenzner, Pascal and Molitor, Louise and Pappik, Marcus and Schöne, Friedrich and Sommer, Fabian and Stangl, David}, booktitle = {Web and Internet Economics (WINE)}, keywords = {louisemolitor marcuspappik pascallenzner tobiasfriedrich wine year2019}, pages = {156-170}, title = {Convergence and Hardness of Strategic Schelling Segregation}, year = 2019 }