text: 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 @math , for some @math . 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 @math steps, where @math 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.
  @cite_18: Schelling's model of segregation looks to explain the way in which particles or agents of two types may come to arrange themselves spatially into configurations consisting of large homogeneous clusters, i.e. connected regions consisting of only one type. As one of the earliest agent based models studied by economists and perhaps the most famous model of self-organising behaviour, it also has direct links to areas at the interface between computer science and statistical mechanics, such as the Ising model and the study of contagion and cascading phenomena in networks. While the model has been extensively studied it has largely resisted rigorous analysis, prior results from the literature generally pertaining to variants of the model which are tweaked so as to be amenable to standard techniques from statistical mechanics or stochastic evolutionary game theory. In BK , Brandt, Immorlica, Kamath and Kleinberg provided the first rigorous analysis of the unperturbed model, for a specific set of input parameters. Here we provide a rigorous analysis of the model's behaviour much more generally and establish some surprising forms of threshold behaviour, notably the existence of situations where an level of intolerance for neighbouring agents of opposite type leads almost certainly to segregation.
  @cite_22: We prove that the two-dimensional Schelling segregation model yields monochromatic regions of size exponential in the area of individuals' neighborhoods, provided that the tolerance parameter is a constant strictly less than 1 2 but sufficiently close to it. Our analysis makes use of a connection with the first-passage percolation model from the theory of stochastic processes.
  @cite_28: This paper presents a variation of the Schelling [J. Math. Sociol. 1 (1971) 143; T.C. Schelling, Micromotives and Macrobehavior, Norton, New York, 1978] model to show that segregation emerges and persists even if every person in the society prefers to live in a half-black, half-white neighborhood. In contrast to Schelling’s inductive approach, we formulate neighborhood transition as a spatial game played on a lattice graph. The model is rigorously analyzed using techniques recently developed in stochastic evolutionary game theory. We derive our primary results mathematically and use agent-based simulations to explore the dynamics of segregation.
  @cite_21: Using dimes and pennies on a checkerboard, Schelling (1971, 1978) studied the link between residential preferences and segregational neighborhood patterns. While his approach clearly has methodological advantages in studying the dynamics of residential segregation, Schelling's checkerboard model has never been rigorously analyzed. We propose an extension of the Schelling model that incorporates economic variables. Using techniques recently developed in stochastic evolutionary game theory, we mathematically characterize the model's long-term dynamics.
  @cite_6: We analyze the Schelling model of segregation in which a society of n individuals live in a ring. Each individual is one of two races and is only satisfied with his location so long as at least half his 2w nearest neighbors are of the same race as him. In the dynamics, randomly-chosen unhappy individuals successively swap locations. We consider the average size of monochromatic neighborhoods in the final stable state. Our analysis is the first rigorous analysis of the Schelling dynamics. We note that, in contrast to prior approximate analyses, the final state is nearly integrated: the average size of monochromatic neighborhoods is independent of n and polynomial in w.
  @cite_24: Suggests a reorientation of game theory in which players are not hyper-rational and knowledge is incomplete; postulates a simple adaptive learning process; and applies this framework to the study of social and economic institutions. Discusses learning; dynamic and stochastic stability; adaptive learning in small games; variations on the learning process; local interaction; equilibrium and disequilibrium selection in general games; bargaining; and contracts. Young is Scott and Barbara Black Professor of Economics at Johns Hopkins University. Bibliography; index.
  @cite_19: The Schelling segregation model attempts to explain possible causes of racial segregation in cities. Schelling considered residents of two types, where everyone prefers that the majority of his or her neighbors are of the same type. He showed through simulations that even mild preferences of this type can lead to segregation if residents move whenever they are not happy with their local environments. We generalize the Schelling model to include a broad class of bias functions determining individuals happiness or desire to move, called the General Influence Model. We show that for any influence function in this class, the dynamics will be rapidly mixing and cities will be integrated (i.e., there will not be clustering) if the racial bias is sufficiently low. Next we show complementary results for two broad classes of influence functions: Increasing Bias Functions (IBF), where an individual's likelihood of moving increases each time someone of the same color leaves (this does not include Schelling's threshold models), and Threshold Bias Functions (TBF) with the threshold exceeding one half, reminiscent of the model Schelling originally proposed. For both classes (IBF and TBF), we show that when the bias is sufficiently high, the dynamics take exponential time to mix and we will have segregation and a large "ghetto" will form.
  @cite_27: Schelling’s models of segregation, first described in 1969 (Am Econ Rev 59:488–493, 1969) are among the best known models of self-organising behaviour. Their original purpose was to identify mechanisms of urban racial segregation. But his models form part of a family which arises in statistical mechanics, neural networks, social science, and beyond, where populations of agents interact on networks. Despite extensive study, unperturbed Schelling models have largely resisted rigorous analysis, prior results generally focusing on variants in which noise is introduced into the dynamics, the resulting system being amenable to standard techniques from statistical mechanics or stochastic evolutionary game theory (Young in Individual strategy and social structure: an evolutionary theory of institutions, Princeton University Press, Princeton, 1998). A series of recent papers ( in: Proceedings of the 44th annual ACM symposium on theory of computing (STOC 2012), 2012); in: 55th annual IEEE symposium on foundations of computer science, Philadelphia, 2014, J Stat Phys 158:806–852, 2015), has seen the first rigorous analyses of 1-dimensional unperturbed Schelling models, in an asymptotic framework largely unknown in statistical mechanics. Here we provide the first such analysis of 2- and 3-dimensional unperturbed models, establishing most of the phase diagram, and answering a challenge from in: Proceedings of the 44th annual ACM symposium on theory of computing (STOC 2012), 2012).
  @cite_13: 
  @cite_12: Abstract The Schelling segregation models are “agent based” population models, where individual members of the population (agents) interact directly with other agents and move in space and time. In this note we study one-dimensional Schelling population models as finite dynamical systems. We define a natural notion of entropy which measures the complexity of the family of these dynamical systems. The entropy counts the asymptotic growth rate of the number of limit states. We find formulas and deduce precise asymptotics for the number of limit states, which enable us to explicitly compute the entropy.
summary: Recently, a series of papers by Young @cite_24 , Zhang @cite_21 @cite_28 , @cite_13 , @cite_6 @cite_22 , @cite_18 @cite_27 and @cite_19 initiated a rigorous analysis of stochastic processes induced by Schelling's model. In these processes either two randomly chosen unhappy agents of different type swap positions @cite_24 @cite_21 @cite_28 or a randomly chosen agent changes her type with a certain probability @cite_6 @cite_18 @cite_19 @cite_27 @cite_22 . It is worth noticing that both types of processes are closely related but not identical to Schelling's original model where discontent agents move to different positions until they become content with their current location. The focus of the above mentioned works is on investigating the expected size of the obtained homogeneous regions, but it is also shown that the stochastic processes starting from a uniform random agent placement converge with high probability to a stable placement. The convergence time was considered by Mobius & Rosenblat @cite_12 who observe that the Markov chain analyzed in @cite_24 @cite_21 @cite_28 has a very high mixing time. @cite_19 show in the two-dimensional grid case a dichotomy in mixing times for high @math and very low @math values.