The Existence of Pairwise Stable Networks

Matthew O. Jackson ; Alison Watts

Professor of Economics, Humanities and Social Sciences 228-77, Caltech, Pasadena, CA 91125, USA, Tel: +1-626-395-4022 jacksonm@hss.caltech.edu
Assistant Professor, Department of Economics, Southern illinois University, Carbondale, IL 62901, USA, Tel: +1-618-453-5072 wattsa@siu.edu

JEL Classification: A14, D20, J00

Abstract

We examine networks connecting individuals, where the payoff to an individual from an economic or social activity depends on the full network of connections among individuals. Individuals can form and sever links connecting themselves to other individuals based on the improvement that the resulting network offers them relative to the current network. As individuals do this, we obtain sequences of networks called ‘improving paths.’ We study conditions under which such sequences cycle, and conditions under which such sequences lead to a stable network. Specifically, we give conditions necessary and sufficient to rule out cycles, which are in turn sufficient conditions for existence of pairwise stable networks.

Keywords:

Networks, Pairwise stable, Network formation

Acknowledgments

This paper was prepared for a lecture presented at the 9th SJE-KlSDl International Symposium: Cost Allocation in Telecommunications, Seoul National University. We thank the participants for the helpful discussion and especially to Youngsub Chun for the invitation to participate.

References

Arrow, K. J., and Borzekowski, R. “Limited Network Connections and the Distribution of Wages.” Mimeograph, Stanford University, 2000.
Aumann, R., and Myerson, R. “Endogenous Formation of Links Between Players and Coalitions: An Application of the Shapley Value.” In A. Roth (ed.), The Shapley Value. Cambridge University Press, 1988. [https://doi.org/10.1017/CBO9780511528446.013]
Bala, V., and Goyal, S. “A Non-Cooperative Model of Network Formation.” Econometrica 68 (2000): 1181-229. [https://doi.org/10.1111/1468-0262.00155]
Boorman, S. “A Combinatorial Optimization Model for Transmission of Job Information through Contact Networks.” Bell Journal of Economics 6 (1975): 216-49. [https://doi.org/10.2307/3003223]
Calvo-Armengol, A., and Jackson, M. O. “Social Networks and Resulting Patterns and Dynamics of Employment and Wages.” Mimeograph, Caltech, 2001.
Droste, E. R., Gilles, P., and Johnson, C. “Evolution of Conventions in Endogenous Social Networks.” Mimeograph, Virginia Tech, 2000.
Dutta, B., and Jackson, M. O. “The Stability and Efficiency of Directed Communication Networks.” Review of Economic Design 5 (2000): 251-72. [https://doi.org/10.1007/PL00013688]
Dutta, B. “On the Formation of Networks and Groups.” In B. Dutta and M. O. Jackson (eds.), Models of the Formation of Networks and Groups. Forthcoming from Springer-Verlag: Heidelberg, 2001.
Dutta, B., and Mutuswami, S. “Stable Networks.” Journal of Economic Theory 76 (1997): 322-44. [https://doi.org/10.1006/jeth.1997.2306]
Ellison, G. “Learning, Local Interaction, and Coordination.” Econometrica 61 (1993): 1047-71. [https://doi.org/10.2307/2951493]
Fafchamps, M., and Lund, S. “Risk-Sharing Networks in Rural Philippines.” Mimeograph, Stanford University, 1997. [https://doi.org/10.2139/ssrn.71379]
Goyal, S., and Vega-Redondo, F. “Learning, Network Formation and Coordination.” Mimeograph, Erasmus University, 1999.
Jackson, M. O. “The Stability and Efficiency of Economic and Social Networks.” Forthcoming in Advances in Economic Design, Edited by Murat Sertel; to be Reprinted in Models of the Formation of Networks and Groups, Edited by B, Dutta and M. O. Jackson, Forthcoming from Springer-Verlag: Heidelberg, 2001.
Jackson, M. O., and van den Nouweland, A. “Strongly Stable Networks.” Mimeograph, Caltech and the University of Oregon, 2001.
Jackson, M. O., and Watts, A. “The Evolution of Social and Economic Networks.” Forthcoming in Journal of Economic Theory, 1998.
Jackson, M. O., and Watts, A. “On the Formation of Interaction Networks in Social Coordination Games.” Forthcoming in Games and Economic Behavior, 1999.
Jackson, M. O., and Wolinsky, A. “A Strategic Model of Social and Economic Networks.” Journal of Economic Theory 71 (1996): 44-74. [https://doi.org/10.1006/jeth.1996.0108]
Kandori, M., Mailath, G., and Rob, R. “Learning, Mutation, and Long Run Equilibria in Games.” Econometrica 61 (1993): 29-56. [https://doi.org/10.2307/2951777]
Kreps, D. “Notes on the Theory of Choice.” In Underground Classics in Economics. Westview Press, Boulder, 1988.
Montgomery, J. “Social Networks and Labor Market Outcomes.” American Economic Review 81 (1991): 1408-18.
Myerson, R. “Graphs and Cooperation in Games.” Math. Operations Research 2 (1977): 225-9. [https://doi.org/10.1287/moor.2.3.225]
Page, F., and Wooders, M., and Kamat, S. “Networks and Farsighted Stability.” DP Warwick University, 2001.
Ritzberger, R., and Weibull, J. “Evolutionary Selection in Normal- Form Games.” Econometrica 63 (1995): 1371-99. [https://doi.org/10.2307/2171774]
Skyrms, B., and Pemantle, R. “A Dynamic Model of Social Network Formation.” Proceedings of the National Academy of Sciences 97 (2000): 9340-6. [https://doi.org/10.1073/pnas.97.16.9340]
Topa, G. “Social Interactions, Local Spillovers and Unemployment.” Review of Economic Studies 68 (2001): 261-96. [https://doi.org/10.1111/1467-937X.00169]
Watts, A. “A Dynamic Model of Network Formation.” Games and Economic Behavior 34 (2001): 331-41. [https://doi.org/10.1006/game.2000.0803]
Watts, A. “Non-Myopic Formation of Circle Networks.” Economics Letters 74 (No. 2 2002): 277-82. [https://doi.org/10.1016/S0165-1765(01)00540-7]
Young, H. P. “The Evolution of Conventions.” Econometrica 61 (1993): 57-84. [https://doi.org/10.2307/2951778]