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.
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.
@cite_18 @cite_22 @cite_28 @cite_21 @cite_6 @cite_24 @cite_19 @cite_27 @cite_13 @cite_12
2953060309 2099205567 2028633127 2963904935
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. We introduce an extended family of continuous-domain stochastic models for sparse, piecewise-smooth signals. These are specified as solutions of stochastic differential equations, or, equivalently, in terms of a suitable innovation model; the latter is analogous conceptually to the classical interpretation of a Gaussian stationary process as filtered white noise. The two specific features of our approach are 1) signal generation is driven by a random stream of Dirac impulses (Poisson noise) instead of Gaussian white noise, and 2) the class of admissible whitening operators is considerably larger than what is allowed in the conventional theory of stationary processes. We provide a complete characterization of these finite-rate-of-innovation signals within Gelfand's framework of generalized stochastic processes. We then focus on the class of scale-invariant whitening operators which correspond to unstable systems. We show that these can be solved by introducing proper boundary conditions, which leads to the specification of random, spline-type signals that are piecewise-smooth. These processes are the Poisson counterpart of fractional Brownian motion; they are nonstationary and have the same 1 ω-type spectral signature. We prove that the generalized Poisson processes have a sparse representation in a wavelet-like basis subject to some mild matching condition. We also present a limit example of sparse process that yields a MAP signal estimator that is equivalent to the popular TV-denoising algorithm. Random graph models with limited choice have been studied extensively with the goal of understanding the mechanism of the emergence of the giant component. One of the standard models are the Achlioptas random graph processes on a fixed set of (n ) vertices. Here at each step, one chooses two edges uniformly at random and then decides which one to add to the existing configuration according to some criterion. An important class of such rules are the bounded-size rules where for a fixed (K 1 ), all components of size greater than (K ) are treated equally. While a great deal of work has gone into analyzing the subcritical and supercritical regimes, the nature of the critical scaling window, the size and complexity (deviation from trees) of the components in the critical regime and nature of the merging dynamics has not been well understood. In this work we study such questions for general bounded-size rules. Our first main contribution is the construction of an extension of Aldous’s standard multiplicative coalescent process which describes the asymptotic evolution of the vector of sizes and surplus of all components. We show that this process, referred to as the standard augmented multiplicative coalescent (AMC) is ‘nearly’ Feller with a suitable topology on the state space. Our second main result proves the convergence of suitably scaled component size and surplus vector, for any bounded-size rule, to the standard AMC. This result is new even for the classical Erdős–Renyi setting. The key ingredients here are a precise analysis of the asymptotic behavior of various susceptibility functions near criticality and certain bounds from (The barely subcritical regime. Arxiv preprint, 2012) on the size of the largest component in the barely subcritical regime. 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).