Abstract
We consider a dynamic social network model in which agents play repeated games in pairings determined by a stochastically evolving social network. Individual agents begin to interact at random, with the interactions modeled as games. The game payoffs determine which interactions are reinforced, and the network structure emerges as a consequence of the dynamics of the agents’ learning behavior. We study this in a variety of game-theoretic conditions and show that the behavior is complex and sometimes dissimilar to behavior in the absence of structural dynamics. We argue that modeling network structure as dynamic increases realism without rendering the problem of analysis intractable.
This chapter is based on B. Skyrms and R. Pemantle, “A Dynamic Model of Social Network Formation” PNAS 97 (16), 9340-9346 (2000).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Refernces
Hofbauer, J. and Sigmund, K. (1988). The theory of evolution and dynamical systems (Cambridge University Press: Cambridge).
Weibull, J. (1997). Evolutionary game theory (MIT Press: Cambridge, MA).
Feldman, M. and Thomas, E. (1987). Behavior-dependent contexts for repeated player of the Prisoner’s Dilemma II: Dynamical aspects of the evolution of cooperation. J. Theor. Biol. 128, 297–315.
Wright, S. (1921). Systems of mating III: assortative mating based on somatic resemblance. Genetics 6, 144–161.
Wright, S. (1945). Tempo and mode in evolution: a critical review. Ecology 26, 415–419.
Jackson, M. and Watts, A. (1999). On the formation of interaction networks in social coordination games. Working paper.
Durrett, R. and Neuhauser, C. (1997). Coexistence results for some competition models. Ann. Appl. Prob. 7, 10–45.
Kang, H.-C., Krone, S. and Neuhauser, C. (1995). Stepping stone models with extinction and recolonization. Ann. Appl. Prob. 5, 1025–1060.
Durrett, R. and Levin, S. (1994). The importance of being discrete (and spatial). Theor. Pop. Biol. 46, 363–394.
Blume, L. (1993). The statistical mechanics of strategic interaction. Games Econ. Behav. 5, 387–423.
Pollack, G. B. (1989). Evolutionary stability on a viscous lattice. Soc. Networks 11, 175–212.
Lindgren, K. and Nordahl, M. (1994). Evolutionary dynamics and spatial games. Physica D 75, 292–309.
Anderlini, L. and Ianni, A. (1997). Learning on a torus. In: The dynamics of norms, ed. C. Bicchieri, R. Jeffrey, and B. Skyrms (Cambridge University Press: Cambridge) 87–107.
Ellison, G. (1993). Learning, local interaction, and coordination. Econometrica 61, 1047–1071.
Watts, D. and Strogatz, S. (1998) Collective dynamics of “small-world” networks. Nature 393, 440–442.
Schelling, T. (1969) Models of Segregation. Am. Eco. Rev., Papers Proc. 59, 488–493.
Schelling, T. (1971). Dynamic models of Segregation. J. Math. Sociol. 1, 143–86.
Epstein, J. and Axtell, R. (1996). Growing Artificial Societies (MIT/Brookings: Cambridge, MA).
Zajonc, R.B. (1968). Attitudinal effects of mere exposure. J. Personality Social Psychol. Monogr. 9, 1–28.
Coppersmith, D. and Diaconis, P. (1987). Reinforced Random Walk. Unpublished manuscript.
Arthur, W. B. (1989). Competing technologies, increasing returns, and lock-in by historical events. Econ. J. 99, 116–131.
Eggenberger, F. and Pólya, G. (1923). Über die Statistik verketter Vorgange. Zeit. Angew. Math. Mech. 3, 279–289.
Johnson, N. and Kotz, S. (1977). Urn models and their application (John Wiley & Sons: New York).
Durrett, R. (1996). Probability: Theory and examples, 2nd edition (Duxbury Press, Wadsworth Publishing Company: Belmont, CA).
Pemantle, R. and Skyrms, B. (2000). Reinforcement schemes may take a long time to exhibit limiting behavior. In Preparation.
Robbins, H. and Monro, S. (1951). A stochastic approximation method. Ann. Math. Statist. 22, 400–407.
Pemantle, R. (1990). Nonconvergence to unstable points in urn models and stochastic approximations. Ann. Probab. 18, 698–712.
Benaïm, M. and Hirsch, M. (1995). Dynamics of Morse-Smale urn processes. Ergodic Theor. Dyn. Syst. 15, 1005–1030.
Talagrand, M. (1995). Concentration of measure and isoperimetric inequalities in product spaces. IHES Publ. Math. 81, 73–205.
Ehrenfest, P. and Ehrenfest, T. (1907). Über zwei bekannte Einwande gegen das Bolzmannshe H-Theorem. Phys. Zeit. 8, 311–314.
Diaconis, P. and Stroock, D. (1991). Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Prob. 1, 39–61.
Kac, M. (1947). Random walk and the theory of Brownian motion. Am. Math. Monthly 54, 369–391.
Davis, B. (1990). Reinforced random walk. Prob. Theor. Rel. Fields 84, 203–229.
Foster, D. and Young, H. P. (1990). Stochastic evolutionary game theory. Theor. Pop. Biol. 38, 219–232.
Ellison, G. (2000). Basins of attraction, long run stochastic stability, and the speed of step-by-step evolution. Rev. Econ. Studies, 67 (1), 17–45.
Rousseau, J.-J. (1984). A discourse on inequality. Tr. Maurice Cranston (Penguin Books: London).
Harsanyi, J. and Selten, R. (1988). A general theory of equilibrium in games (MIT Press: Cambridge, MA).
Kandori, M., Mailath, G. and Rob, R. (1993). Learning, mutation, and long run equilibria in games. Econometrica 61, 29–56.
Alexander, J. McKenzie (2007) The Structural Evolution of Morality. Cambridge: Cambridge University Press.
Argiento, R., Pemantle, R., Skyrms, B. and Volkov, S. (forthcoming) Learning to Signal: Analysis of a Micro-Level Reinforcement Model. Stochastic Processes and their Applications.
Bala, V. and Goyal, S. (2000) A Non-Cooperative Model of Network Formation. Econometrica 68: 1181–1229.
Bonacich. P. and Liggett, T. (2003) Asymptotics of a Matrix-Valued Markov Chain Arising in Sociology. Stochastic Processes and their Applications 104: 155–171.
Goyal, S. and Vega-Redondo, F. (2005) Network Formation and Social Co-ordination. Games and Economic Behavior 50: 178–207.
Gross, T. and Blasius, B. (2008) Adaptive Coevolutionary Networks: A Review. Journal of the Royal Society Interface 5: 259–271.
Hanaki, N., Peterhansl, A., Dodds, P. S., and Watts, D. (2007) Cooperation in Evolving Social Networks. Management Science 53:1036–1050.
Jackson, M. and Watts, A. (2002) On the Formation of Interaction Networks in Social Coordination Games. Games and Economic Behavior 41: 265–291.
Kirman, A, (1997) The Economy as an Evolving Network. Journal of Evolutionary Economics 7: 339–353.
Liggett, T. M. and Rolles, S. (2004) An Infinite Stochastic Model of Social Network Formation. Stochastic Processes and their Applications 113: 65–80.
Pacheco, J. M., Traulsen, A. and Nowak, M. A. (2006) Coevolution of Structure and Strategy in Complex Networks with Dynamic Linking. Physical Review Letters 97: 258103.
Pacheco, J. M., Traulsen, A., Ohtsuki, H. and Nowak, M. A. (2008) Repeated Games and Direct Reciprocity Under Active Linking. Journal of Theoretical Biology 250: 723–731.
Pemantle, R. (2007) A Survey of Random Processes with Reinforcement. Probability Surveys 4: 1–79.
Pemantle, R. and Skyrms, B. (2004a) Time to Absorption in Discounted Reinforcement Models. Stochastic Processes and their Applications 109:1–12.
Pemantle, R. and Skyrms, B. (2004b) Network Formation by Reinforcement Learning: The Long and the Medium Run. Mathematical Social Sciences 48:315–327.
Santos, F. C., J. M. Pacheco and T. Lenaerts (2006) Cooperation Prevails when Individual Adjust their Social Ties. PloS Computational Biology 2: 1284–1291.
Skyrms, B. (2004) The Stag Hunt and the Evolution of Social Structure. Cambridge: Cambridge University Press.
Skyrms, B. (2009) Groups and Networks: Their Role in the Evolution of Cooperation. In Groups, Games and the Global Good. Ed. Simon Levin. Berlin: Springer Verlag.
Skyrms, B. and R. Pemantle (forthcoming) Learning to Network. In Probability in Science. Ed. E. Eells and J. Fetzer. Open Court Publishing.
Watts, A. (2001) A Dynamic Model of Network Formation. Games and Economic Behavior 34: 331–341.
Zimmerman, M. G., Eguiluz, V. M., San Miguel, M. (2004) Coevolution of Dynamical States and Interactions in Dynamic Networks. Physical Review E 69: 065102.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Skyrms, B., Pemantle, R. (2009). A Dynamic Model of Social Network Formation. In: Gross, T., Sayama, H. (eds) Adaptive Networks. Understanding Complex Systems. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01284-6_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-01284-6_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01283-9
Online ISBN: 978-3-642-01284-6
eBook Packages: Physics and AstronomyPhysics and Astronomy (R0)