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.
Our research focus is on theoretical computer science and algorithm engineering. We are equally interested in the mathematical foundations of algorithms and developing efficient algorithms in practice. A special focus is on random structures and methods.
