COMPUTING SCIENCE

# The Math of Segregation

# Firewalls of Color

When Schelling began his experiments in algorithmic social science, he had nothing like NetLogo to play with. Indeed, he had no computational aids at all. His first model was a paper-and-pencil affair, where agents were represented by plus signs and zeros. Furthermore, the model was one-dimensional, with the symbols arranged along a line rather than on a plane. And the rules of the game were stricter: Agents could move only if doing so transformed them from unhappy to happy; neither neutral nor unfavorable moves were allowed.

A paper presented last year at the Symposium on the Theory of Computing harks back to the original one-dimensional Schelling model. The authors are Christina Brandt of Stanford University, Nicole Immorlica of the Microsoft New England Research Center, Gautam Kamath of MIT, and Robert Kleinberg of Cornell University. For convenience I refer to this quartet as the BIKK group.

The BIKK model does not match Schelling’s first version in every detail, but it’s close. *N* agents are randomly assigned to two color groups and randomly arranged along a line. The ends of the line are then joined to form a ring. There are no vacant sites. Every agent surveys a neighborhood that includes its own site and *w* sites to the left and right, for a total of 2*w*+1 neighbors. The agent is unhappy if the proportion of like-colored agents in this interval is less than the threshold τ; in the BIKK study τ is always equal to 1/2. A move consists in swapping two randomly chosen unhappy agents of opposite colors. (With τ=1/2, the swap necessarily makes both agents happy.)

The BIKK group proves that this system evolves to a “frozen” state, in which no more swaps are possible. The frozen state is segregated, in the sense that most agents find themselves in an environment where well over 50 percent of their neighbors are like-colored. But the segregation is local rather than global. The society breaks down into blocks whose size is determined by the neighborhood radius *w*, not by the overall population size *N*. Specifically, as *w* increases, the block size grows no faster than *w*^{2}. (The BIKK group hopes to improve on this result, showing that the growth rate is no greater than *w*.)

Because of the randomness inherent in the Schelling process, the proofs have a probabilistic aspect. It’s not possible to say that the model will absolutely never yield two giant monochromatic blocks; after all, the random initialization of the sites could produce that state at the outset. But the proof shows that as *N* goes to infinity, the probability of such an anomalous event approaches zero.

The key idea behind the BIKK analysis is the observation that once a monochromatic run of sites reaches a length of *w*+1, none of those agents will ever again become unhappy, and so they will never move. Such a formation is called a firewall, because agents of the opposite color cannot go through it. The BIKK authors establish upper and lower bounds on the frequency of firewalls, showing that “for any site on the ring, with high probability, the process will eventually form firewalls of both colors on both sides of the site.” The firewalls become the nuclei of the segregated blocks. Because there are a fair number of firewalls, they cannot grow too big before they run into each other.

EMAIL TO A FRIEND :