Modelling segregation: Schelling’s model

class: center, middle, inverse, title-slide

.title[
# Modelling segregation: Schelling’s model
]
.author[
### David Garcia, University of Konstanz
]
.date[
### Computational Modelling of Social Systems
]

---

layout: true

<div class="my-footer"><span>David Garcia - Computational Modelling of Social Systems</span></div>

---

# Overview

## 1. Segregation

## 2. Schelling's segregation model

## 3. Analyzing Schelling's model

## 4. Cellular Automata: The game of life

---

# Segregation

## *1. Segregation*

## 2. Schelling's segregation model

## 3. Analyzing Schelling's model

## 4. Cellular Automata: The game of life

---

# Urban segregation: definition

Urban segregation is the unequal distribution of different social groups in the urban space, based mainly on occupation, income and education, as well as on gender and ethnicity. -- [The Future of Cities. European Research Comission](https://urban.jrc.ec.europa.eu/thefutureofcities/social-segregation#the-chapter)

---

## Segregation example: District of Columbia, US

[America is more diverse than ever — but still segregated. The Washington Post](https://www.washingtonpost.com/graphics/2018/national/segregation-us-cities/)

---

## Questions about the origin of segregation

- Top-down segregation: Discriminatory policies

- Bottom-up segregation: Individual location choices influenced by:
  - Price of housing and services
  - Access to religious centers and education in a language
  - Tenant exclusion and bias
  
- What is the role of inhabitant intolerance to different neighbors?

- Without central discrimination, can segregation emerge even when individuals tolerate living in a neighborhood in which they are in the minority?

---

# Schelling's segregation model

## 1. Segregation

## *2. Schelling's segregation model*

## 3. Analyzing Schelling's model

## 4. Cellular Automata: The game of life

---

# Schelling's model setup

.pull-left[
<img src="Figures/Schelling1.svg" width="500" style="display: block; margin: auto;" />
]

.pull-right[

- Agents of two kinds, similar number (here 22 and 23)
- Low but nonzero fraction of empty cells (here 19)
- Cells have a neighborhood of 8 cells (3x3 - 1)
- Border and corner cells have smaller neighborhood
- Agents are aware of the fraction of similar agents in their neighborhood: `$f$`
- Agents are satisfied with `$f \geq F$`
- `$F$` measures intolerance

]
---

# Relocation example

.pull-left[
<img src="Figures/Schelling2.svg" width="500" style="display: block; margin: auto;" />
]
.pull-right[
-  `$F=0.35$`

- 3/3 neighbors are equal: 
  - agent stays

- Remember:
  - Only occupied neighbor cells count
  - Cells close to the border have smaller neighborhoods
]
---

# Relocation example

.pull-left[
<img src="Figures/Schelling3.svg" width="500" style="display: block; margin: auto;" />
]
.pull-right[
-  `$F=0.35$`

- 1/3 neighbors are equal:
  - 1/3 < 0.35
  - agent marked for relocation
]

---

# Relocation example

.pull-left[
<img src="Figures/Schelling4.svg" width="500" style="display: block; margin: auto;" />
]
.pull-right[
-  `$F=0.35$`

- 2/4 neighbors are equal:
  - 0.5 > 0.35
  - agent stays
]

---

# Relocation example

.pull-left[
<img src="Figures/Schelling5.svg" width="500" style="display: block; margin: auto;" />
]
.pull-right[
-  `$F=0.35$`

- 1/3 neighbors are equal:
  - 1/3 < 0.35
  - agent marked for relocation
]

---

# Relocation example

.pull-left[
<img src="Figures/Schelling6.svg" width="500" style="display: block; margin: auto;" />
]
.pull-right[
-  `$F=0.35$`

- 1/2 neighbors are equal:
  - 0.5 > 0.35
  - agent stays

- Note:
  - Corner cells have at most three neighbors
]

---

# Relocation example

.pull-left[
<img src="Figures/Schelling7.svg" width="500" style="display: block; margin: auto;" />
]
.pull-right[
- "Unhappy" agents with `$f<F$`

- Relocation based on a sequence and a rule where to jump

- Some variablity in this step:
  - Random sequence or ordered
  - Allowing random jumps with a low probability (e.g. 1%)

- Options about jumps:  
a) closest happy free spot  
b) happiest free spot: `$max(f)$`, even if new `$f$` still below `$F$`
]
---

# Simulation result

.pull-left[
<img src="Figures/SchellingEnd.png" width="500" style="display: block; margin: auto;" />
]
.pull-right[

- State after running a few iterations

- All agents are satisfied ( `$f \geq F$` )

- No more relocations take place (simulation ends)

- Result looks segregated 
  - Two large black regions
  - Rest formed by scattered white agents
]

---

# Simulation configuration

.pull-left[
<img src="Figures/RND.png" width="450" style="display: block; margin: auto;" />
]

.pull-right[
<img src="Figures/setup.png" width="450" style="display: block; margin: auto;" />

http://nifty.stanford.edu/2014/mccown-schelling-model-segregation/

- Random initial configuration
- Parameters can be changed
- Reporting % satisfied agents and simulation round

]

---

# Analyzing Schelling's model

## 1. Segregation

## 2. Schelling's segregation model

## *3. Analyzing Schelling's model*

## 4. Cellular Automata: The game of life

---

# Measuring segregation: Moran's I

`$$\Large I = \frac{M \sum_i \sum_j w_{i,j} (x_i - \bar x) (x_j - \bar x)}{(\sum_i \sum_j w_{i,j}) \sum_i (x_i-\bar x)^2}$$`

- `$M$`: Number of occupied cells
- `$w_{i,j}$`: adjacency matrix of cells
  - `$w_{i,j}=1$` if `$i$` is a neighbor of `$j$`, otherwise `$w_{i,j}=0$` 
- `$x_i$`: color value of occupied cell `$i$`
  - `$x_i=1$` if blue agent in it, `$x_i=0$` if red agent in it
  - We only count over occupied cells, ignore empty ones
- `$\bar x$`: mean value of `$x$`, i.e. fraction of blue agents
- Also known as spatial autocorrelation
---

# Segregation versus tolerance

.pull-left[
<img src="Figures/IvsF.png" width="750" style="display: block; margin: auto;" />
]
.pull-right[

- 3x3 neighborhood (up to 8 neighbors), torus edges

- Boxplots of I after convergence in several simulations

- Moran's I stays low for low F values

- Sharp increase above two neighbors for F

- Substantial segregation for F>0.33

]

---

# Cellular Automata: The game of life

## 1. Segregation

## 2. Schelling's segregation model

## 3. Analyzing Schelling's model

## *4. Cellular Automata: The game of life*

---

# Cellular Automata

- agents `$\equiv$` cells, arranged on a predefined lattice
- formal structure of Cellular Automata
  - finite or infinite grid of identical cells `$i=1,...,L$`
  - cell with internal state `$\theta_{i} (t) \in \{\theta_1,\dots, \theta_n \}$`
  - neighborhood configuration: `$\beta_{i}(t)\in\{\beta_1,\ldots,\beta_m\}$` 
  - discrete dynamics for the state variable at `$t+1$` :
    `$$\theta_{i}(t+1)=\mathbf{F}\left[\underline{\theta}(t),\underline{\beta}(t)\right]$$`
- characteristics: 
  - discrete space, time, and states
  - same transition rule applies to all cells
  - *each* cell is an agent (!)

---

# Cellspace and Neighbourhoods
- Many types of neighbourhoods possible.
- Examples in 2D:
<img src="Figures/neigh.png" width="800" style="display: block; margin: auto;" />
- Finite cellspace L `$\rightarrow$` border cells need different update rule
  - option 1: mirror border cells 
  - option 2: periodic boundary condition: A Torus
- Not only squares, but also triangular, hexagonal and even irregular tilings possible (e.g. Voronoi tesselations)

---

# Conway's Game of Life

- History
  - **John Conway** (1970): design a self-replicating system 
  - 2010: first self-replicating structure in *Life*, called *Gemini*
  - 2013: first replicator that creates a bigger copy of itself (self-similarity)
- Rules of the Game
  - 2D rectangular infinite grid with "dead" and "alive" cells
  - a dead cell becomes alive if 3 neighbours are alive - **reproduction**
  - an alive cell dies if less than 2 neighbours are alive - **underpopulation**
  - an alive cell dies if more than 3 neighbours  are alive - **overcrowding**
- Importance of Conway's Game of Life
  - complex behaviour emerges from simple rules for agents
  - early modeling of self-organization

To play the game: https://playgameoflife.com

---

#Simulating the Game of Life

Dead cells are white, alive cells are black:

---
background-image: url(Figures/GolEx.svg)
background-size: 98%
#Evolution of structures

- still lifes: static patterns (e.g. 'beehive')

- oscillators: repeating patterns

- spaceships: translating patterns (e.g. 'glider')

- guns: stationary patterns which emit spaceships

- puffers: translating patterns which leave a trail of debris behind

- the Gemini replicator: http://youtu.be/A8B5MbHPlH0
 
A whole library of structures is available at https://playgameoflife.com/lexicon

You can even setup Game of Life in the Game of life: http://youtu.be/xP5-iIeKXE8

---

# Summary

- Residential segregation: could it emerge without resource limits or central discrimination/laws?

- Schelling's model of segregation: agents in a lattice that relocate when their neighborhood similarity is below a threshold [(Schelling, 1971)](https://www.uzh.ch/cmsssl/suz/dam/jcr:00000000-68cb-72db-ffff-ffffff8071db/04.02%7B_%7Dschelling%7B_%7D71.pdf)

- Analyzing Schelling's model: Moran's I and iteration over F values
  - Segregation emerges below 0.5, as low as 0.33
[(Hatna &  Benenson, 2012)](https://www.jasss.org/15/1/6.html)

- Other models on lattices: Cellular automata. Conway's Game of Life as one of the first examples of emergence of complex behavior from simple rules
[(Gardner, 1970)](https://web.stanford.edu/class/sts145/Library/life.pdf)

---

# Quiz

- Is there residential segregation in Vienna? If so, on what attributes?

- What other contexts can have segregation besides the residential case?

- What are the simplifications of Schelling's model?

- How can we take into account weaker correlations at distance larger than 1 in Moran's I?

- How is Schelling's model different to the formulation of cellular automata?