The Sakoda-Schelling checkerboard model for racial segregation

Note: This example is work in progress.

In 1971, Thomas Schelling published a paper entitled "Dynamic models of segregation" He explored one specific mechanism of racial segregation, by simulating what is often considered to be the first agent-based model. He performed his simulations manually, using coins he moved around on a piece of paper, and made no effort to define unambiguous rules for them. What follows is one possible formalization of his model.

Historical note: A very similar model was published one month earlier by James Sakoda ("The checkerboard model of social interaction"), who had already worked on (but not published) similar agent-based models for more than 20 years. Sakoda's model was computationally more sophisticated (implemented in Fortran, with several parameters to adapt to different situations), and also more general. Historian Rainer Hegselmann (see "Thomas C. Schelling and James M. Sakoda: The Intellectual, Technical, and Social History of a Model") comes to the conclusion that it was in fact too sophisticated for its time, when few social scientists had programming competence or access to computers, and therefore it was quickly forgotten. Schelling's simpler coin-on-paper model caught on and became famous.

Uses:
- Rational numbers
- One-dimensional arrays, Array size
- Function application to one-dimensional arrays
- Reduction over one-dimensional arrays
- Function-based selection from one-dimensional arrays
- Two-dimensional array indexation
- Term equality
- Boolean algebra

Outline of the model

An agent represents an individual or a family that lives in a specific place in some territory. There are two kinds of agents, black and white. Agents like their neighborhood depending on which fraction of its population is of the same kind. If an agent is not happy in its place, it tries to move to another one. Simulations of this model show that even a slight preference for living among one's own kind leads to segregation, with large neigborhoods populated uniformly by agents of the same kind.

The territory

The territory is defined by a set of places and a way to compute the distance between two places:
 distance(p1:place, p2:place) : ℚ.nn

Schelling's paper territory corresponds to a rectangular grid of cells defined by two integer coordinates:
cell(x:ℤ, y:ℤ) : place

The grid is finite, consisting of N : ℕ.nz rows and M : ℕ.nz columns. The following function tests if a place is in the territory:
 isInTerritory : place → 𝔹
 x:ℤ, y:ℤ, isInTerritory[cell(x, y)] ⇒ (x ≥ 1) ∧ (x ≤ N) ∧ (y ≥ 1) ∧ (y ≤ M)

Schelling moved his coins only along the rows and columns, like a rook in chess. The distance between two cells, defined as the minimum number of moves to get from one to the other, is thus:
 x1:ℤ, x2:ℤ, y1:ℤ, y2:ℤ, distance(cell(x1, y1), cell(x2, y2)) ⇒ abs(x1 - x2) + abs(y1 - y2)
with the absolute value abs(ℤ) : ℕ defined by
 n:ℕ, abs(n) ⇒ n
 z:ℤ, abs(z) ⇒ -(z) | z < 0

Example

Schelling's first example shown in the paper, in Fig. 7, has example N ⇒ 13 rows and example M ⇒ 16 columns.

Neighborhoods

The neighborhood of a cell in the bulk of the grid consists of its eight surrounding cells:
 bulkNeighborhood(place) : Array(place, 8)
 bulkNeighborhood(cell(x:ℤ, y:ℤ)) ⇒ {[cell(x - 1, y - 1), cell(x, y - 1), cell(x + 1, y - 1), cell(x - 1, y), cell(x + 1, y), cell(x - 1, y + 1), cell(x, y + 1), cell(x + 1, y + 1)]}

Cells on the edges of the territory have fewer neigbors:
 neighborhood(place) : Array1D(place)
 p:place, neighborhood(p) ⇒ select(isInTerritory, bulkNeighborhood(p))

Example

For the example of Schelling's Fig. 7, the neighborhood of the top-left corner is
 example neighborhood(cell(1, 1)) ⇒ {[cell(2, 1), cell(1, 2), cell(2, 2)]}
and the neighborhood of the bottom-right corner is
 example neighborhood(cell(N, M)) ⇒ {[cell(12, 15), cell(13, 15), cell(12, 16)]}.
A neighborhood of a cell on an edge contains five cells:
 example length(neighborhood(cell(1, 5))) ⇒ 5
and a cell in the middle of the territory has eight neighbors:
 example length(neighborhood(cell(5, 6))) ⇒ 8.

Agents

There are two kinds of agent: black : agent and white : agent.

Occupation

The occupation of each place is either an agent ⊆ occupation or the special value empty : occupation.

Simulation

A simulation starts from an initial state, which is then updated in a series of iterations:
 iteration : state → state

The simulation is thus a series of successive states,
 simulation[ℕ] : state
 (s:simulation)[n:ℕ.nz] ⇒ iteration[s[n - 1]],
with (s:simulation)[0] being the initial state.

For the segregation model, the state describes the current occupation of each place in the territory. For a rectangular grid of cells, this state can be represented by a two-dimensional array:
 Array2D(occupation) ⊆ state
 occupation(place, state) : occupation
 occupation(cell(x:ℕ.nz, y:ℕ.nz), s:Array2D(occupation)) ⇒ s[x, y]

An iteration is a pass over the territory, row by row and, within each row, column by column:
 iteration[s:state] ⇒ rowPass(N, s)

 rowPass(ℕ, state) : state
 rowPass(0, s:state) ⇒ s
 rowPass(n:ℕ.nz, s:state) ⇒ columnPass(n, M, rowPass(n - 1, s))

 columnPass(ℕ, ℕ, state) : state
 columnPass(n:ℕ.nz, 0, s:state) ⇒ s
 columnPass(n:ℕ.nz, m:ℕ.nz, s:state) ⇒ move(cell(n, m), columnPass(n, m - 1, s))

Note: Schelling's article is less precise about the order in which the cells are processed: "Working generally from the upper left corner downward and to the right, ..." (page 156)

Moves

In each move, a single place is examined:
 move(place, state) : state

What happens during a move depends most importantly on its occupation:
 move(occupation, place, state) : state
 move(p:place, s:state) ⇒ move(occupation(p, s), p, s)

If the place is empty, nothing changes:
 move[1]: move(empty, p:place, s:state) ⇒ s

If the place is occupied by agent that is happy there, nothing changes either:
 move[2]: move(a:agent, p:place, s:state) ⇒ s | isHappy(a, p, s)

Otherwise, the place is occupied by an unhappy agent, who tries to move to the nearest empty place that offers happiness. Such a move is equivalent to an exchange of the occupations of the two places:
move[3]: move(a:agent, p:place, s:state) ⇒ exchange(p, nearestEmptyHappyPlace(a, p, s), s)
with
 exchange(place, place, state) : state
and
 nearestEmptyHappyPlace(agent, place, state) : place.

Happiness

Happiness is binary. Agents are happy in a place, or they are not:
isHappy(agent, place, state) : 𝔹

Happiness depends on the fraction of the population in the neighborhood of a place that is of the same color as the agent

An agent is happy if at least half of the other agents in its neighborhood are of the same color:
 a:agent, p:place, s:state, isHappy(a, p, s) ⇒ fractionOfColor(a, p, s) ≥ 1/2

The number of places in a neighborhood occupied by an agent of some color is
 neighborsOfColor(agent, place, state) : ℕ
 neighborsOfColor(a:agent, p:place, s:state) ⇒ length(select(sameAs(a, s), neighborhood(p)))
with
 sameAs(occupation, state) : place → 𝔹
 sameAs(o:occupation, s:state)[cell(x:ℕ.nz, y:ℕ.nz)] ⇒ s[x, y] == o

The fraction is then computed as
 fractionOfColor(agent, place, state) : ℚ.nn
 fractionOfColor(black, p:place, s:state) ⇒ neighborsOfColor(black, p, s) ÷ (neighborsOfColor(black, p, s) + neighborsOfColor(white, p, s))
 fractionOfColor(white, p:place, s:state) ⇒ 1 - fractionOfColor(black, p:place, s:state)

Finding a place to move to

Schelling writes: "The rule of movement, then, is that an individual discontent with his own neighborhood moves to the nearest vacant spot that surrounds him with a neighborhood that meets his demands." (page 154/155)

This leaves two cases that need to be addressed:
1. There is no suitable destination at all.
2. There are several equally near places that satisfy the agent's criteria.

Initialization

The initial state of the simulation is defined by a random selection of occupations. The fraction of empty places is provided as an input. The fractions of the two kinds of agents are taken to be equal.
 randomOccupation(emptyFraction:ℚ.nn) : state