nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Stochastic Stability in Schelling’s Segregation Model with Markovian Asynchronous Update

verfasst von : Gabriel Istrate

Erschienen in: Cellular Automata

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We investigate the dependence of steady-state properties of Schelling’s segregation model on the agents’ activation order. Our basic formalism is the Pollicott-Weiss version of Schelling’s segregation model. Our main result modifies this baseline scenario by incorporating contagion in the decision to move: (pairs of) agents are connected by a second, agent influence network. Pair activation is specified by a random walk on this network.

The considered schedulers choose the next pair nonadaptively. We can complement this result by an example of adaptive scheduler (even one that is quite fair) that is able to preclude maximal segregation. Thus scheduler nonadaptiveness seems to be required for the validity of the original result under arbitrary asynchronous scheduling. The analysis (and our result) are part of an adversarial scheduling approach we are advocating to evolutionary games and social simulations.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata

Nächstes Kapitel Cellular Automata Pseudo-Random Number Generators and Their Resistance to Asynchrony

This translates, intuitively, to the following condition: we always give the participants in a swap the chance to immediately reevaluate their last move.

This is where we use a property specific to our model of Schelling segregation, as opposed to proving a result valid for general potential game: the property that we employ is that in Schelling’s model any move m “can be undone”. This means that there is a move n using the same pair of vertices as m that brings the system back to where it was before. Move n simply “swaps back” the two agents if they were swapped by m, and leaves them in place otherwise.

Schelling, T.C.: Dynamic models of segregation. J. Math. Sociol. 1, 143–186 (1971)CrossRef

Fatès, N.: A guided tour of asynchronous cellular automata. In: Kari, J., Kutrib, M., Malcher, A. (eds.) AUTOMATA 2013. LNCS, vol. 8155, pp. 15–30. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40867-0_2CrossRefMATH

Vinković, D., Kirman, A.: A physical analogue of the Schelling model. Proc. Nat. Acad. Sci. 103(51), 19261–19265 (2006)CrossRef

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

Zhang, J.: Residential segregation in an all-integrationist world. J. Econ. Behav. Organ. 24(4), 533–550 (2004)CrossRef

Young, H.P.: Individual Strategy and Social Structure: an Evolutionary Theory of Institutions. Princeton University Press, Princeton (1998)

Brandt, C., Immorlica, N., Kamath, G., Kleinberg, R.: An analysis of one-dimensional Schelling segregation. In: Proceedings of the 44th Annual ACM STOC, pp. 789–804 (2012)

Montanari, A., Saberi, A.: Convergence to equilibrium in local interaction games. In: Proceedings of 50th Annual IEEE FOCS, pp. 303–312. IEEE (2009)

Auletta, V., Ferraioli, D., Pasquale, F., Penna, P., Persiano, G.: Logit dynamics with concurrent updates for local interaction games. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 73–84. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40450-4_7CrossRef

10.

Pollicott, M., Weiss, H.: The dynamics of Schelling-type segregation models. Adv. Appl. Math. 27, 17–40 (2001)CrossRef

11.

Hegselmann, R.: Thomas C. Schelling and James M. Sakoda: the intellectual, technical, and social history of a model. J. Artif. Soc. Soc. Simul. 20(3), 15 (2017)

12.

Fates, N., Morvan, M.: An experimental study of robustness to asynchronism for elementary cellular automata. arXiv preprint nlin/0402016 (2004)

13.

Bouré, O., Fates, N., Chevrier, V.: Probing robustness of cellular automata through variations of asynchronous updating. Nat. Comput. 11(4), 553–564 (2012)MathSciNetCrossRef

14.

Foster, D., Young, H.P.: Stochastic evolutionary game dynamics. Theor. Popul. Biol. 38(2), 219–232 (1990)MathSciNetCrossRef

15.

Young, H.P.: The dynamics of conformity. In: Social Dynamics, pp. 133–153 (2001)

16.

Page, S.E.: On incentives and updating in agent based models. Comput. Econ. 10(1), 67–87 (1997)CrossRef

17.

Kandori, M., Mailath, G.J., Rob, R.: Learning, mutation, and long run equilibria in games. Econometrica 61, 29–56 (1993)MathSciNetCrossRef

18.

Alós-Ferrer, C., Netzer, N.: The logit-response dynamics. Games Econ. Behav. 68(2), 413–427 (2010)MathSciNetCrossRef

19.

Istrate, G., Marathe, M.V., Ravi, S.S.: Adversarial scheduling analysis of game-theoretic models of norm diffusion. In: Beckmann, A., Dimitracopoulos, C., Löwe, B. (eds.) CiE 2008. LNCS, vol. 5028, pp. 273–282. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-69407-6_31CrossRefMATH

20.

Istrate, G., Marathe, M.V., Ravi, S.S.: Adversarial scheduling analysis of discrete models of social dynamics. Math. Struct. Comput. Sci. 22(5), 788–815 (2012)CrossRef

21.

Dyer, M., Greenhill, C., Goldberg, L.A., Istrate, G., Jerrum, M.: The convergence of iterated prisoner’s dilemma game. Comb. Probab. Comput. 11, 135–147 (2002)MathSciNetCrossRef

22.

Hines, P., Dobson, I., Rezaei, P.: Cascading power outages propagate locally in an influence graph that is not the actual grid topology. IEEE Trans. Power Syst. 32(2), 958–967 (2017)

23.

Fatès, N., Morvan, M.: Perturbing the topology of the game of life increases its robustness to asynchrony. In: Sloot, P.M.A., Chopard, B., Hoekstra, A.G. (eds.) ACRI 2004. LNCS, vol. 3305, pp. 111–120. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30479-1_12CrossRef

24.

Dennunzio, A., Formenti, E., Kŭrka, P.: Cellular automata dynamical systems. In: Rozenberg, G., Bäck, T., Kok, J.N. (eds.) Handbook of Natural Computing, pp. 25–75. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-540-92910-9_2CrossRefMATH

25.

Blume, L.E.: Population games. In: Durlauf, S., Young, H.P. (eds.) Social Dynamics: Economic Learning and Social Evolution. MIT Press, Cambridge (2001)

26.

Monderer, D., Shapley, L.S.: Potential games. Games Econ. Behav. 14, 124–143 (1996)MathSciNetCrossRef

Titel: Stochastic Stability in Schelling’s Segregation Model with Markovian Asynchronous Update
verfasst von: Gabriel Istrate
Verlag: Springer International Publishing
Buch: Cellular Automata
Print ISBN: 978-3-319-99812-1

Electronic ISBN: 978-3-319-99813-8

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-99813-8_38

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"