Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Exploring Game-theoretic Schelling Segregation (Master Project Winter 2018/19)

Chicago
New York
Los Angeles

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 segre­gated 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.

Project Team

The Master Project is organized by the Algorithm Engineering Group.

Project Supervisor

Hasso Plattner Institute

Office: A-1.10
Tel.: +49 331 5509-410
E-Mail: friedrich(at)hpi.de

Project Supervisor

Hasso Plattner Institute

Office: A-1.5
Tel.: +49 331 5509-419
E-Mail: Pascal.Lenzner(at)hpi.de

Advisor

Hasso Plattner Institute

Office: A-1.7/8
Tel.: +49 331 5509-415
E-Mail: Louise.Molitor@hpi.de

Hagen Echzell

Participant

Hasso Plattner Institute

E-Mail: Hagen.Echzell(at)student.hpi.de

Marcus Pappik

Participant

Hasso Plattner Institute

E-Mail: Marcus.Pappik(at)student.hpi.de

Friedrich Schöne

Participant

Hasso Plattner Institute

E-Mail: Friedrich.Schoene(at)student.hpi.de

Fabian Sommer

Participant

Hasso Plattner Institute

E-Mail: Fabian.Sommer(at)student.hpi.de

David Stangl

Participant

Hasso Plattner Institute

E-Mail: David.Stangl(at)student.hpi.de