Wanting a third, and getting three quarters
Worth reading first: Two equilibria and no way to choose · The landscape nobody is looking at.
In 1969 and 1971 the economist Thomas Schelling played a game with coins on a chessboard. Pennies and dimes were scattered over the squares, with some squares left empty. Each coin looked at its eight neighbours, and if too few of them were its own kind it moved to an empty square where it would be satisfied. Schelling repeated the moves by hand until no coin wanted to move. Even when every coin was content to be in a local minority — demanding only that a third of its neighbours match it — the board ended up sorted into large single-kind regions.
The model is the most famous example of what is now called emergence: a pattern in the whole that is not present in the preferences of any part. In the language of two equilibria and no way to choose it is also a statement about equilibria. The state in which nobody wants to move is an equilibrium of a location game, and this essay runs Schelling’s procedure until it reaches one, measures how much more segregated the result is than anyone asked for, and then exhibits a second equilibrium — a perfectly integrated city in which every resident is equally content — that the moving residents never find. The segregation is not forced by the preferences. It is selected by the process.
The rules of the game
The grid has forty squares a side, and its edges wrap round, so that every square has exactly eight neighbours and there are no edges to treat differently. A tenth of the 1,600 squares are empty; of the rest, half are red and half blue, placed at random. A resident is content if at least a fraction of its occupied neighbours are its own colour, and here . A discontented resident moves to a randomly chosen empty square at which it would be content. The moves are made in rounds: in each round every discontented resident, taken in random order, gets one move.
In the random starting city, on the left, the average resident has half its neighbours of its own colour, as chance would give. About one resident in six is discontented. On the right is the city after four rounds and 352 moves, when every resident is content and nobody wants to move. The average resident now has 77% of its neighbours of its own colour, and the picture shows why: the city has sorted itself into broad red and blue territories with ragged borders, the empty squares collecting along the borders between them.
Nobody in this city wanted a red or blue neighbourhood. Every resident would have been content as one of three in a mixed group. The territories are a consequence of the moves, not of anyone’s demand.
The first round does most of the work
The sorting is fast. The figure follows the same run round by round. At the start 265 residents are discontented. After the first round only 50 are, and the share of like neighbours has jumped from 50% to 71% — most of the eventual change, in one pass. The second round leaves 9 discontented, the third 3, the fourth none.
The speed comes from a feedback that the rule builds in. A red resident that leaves a mostly blue patch makes that patch bluer, and so makes its remaining red residents more likely to be discontented too; it arrives at a patch where it is content, which by definition already has a share of red, and makes that patch redder, so that a blue resident there is now closer to its own limit. Each move is a small step towards sorting, and it creates the conditions for the next. Schelling called the phenomenon tipping: a neighbourhood that loses a few residents of one kind can lose the rest in a cascade, because each departure pushes the next resident over its threshold.
Nothing in the dynamics aims at segregation. Each move is the decision of one resident to go somewhere tolerable. Segregation is the fixed point of the many decisions together, the state at which no one’s tolerance is exceeded and so no one has a reason to change anything.
How the result depends on the demand
The figure repeats the experiment for thresholds from 5% to 70%, six runs at each, and records the settled share of like neighbours. The dotted diagonal is what the residents ask for: a resident at threshold wants a share of like neighbours and no more. For very mild demands, below a quarter, the settled city is barely more segregated than a random one — about 51% to 57% like neighbours — because almost everyone is content from the start and few moves are made.
Between a threshold of 0.25 and 0.3 the settled share jumps, from 57% to 73%, and above that it climbs steadily: 81% at 0.4, 86% at a half, 91% at 0.55. The jump is a whole-number effect worth noticing. A resident with eight occupied neighbours needs two like ones at a threshold of a quarter but three at 0.3, and the step from two to three is what turns a city in which most residents are content into one in which a sixth are not. A model in which preferences change smoothly can still respond in steps, because what a resident counts is people.
Above 0.6 the dynamics often fail to settle at all: at 0.65 and 0.7 none of the runs reached a state where everyone was content within 120 rounds. The demand is then so high that the empty squares are rarely good enough for anybody, and residents keep moving. The interesting regime is the mild one, between about a quarter and a half, where every resident would accept being outnumbered and the city still ends heavily sorted. At a third, the settled share of like neighbours is more than twice what anyone asked for.
Every start ends sorted
One run proves little about a random process, so the figure runs forty, from forty different random cities, all with a one-third threshold. Every one settles. The starting cities are all close to half like neighbours, between 48% and 52%, as they must be. The settled cities are all between 70% and 80%. There is no run in which the moving residents find a mixed arrangement and stop there.
That uniformity is the model’s real claim. A single sorted city could be a fluke of the starting arrangement; forty from forty is a property of the rule. It is the property that made the model famous and that has been reproduced in many variations since — with more than two kinds of resident, with different neighbourhood sizes, with residents who move to the best available square rather than the first acceptable one. The qualitative result survives all of them: mild individual preferences, enacted one move at a time, produce strong collective sorting.
An integrated city where nobody moves
It is tempting to conclude that segregation is the only possible outcome for residents with these preferences. It is not. The left half of the figure is a city laid out like a chessboard, red and blue alternating, with a tenth of the squares left empty along diagonal lines. Each resident’s four diagonal neighbours are its own colour and its four orthogonal neighbours are the other, so the average resident has exactly half its neighbours of its own kind — the same as a random city. And every resident has at least a third: the computation checks all of them and finds none discontented. Nobody in the chequered city wants to move. It is an equilibrium, and a fully integrated one.
So the location game has (at least) two kinds of equilibrium, integrated and segregated, and every resident is content in both. The residents’ preferences do not distinguish them. What distinguishes them is the process: the integrated equilibrium is a needle in a haystack that no sequence of discontented residents moving to tolerable squares will reach from a random start, while the segregated equilibria are where almost every such sequence ends. This is equilibrium selection of exactly the kind two equilibria and no way to choose found in a two-player game, where the payoffs leave the choice open and something outside them — history, a focal point, a dynamic — settles it.
Local rules, global pattern
Schelling’s model belongs to a family of systems that keeps recurring in mathematics: systems in which every part follows a rule that looks only at its immediate surroundings, and the whole develops structure that no rule mentions. A jam that comes from nowhere found traffic jams forming on an empty ring road out of drivers who each only kept a safe distance from the car ahead; nobody braked for a jam, and the jam moved backwards through the traffic as a pattern made of different cars at every moment. The segregated territories are the same kind of object. They are not made of particular residents — the residents on a border keep changing as the city settles — but of the rule’s tendency to reinforce whatever local imbalance chance first produced.
The contrast with no local rule can count the votes is instructive in the other direction. There, cells on a ring tried to agree, by looking only at their neighbours, on which value was in the global majority, and no local rule could do it reliably: local information cannot see a global count. Schelling’s residents are not trying to compute anything global, and the global outcome they produce is not one any of them wanted. In both cases the lesson is that the relation between a local rule and a global result is not something one can read off the rule — in one case because the rule cannot reach the result it wants, in the other because it reaches a result nobody wanted.
The model also has a geometric cousin in this collection’s game theory. Sellers in a square town placed competing shops in a square and asked where they settle when each moves to the best spot given the others; there too the settled arrangement is an equilibrium of a location game, and there too the equilibrium reached depends on the order of moves and the starting positions. The difference is that a shopkeeper’s payoff is a smooth function of position and a resident’s is a step — content or not — and the step is what makes Schelling’s dynamics cascade. A resident just below its threshold and one far below it behave identically, which is why one departure can tip a whole neighbourhood.
A population, not a strategy
The equilibrium here is also of a less familiar kind than in most two-player games. No resident chooses a strategy in the usual sense; each simply occupies a square, and the equilibrium is a statement about the population’s arrangement — that no individual, acting alone, has a reason to change it. A mixture that is a population read a mixed strategy as the proportions of a population playing pure ones, and Schelling’s city is that reading pushed further: the equilibrium is not a probability over strategies but a spatial pattern, and the equilibrium concept is the plainest one available — nobody wants to move — with nothing about how anyone came to be where they are. A best reply to the past studied the dynamics that are supposed to lead to an equilibrium by repeated best responses; Schelling’s residents are best-responding in the weakest possible sense, moving to the first acceptable square rather than the best one, and the dynamics converge quickly all the same — to the equilibrium they select, not to the one an observer might prefer.
Why there is no landscape to descend
The landscape nobody is looking at explained why some games, like congestion on roads, cannot cycle when players move one at a time: there is a single number, the potential, that every improving move lowers, so the moves must stop. It is natural to look for such a number here, and Schelling’s threshold rule does not have one. When a discontented resident leaves a square, its former neighbours each lose a neighbour of some colour, and a neighbour of its own colour who was exactly at the threshold becomes discontented. A move that satisfies one resident can dissatisfy others, and no quantity of the whole city is guaranteed to improve.
Variants of the model do have a potential. If residents count the number of like neighbours rather than comparing a share with a threshold, and two residents of different colours swap squares only when both gain, then the total number of like adjacencies in the city rises with every swap, and the swaps must stop. In those versions convergence is a theorem. In Schelling’s original version it is an observation: for thresholds up to about a half the runs here all settle in a handful of rounds, and above 0.6 they often do not settle at all. The absence of a potential is part of why the model resisted mathematical analysis for decades after it was proposed, and why its first rigorous results, on the size of the segregated regions in large cities, came only in the 2010s.
What the simulation cannot show
Every figure here is a seeded simulation: the same seed gives the same city, and every claim the figures make — that the run settled, that every resident in the chequered city is content, that every one of forty runs ended above 70% — is checked on the cities actually computed. But a simulation of forty runs on a thirty-by-thirty grid is not a theorem about all runs on all grids. That the settled share at a third is between 70% and 80% is a measurement with those grid sizes, those empty-square densities and that move rule, and each could change it.
And the model is a model of preferences and moves, not of a real city. Real residential sorting involves prices, incomes, discrimination by landlords and lenders, the location of schools and work, and history. Schelling’s point was not that these do not matter, but that even without any of them — even with tolerant residents and free movement — sorting would emerge, so that observing segregation does not by itself show that anyone wants it. The model is an argument about what cannot be inferred, and it is strongest read that way.
Still open: the size of the regions
For large cities the mathematics has caught up only partly. In one-dimensional versions — residents on a ring — Christina Brandt, Nicole Immorlica, Gautam Kamath and Robert Kleinberg showed in 2012 that at a threshold of one half the sorted runs are only polynomially longer than a resident’s neighbourhood, and George Barmpalias, Richard Elwes and Andrew Lewis-Pye found runs exponentially longer for some other thresholds. In two dimensions, Immorlica, Kleinberg and their coauthors proved in 2017 that for some tolerant thresholds the sorted regions are exponentially larger than a neighbourhood. Exactly where the transitions between little sorting, large regions and complete sorting lie, and how they depend on the share of empty squares, is not settled for the two-dimensional model with Schelling’s own rule — the model whose figures above are a few thousand moves on a laptop.
Content, and sorted
Residents who each want only a third of their neighbours to share their colour, moving one at a time to squares they can tolerate, sort a random city into territories in which the average resident has three quarters like neighbours. The sorting takes a few rounds, every random start ends in it, and the settled share jumps where the demand crosses from two like neighbours in eight to three. Yet a chequered city, half like neighbours, satisfies every resident just as well: it is an equilibrium too, and the dynamics never reach it. The preferences allow integration; the process selects segregation, and no single number of the city tracks the moves, so nothing guarantees that the moving stops at all — though at mild demands it always did.
Shares its objects with
Essays that name at least two of the same things, and that neither author linked.
- A crowd of clocks that falls into step — both name simulation, threshold
- A long enough chain never locks — both name simulation, threshold
- A threshold no average can see — both name simulation, threshold
- Patience instead of a contract — both name equilibrium selection, nash equilibrium
- The reading that is almost right — both name equilibrium selection, nash equilibrium
- Two chaotic orbits made to agree — both name simulation, threshold
Named objects
A dashed tag is an object no other essay names yet.
Best responseEquilibrium selectionNash equilibriumPotential gameSimulationThreshold