A Standard Schelling Model
Advisor: Aaron Glanzer
Internship Location: Mason Experimental Geometry Lab
Onsite Mentor: Professor Michael Jarret
In this project, we introduce a unifying framework for Schelling-type segregation models. They are defined as parametrized probility distributions on a graph using the Metropolis-Hastings distribution with specificed proposal and acceptance distributions. The framework extends to multiple demographies and vacancy types. We further provide a "practitioner's cookbook" that reframes examples like Schelling 1971 and Ising’s Model as different proposal-accept distributions. The cookbook is such that changing the ingredients creates a better recipe (a type of model).
Project Blog
Post 1: Intro Blog: A Standard Schellings Model
Hi, I’m Adithya Prabha and I’m currently working in algorithms at a lab in George Mason University (GMU). I’m working with Schelling's segregation model in an attempt to make the model more “unified”.
What exactly does that mean? We're redefining "Schelling models" as Markov chains driven by Metropolis-Hastings algorithms. Think of it kinda like this: instead of messy, agent-based simulations that freeze up, we parameterize everything (graph, demographics, proposal distributions, etc). This lets us ensure that the model is ergodic (meaning it settles into a unique long-term state regardless of where you start). I’ve also started working on a practioner’s cookbook with “recipes” for constructing other famous Schelling-like models.
Why do this? Schelling's 1971 work showed how a large amount of small scale changes can result in a very segregated city (large-scale change). Today’s variants of the same model in different fields are all over the place. They are super relevant in social sciences, physics, and even math. Unfortunately, these variants sometimes get stuck in "absorbing states” or even oscillate wildly. We hope to add stochastic rigor so that our simulations are reliable and most importantly, comparable.
From my own point of view, I hope to better understand theoretical computer science, write a paper, and become a more articulate presenter. On a wider level, I hope we successfully complete this project because it would enable more accurate modeling across a variety of fields.
Post 2: Blog #2: Model Interpretation
In the last week, I have read about the foundations of Schelling-like models. I have read literature that reformulates the classic schelling agent-based model as a graph coloring model. I have also read about the classic Schelling segregation problem as a graph coloring model combined with Markov Chain Monte Carlo (MCMC) techniques. I must say that this is really interesting, especially because it changes focus from individual agent movement to global configuration updates over a finite graph G = (V, E). Each vertex represents an agent that is assigned one of q labels/color. All these different versions of Schelling's 1971 original have one goal in mind: that is, to minimize a global unhappiness function H(f) based on agent demographics.
While reading about the metropolis-hastings function, I learned that it actually underlies MCMC simulation in this model. Metropolis-Hastings was actually created between 1950-1970. This is especially important for sampling from complex probability distributions by suggesting candidate configurations that actually accept them in a manner that is favorable for low-energy states (i.e., those with low unhappiness or H(f)).
This reformulation also improves computational efficiency because it is equivalent to relabeling nodes instead of moving agents. It is also a connection between sociology and mathematics. From a sociological perspective, it offers a theoretical understanding of emergent segregation in complex systems such as demographics or social networks. From a mathematical perspective, it utilizes tools from graph theory and probability theory. It also offers error bounds on the effects of perturbing the transition matrices. Some of the nuances include issues related to the structure of the graphs, such as grids versus random graphs. It also has implications for policy interventions in cities.
I am currently in the process of implementing this in code. I will begin by implementing it on simple graphs. Some of the edge cases I will consider include balanced versus imbalanced demographics.
Week 3: Implementation-ish
Since my last post, I've made solid progress on the implementation side of things. I got a working version of the Metropolis-Hastings Schelling simulation running on simple grid graphs. It was genuinely exciting to see it come together — you start with a randomly scattered configuration of agents, run a few thousand iterations, and watch distinct clusters of the same "color" slowly form. The global unhappiness H(f) drops over time and then stabilizes once the chain finds a local minimum, which lines up with what the theory predicts.
One thing that took me a while to understand was the proposal distribution φ. Since φ is proportional to e^(-ζH(f)), the chain is more likely to propose configurations that reduce unhappiness. Getting this to behave correctly with the acceptance criterion took some debugging, but once it clicked, the simulations started looking right.
I also spent time this week better understanding the Metropolis-Hastings algorithm itself. I had a very basic understanding from my reading last week, but actually implementing it forced me to think carefully about each step — sampling a candidate configuration, computing the acceptance ratio, and deciding whether to move forward or stay put. Doing it by hand in code made the mechanics much more concrete.
Week 5: Simulation and Explanation
With a simulation created, now would be the ideal time to take a step back and delve into exactly what is going on, especially since a term like "Metropolis-Hastings Schelling simulation" sounds complicated when really, it's a pretty simple concept. Consider a grid where people are either red or blue and have only one preference - having neighbors similar to themselves. If there are too many dissimilar neighbors, a person is said to be "unhappy". Now the question that the Schelling model asks is what happens to this city in the long run if all unhappy people continue to migrate? The traditional way to tackle this question is simply moving each person at a time till there aren't any unhappy agents left. However, such a process is highly susceptible to small changes in agent movement order and thus difficult to analyze. In contrast, our implementation proposes to use the Metropolis-Hastings algorithm, where we perform a random swap of positions of two individuals instead of moving them individually. The acceptance of that swap will be done according to whether it increases the general level of "happiness". Those swaps that decrease the "happiness" levels have a very low probability to be accepted while those that increase such a measure are usually accepted without any problem. After a few thousand steps, you can see how Schelling's idea takes place: the city gets organized into segregated zones although no one was striving for it intentionally.
Week 6: Implications and Process
This week, I'm going to step back and explain a bit more about what a Schelling Model is and why it matters.
What does a Schelling Model entail? In our new framework, “Schelling models” will mean Metropolis-Hastings Markov chains. Here is how you might conceptualize it: instead of cumbersome agent-based simulations with absorbing states, everything – the graph, demographics, and proposal distribution – will be parametrized, ensuring that the process is ergodic and always converges to a unique stationary state.
After my success with the grid graph simulation and emergence of segregation clusters, I have been pondering more about the significance of unifying the models this way and what further consequences it may entail. Schelling's 1971 discovery revealed that even minimal preferences may lead to massive segregation in populations. But modern variations, ranging from social science models to physics and networks theories, frequently face issues with absorbing states, huge oscillations, and high sensitivity to the order of updates, making agent-based models hard to analyze.
The Metropolis-Hastings framework makes everything stochastic: reliable, repeatable, and comparable.
Now for implications! In sociology, there is now greater understanding of how local rules lead to macro-level effects, allowing more accurate assessment of interventions such as mixed neighborhoods under balance versus imbalance. Mathematically, it connects graph theory, probability theory, and statistical mechanics, providing new avenues for analysis. Practically, one may develop a “cookbook” of procedures to allow others to build replicable variations.
For myself, I will gain new knowledge of theoretical computer science, helping me write a better paper and give a better presentation. Beyond that, success with a unification would lead to improvements in how one models sociological phenomena everywhere.
Week 7: Full Simulation in Code!
This week marked the first time that I truly experienced the full capabilities of our code! I created a Metropolis-Hastings algorithm on a lattice structure and let it iterate until the next iteration wouldn’t provide a better energy state. In the random case I chose that meant 10,000 times. As expected, the result proved accurate in theory. However, watching it take place is another story.
Starting from a fully randomized distribution of red and blue agents on the grid with no discernible pattern, I activated the algorithm. In the early stages, there wasn’t much to see... The agent configuration changed slightly in certain areas in order to explore new possibilities. Then, at some point during iteration 1,000, I noticed something: local clusters of similarly colored agents emerge.These pockets of same coloring have formed into groups (at 5,000 iterations). By 10,000 iterations, the lattice has achieved full segregation into red and blue regions.
It gets more interesting when the system reaches this segregated state because after that point, nothing really happens. The chain has reached a point where the value for the function H(f) (unhappiness) is at a local minimum from which it cannot be moved out due to the negative energy being at the minimum. This steady state is what our theoretical model guarantees (something not seen in the standard ABM approach).
Week 8: Non-Schelling Models
It turns out that one of the reasons why developing precise mathematics for these models was crucial is that many of the models resembling Schelling's do not hold up under closer examination.
First, there is the issue of "reducibility," meaning that the simulation gets "stuck." Classical Schelling models iterate over each agent until all are satisfied and then lock themselves into that configuration indefinitely. However, which configuration the model settles on is purely a function of which agents got their turn to act first. Thus, running the same simulation twice with a random permutation would yield vastly different levels of segregation.
Second, there is "periodicity." In some simulations, the model can find itself locked into an infinite loop. Imagine that we have two dissatisfied agents, one of type A and one of type B, sitting adjacent to each other. Then they trade spots to maximize their satisfaction. As a result, they are still adjacent to each other and therefore remain dissatisfied, swapping again the next round.
And finally, there are poorly-defined move rules. Consider the statement: "Agents choose to go to the closest vacant cell that suits them." How do agents determine such a cell? Do agents look at each vacancy in some specified order? This vagueness leads to the implementation making certain decisions that are not specified by the model but significantly impact its outcome.
The key benefit of our approach is that it eliminates this issue. Since we use the right Markov chain with precisely defined transition probabilities and acceptance probabilities, we can be sure that regardless of the initial state or update order, we reach some well-behaved stationary regime.