pith. sign in

arxiv: 1907.07513 · v1 · pith:BSQXQLRRnew · submitted 2019-07-17 · 💻 cs.GT

Convergence and Hardness of Strategic Schelling Segregation

Hagen Echzell , Tobias Friedrich , Pascal Lenzner , Louise Molitor , Marcus Pappik , Friedrich Sch\"one , Fabian Sommer , David Stangl This is my paper

Pith reviewed 2026-05-24 19:57 UTC · model grok-4.3

classification 💻 cs.GT
keywords Schelling segregationimproving response dynamicsconvergence thresholdsweak acyclicitygame theoryresidential segregationmulti-type agentsgraph dynamics
0
0 comments X

The pith

Generalized Schelling segregation has sharp thresholds where improving dynamics switch from linear-time convergence to violating weak acyclicity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that in a game-theoretic generalization of Schelling segregation allowing multiple agent types and arbitrary graphs, improving response dynamics converge for tolerance values below certain thresholds but can violate weak acyclicity above them. These sharp transitions hold for the original two-type grid model as well. When the dynamics converge, they reach an equilibrium after at most O(m) steps where m is the number of edges. The results map the precise boundary between guaranteed convergence and the strongest form of non-convergence.

Core claim

In the generalized Schelling game, there exist sharp thresholds on the tolerance parameter such that improving response dynamics are guaranteed to converge below the threshold but the game can violate weak acyclicity above it. The same threshold results apply to Schelling's original model. In all convergent cases the dynamics reach an equilibrium in O(m) steps for m the number of edges in the underlying graph, and this bound is achieved in simulations from random initial placements.

What carries the argument

Improving response dynamics (IRD) on the strategic Schelling game, in which discontent agents swap positions with other discontent agents or move to random empty cells to raise their satisfaction fraction above τ.

If this is right

  • Below the threshold, equilibria can be found by running IRD in at most O(m) steps.
  • Above the threshold, no convergence guarantee exists so other algorithmic approaches become necessary.
  • The same convergence-versus-non-convergence transition occurs in the classic two-type grid setting.
  • The O(m) step bound is tight for random starting configurations on the graphs tested.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Small shifts in resident tolerance could flip entire neighborhoods from stable to unstable segregation patterns when modeled on real street graphs.
  • Empirical Schelling studies that assume convergence should test whether their chosen tolerance lies below or above the identified thresholds.
  • The threshold technique may transfer to other local-improvement processes on graphs with similar move rules.

Load-bearing premise

The model assumes discontent agents move exclusively by swapping with other discontent agents or jumping to random empty cells on an arbitrary graph.

What would settle it

Simulate improving response dynamics on a concrete small graph with tolerance value just above the identified threshold and check whether a cycle violating weak acyclicity appears.

Figures

Figures reproduced from arXiv: 1907.07513 by David Stangl, Fabian Sommer, Friedrich Sch\"one, Hagen Echzell, Louise Molitor, Marcus Pappik, Pascal Lenzner, Tobias Friedrich.

Figure 1
Figure 1. Figure 1: (a) Residential segregation in New York City, color-coded by ethnicity. Every dot [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An IRC for the SSG with x = max  d 1 τ−0.5 e, d 1 2−2τ e  for τ ∈ [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An IRC for the 1-k-SSG with x > 3 4τ − 1 for any τ ∈ (0, 0.5]. Agent types are marked orange, blue and gray. Multiple nodes in series represent a clique of nodes of the stated size. Edges between cliques or between a clique and single nodes represent that all involved nodes are completely interconnected. 2.2 IRD Convergence for the One-versus-One Version Remember, that in the 1-1-SSG and 1-1-JSG, respectiv… view at source ↗
Figure 4
Figure 4. Figure 4: An IRC with exactly one improving swap per step for the 1-1-SSG with [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: An IRC for the JSG for τ > 2 ∆ on a ∆-regular network. Empty nodes are white, agents of type T1 are orange, type T2 agents are blue. Multiple nodes in series represent a clique of ∆ − 2 nodes. An edge between a clique and a single node denotes that each clique node is connected to that single node. An edge between two cliques represents that each clique node as exactly one neighbor in the other clique. Wit… view at source ↗
Figure 6
Figure 6. Figure 6: An IRC with exactly one improving jump per step for the JSG for [PITH_FULL_IMAGE:figures/full_fig_p013_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: A network where the optimal placement p ∗ G is not in equilibrium for τ > 0.9. Multiple nodes in series represent a clique of nodes of the stated size. Edges between cliques or between a clique and single nodes represent that all involved nodes are completely interconnected. equivalent statements for computing stable placements. The following example illustrates the rather counter-intuitive fact that an op… view at source ↗
Figure 8
Figure 8. Figure 8: Number of moves until convergence on 8-regular toroidal grids and 8 [PITH_FULL_IMAGE:figures/full_fig_p018_8.png] view at source ↗
read the original abstract

The phenomenon of residential segregation was captured by Schelling's famous segregation model where two types of agents are placed on a grid and an agent is content with her location if the fraction of her neighbors which have the same type as her is at least $\tau$, for some $0<\tau<1$. Discontent agents simply swap their location with a randomly chosen other discontent agent or jump to a random empty cell. We analyze a generalized game-theoretic model of Schelling segregation which allows more than two agent types and more general underlying graphs modeling the residential area. For this we show that both aspects heavily influence the dynamic properties and the tractability of finding an optimal placement. We map the boundary of when improving response dynamics (IRD), i.e., the natural approach for finding equilibrium states, are guaranteed to converge. For this we prove several sharp threshold results where guaranteed IRD convergence suddenly turns into the strongest possible non-convergence result: a violation of weak acyclicity. In particular, we show such threshold results also for Schelling's original model, which is in contrast to the standard assumption in many empirical papers. Furthermore, we show that in case of convergence, IRD find an equilibrium in $\mathcal{O}(m)$ steps, where $m$ is the number of edges in the underlying graph and show that this bound is met in empirical simulations starting from random initial agent placements.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper studies a generalized game-theoretic version of Schelling's segregation model on arbitrary graphs with multiple agent types. Agents are content if at least a fraction τ of their neighbors match their type; discontent agents relocate either by swapping with another discontent agent or by jumping to a uniformly random empty cell. The central results are sharp thresholds (for both the generalized model and Schelling's original two-type grid) separating regimes in which improving response dynamics (IRD) are guaranteed to converge from regimes in which weak acyclicity is violated. When convergence occurs, the paper proves an O(m) step bound (m = number of edges) and reports that this bound is observed in simulations from random initial placements.

Significance. If the thresholds are correct, the work supplies precise, load-bearing boundaries between convergent and non-convergent behavior in a canonical segregation model, directly contradicting the convergence assumption common in empirical Schelling studies. The O(m) bound is a strong positive result for tractability. The paper earns credit for deriving parameter-free sharp thresholds via explicit potential-function and cycle constructions rather than fitted parameters, and for stating the linear convergence bound together with supporting simulations.

major comments (1)
  1. [§2, Theorems 3.3, 4.1, 5.2] §2 (model definition) and Theorems 3.3, 4.1, 5.2: the sharp thresholds separating guaranteed IRD convergence from violation of weak acyclicity rest entirely on the movement rule that discontent agents may only swap with other discontent agents or jump to a uniformly random empty cell. The potential-function arguments and the explicit cycle constructions that witness non-acyclicity fail if agents may move to any empty cell or swap with content agents. Because the paper presents the thresholds as applying to “Schelling’s original model,” the manuscript must justify why this formalization is the correct reading of the 1971 dynamics; without that justification the claimed applicability to the original model is not yet supported.
minor comments (2)
  1. [Abstract] The abstract states the O(m) bound and the existence of simulations but does not cross-reference the section containing the proof or the simulation protocol; adding such pointers would improve readability.
  2. [§6] Simulation figures (presumably §6) should state the precise graph families, values of τ, and number of trials used so that the reported O(m) behavior can be reproduced from the text alone.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful and constructive review. The primary concern raised is the need for explicit justification of the movement rule in relation to Schelling's 1971 model. We address this point below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§2, Theorems 3.3, 4.1, 5.2] §2 (model definition) and Theorems 3.3, 4.1, 5.2: the sharp thresholds separating guaranteed IRD convergence from violation of weak acyclicity rest entirely on the movement rule that discontent agents may only swap with other discontent agents or jump to a uniformly random empty cell. The potential-function arguments and the explicit cycle constructions that witness non-acyclicity fail if agents may move to any empty cell or swap with content agents. Because the paper presents the thresholds as applying to “Schelling’s original model,” the manuscript must justify why this formalization is the correct reading of the 1971 dynamics; without that justification the claimed applicability to the original model is not yet supported.

    Authors: We agree that the specific movement rule (swaps restricted to other discontent agents, or jumps to a uniformly random empty cell) is essential to both the potential-function arguments establishing convergence and the cycle constructions establishing violation of weak acyclicity. Different rules would indeed invalidate these proofs. In §2 we define the model precisely in this way and state that it formalizes Schelling's original dynamics. To address the concern, the revised manuscript will expand the model section with a dedicated paragraph that (i) quotes the relevant passages from Schelling (1971) describing relocation of unhappy agents, (ii) explains why restricting swaps to discontent agents and random jumps to empty cells is a faithful and standard interpretation consistent with the original description and with subsequent literature, and (iii) clarifies that all stated thresholds and the O(m) bound apply to this dynamics. We will also add a short remark noting that alternative movement rules lie outside the scope of the present analysis. revision: yes

Circularity Check

0 steps flagged

No circularity; direct proofs on explicitly defined model

full rationale

The paper defines its generalized Schelling model and movement rules (discontent agents swap with other discontent agents or jump to random empty cells) explicitly in the model section, then derives convergence thresholds and non-convergence results (e.g., violation of weak acyclicity) via direct proofs such as potential functions and cycle constructions. These steps do not reduce to fitted inputs renamed as predictions, self-citation chains, or ansatzes smuggled from prior work by the same authors. The results hold conditionally on the stated dynamics and graph, with no load-bearing reliance on external self-citations or redefinitions that would make the claims tautological. This is the standard structure of a theoretical analysis paper and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard domain assumptions from graph theory and game theory for the model generalization; no free parameters, invented entities, or ad-hoc axioms are indicated in the abstract.

axioms (2)
  • domain assumption Residential areas are modeled as undirected graphs with nodes as locations and edges as neighbor relations.
    This enables the generalization beyond grids stated in the abstract.
  • domain assumption Agents move only via improving swaps with other discontent agents or to empty cells when below satisfaction threshold tau.
    This defines the IRD dynamics whose convergence properties are analyzed.

pith-pipeline@v0.9.0 · 5799 in / 1413 out tokens · 33870 ms · 2026-05-24T19:57:19.869096+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages

  1. [1]

    R. D. Alba and J. R. Logan. Minority proximity to whites in suburbs: An individual-level analysis of segregation. American journal of sociology, 98(6):1388–1427, 1993

    work page 1993

  2. [2]

    Barmpalias, R

    G. Barmpalias, R. Elwes, and A. Lewis-Pye. Digital morphogenesis via schelling segrega- tion. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pages 156–165. IEEE, 2014

    work page 2014

  3. [3]

    Barmpalias, R

    G. Barmpalias, R. Elwes, and A. Lewis-Pye. Unperturbed schelling segregation in two or three dimensions. Journal of Statistical Physics, 164(6):1460–1487, 2016

    work page 2016

  4. [4]

    Bazgan, Z

    C. Bazgan, Z. Tuza, and D. Vanderpooten. The satisfactory partition problem. Discrete Applied Mathematics, 154(8):1236 – 1245, 2006

    work page 2006

  5. [5]

    Benard and R

    S. Benard and R. Willer. A wealth and status-based model of residential segregation. Mathematical Sociology, 31(2):149–174, 2007

    work page 2007

  6. [6]

    Benenson, E

    I. Benenson, E. Hatna, and E. Or. From schelling to spatially explicit modeling of urban ethnic and economic residential dynamics. Sociological Methods and Research, 37(4):463– 497, 5 2009

    work page 2009

  7. [7]

    Bhakta, S

    P. Bhakta, S. Miracle, and D. Randall. Clustering and mixing times for segregation models onZ2. In Symposium on Discrete Algorithms (SODA), pages 327–340, 2014

    work page 2014

  8. [8]

    Brandt, N

    C. Brandt, N. Immorlica, G. Kamath, and R. Kleinberg. An analysis of one-dimensional schelling segregation. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing (STOC), pages 789–804. ACM, 2012

    work page 2012

  9. [9]

    E. E. Bruch. How population structure shapes neighborhood segregation. American Journal of Sociology, 119(5):1221–1278, 2014

    work page 2014

  10. [10]

    D. Cable. The racial dot map. Weldon Cooper Center for Public Service, University of Virginia, 2013

    work page 2013

  11. [11]

    Chauhan, P

    A. Chauhan, P. Lenzner, and L. Molitor. Schelling segregation with strategic agents. In International Symposium on Algorithmic Game Theory (SAGT), pages 137–149. Springer, 2018

    work page 2018

  12. [12]

    W. A. V. Clark. Residential segregation in american cities: a review and interpretation. Population Research and Policy Review, 5(2):95–127, Jan 1986

    work page 1986

  13. [13]

    W. A. V. Clark and M. Fossett. Understanding the social context of the schelling segregation model. Proceedings of the National Academy of Sciences, 105(11):4109–4114, 2008

    work page 2008

  14. [14]

    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press and McGraw-Hill, 2001

    work page 2001

  15. [15]

    Elkind, J

    E. Elkind, J. Gan, A. Igarashi, W. Suksompong, and A. A. Voudouris. Schelling games on graphs. arXiv preprint arXiv:1902.07937, to appear at IJCAI’19, 2019

    work page arXiv 1902

  16. [16]

    J. M. Epstein and R. Axtell. Growing Artificial Societies: Social Science from the Bottom Up. The Brookings Institution, 1996

    work page 1996

  17. [17]

    M. Fossett. Ethnic preferences, social distance dynamics, and residential segregation: The- oretical explorations using simulation analysis. Journal of Mathematical Sociology, 30(3- 4):185–273, 2006. 19

    work page 2006

  18. [18]

    M. A. Fossett. Simseg–a computer program to simulate the dynamics of residential seg- regation by social and ethnic status. Race and Ethnic Studies Institute Technical Report and Program, Texas A&M University, 1998

    work page 1998

  19. [19]

    Garey, D

    M. Garey, D. Johnson, and L. Stockmeyer. Some simplified np-complete graph problems. Theoretical Computer Science, 1(3):237 – 267, 1976

    work page 1976

  20. [20]

    M. R. Garey and D. S. Johnson. Computers and intractability. W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences

    work page 1979

  21. [21]

    R. J. Gaylord and L. J. d’Andria. Simulating Society: A” Mathematica” Toolkit for Modeling Socioeconomic Behaviour. Springer Science & Business Media, 1998

    work page 1998

  22. [22]

    M. U. Gerber and D. Kobler. Partitioning a graph to satisfy all vertices. Technical report, 1998

    work page 1998

  23. [23]

    M. U. Gerber and D. Kobler. Algorithmic approach to the satisfactory graph partitioning problem. European Journal of Operational Research, (125):283 – 291, 2000

    work page 2000

  24. [24]

    Gerhold, L

    S. Gerhold, L. Glebsky, C. Schneider, H. Weiss, and B. Zimmermann. Computing the complexity for schelling segregation models. Communications in Nonlinear Science and Numerical Simulation, (13):2236 – 2245, 2008

    work page 2008

  25. [25]

    Grauwin, F

    S. Grauwin, F. Goffette-Nagot, and P. Jensen. Dyanmic models of residential segregation: an analytical solution. Journal of Public Economics, (96):124 – 141, 2012

    work page 2012

  26. [26]

    A. D. Henry, P. Pra lat, and C.-Q. Zhang. Emergence of segregation in evolving social networks. Proceedings of the National Academy of Sciences, 108(21):8605–8610, 2011

    work page 2011

  27. [27]

    Immorlica, R

    N. Immorlica, R. Kleinbergt, B. Lucier, and M. Zadomighaddam. Exponential segregation in a two-dimensional schelling model with tolerant individuals. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 984–993. SIAM, 2017

    work page 2017

  28. [28]

    Mobius and T

    M. Mobius and T. Rosenblat. Computing the complexity for schelling segregation models. Unpublished manuscript, 2000

    work page 2000

  29. [29]

    Monderer and L

    D. Monderer and L. S. Shapley. Potential games. Games and economic behavior, 14(1):124– 143, 1996

    work page 1996

  30. [30]

    Pancs and N

    R. Pancs and N. J. Vriend. Schelling’s spatial proximity model of segregation revisited. Journal of Public Economics, 91(1):1 – 24, 2007

    work page 2007

  31. [31]

    T. C. Schelling. Models of segregation. The American Economic Review, 59(2):488–493, 1969

    work page 1969

  32. [32]

    T. C. Schelling. Dynamic models of segregation. Journal of mathematical sociology, 1(2):143–186, 1971

    work page 1971

  33. [33]

    T. C. Schelling. Micromotives and macrobehavior. WW Norton & Company, 2006

    work page 2006

  34. [34]

    Singh, D

    A. Singh, D. Vainchtein, and H. Weiss. Schelling’s Segregation Model: Parameters, scaling, and aggregation. Demographic Research, 21(12):341–366, 2009

    work page 2009

  35. [35]

    Vinkovi´ c and A

    D. Vinkovi´ c and A. Kirman. A physical analogue of the schelling model. Proceedings of the National Academy of Sciences, 103(51):19261–19265, 2006. 20

    work page 2006

  36. [36]

    H. P. Young. The evolution of conventions. Econometrica: Journal of the Econometric Society, pages 57–84, 1993

    work page 1993

  37. [37]

    H. P. Young. Individual strategy and social structure : an evolutionary theory of institutions. Princeton University Press Princeton, N.J, 1998

    work page 1998

  38. [38]

    J. Zhang. A dynamic model of residential segregation. The Journal of Mathematical Sociology, 28(3):147–170, 2004

    work page 2004

  39. [39]

    J. Zhang. Residential segregation in an all-integrationist world. Journal of Economic Behavior and Organization, 54(4):533–550, 2004

    work page 2004

  40. [40]

    J. Zhang. Tipping and residential segregation: a unified schelling model. J. of Regional Science, 51(1):167–193, 2011. 21

    work page 2011