Order of Play in Sequential Network Formation

San Román, Diego (2025): Order of Play in Sequential Network Formation.

Abstract

Research in anthropology and neuroscience has shown that people have a cognitive limit on the number of stable relationships they can maintain. In this spirit, we consider a network formation game in which the cost of link formation is increasing in the agent's degree. In this class of games, as opposed to commonly studied games with a fixed cost of link formation, the order in which agents form the network (order of play) determines its final structure. In particular, we find that only certain orders of play can explain the formation of circle and complete bipartite networks. We also find that there is multiplicity of equilibria only when marginal costs of link formation are intermediate. Our results show as well that some orders of play are better than others for predicting the equilibrium structure when it is not unique, and that playing last is usually harmful.

• Item Type: MPRA Paper
• Language: English
• Keywords: sequential network formation, pairwise stability, order of play, costs of link formation increasing in degree
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D85 - Network Formation and Analysis: Theory

References

Baetz, O. (2015). Social activity and network formation. Theoretical Economics 10 (2), 315–340.

Bala, V. and S. Goyal (2000). A noncooperative model of network formation. Econometrica 68 (5), 1181–1229.

Ballester, C., A. Calvó-Armengol, and Y. Zenou (2006). Who’s who in networks. wanted: The key player. Econometrica 74 (5), 1403–1417.

Barberà, S. and A. Gerber (2025). On the endogenous order of play in sequential games. Available at SSRN 4810792 .

Belhaj, M., S. Bervoets, and F. Deroïan (2016). Efficient networks in games with local complementarities. Theoretical Economics 11 (1), 357–380. Bonacich, P. (1987). Power and centrality: A family of measures. American Journal of Sociology 92, 1170 – 1182.

Cabrales, A. and E. Hauk (2022). Norms and the evolution of leaders’ followership.

Cimini, G., A. Gabrielli, and F. Sylos Labini (2014). The scientific competitiveness of nations. PloS one 9 (12), e113470

Di Clemente, R., B. Lengyel, L. F. Andersson, and R. Eriksson (2022). Under standing european integration with bipartite networks of comparative advantage. PNAS nexus 1(5), pgac262.

DiMaggio, P. and F. Garip (2012). Network effects and social inequality. Annual review of sociology 38(1), 93–118.

Gualdi, S., G. Cimini, K. Primicerio, R. Di Clemente, and D. Challet (2016). Statistically validated network of portfolio overlaps and systemic risk. Scientific reports 6(1), 39467.

Herings, P. J.-J., A. Mauleon, and V. Vannetelbosch (2009). Farsightedly stable networks. Games and Economic Behavior 67(2), 526–541.

Hiller, T. (2017). Peer effects in endogenous networks. Games and Economic Behavior 105, 349–367.

Hinnosaar, T. (2024). Optimal sequential contests. Theoretical Economics 19(1), 207–244.

Hu, H., G. Dragotto, Z. Zhang, K. Liang, B. Stellato, and J. F. Fisac (2024). Who plays first? optimizing the order of play in stackelberg games with many robots. arXiv preprint arXiv:2402.09246.

Jackson, M. O. (2008). Social and Economic Networks. Princeton University Press.

Jackson, M. O. and A. Watts (2002). On the formation of interaction networks in social coordination games. Games and Economic Behavior 41(2), 265–291.

Jackson, M. O. and A. Wolinsky (1996). A strategic model of social and economic networks. Journal of Economic Theory 71(1), 44–74.

Joshi, S., A. S. Mahmud, and S. Sarangi (2020). Network formation with multi graphs and strategic complementarities. Journal of Economic Theory 188, 105033, https://doi.org/10.1016/j.jet.2020.105033.

Joshi, S., A. S. Mahmud, and H. Tzavellas (2025). Multiplex formation. Available at SSRN 4499938. Mimeo

Kinateder, M. and L. P. Merlino (2017). Public goods in endogenous networks. American Economic Journal: Microeconomics 9(3), 187–212.

König, M. D., C. J. Tessone, and Y. Zenou (2014). Nestedness in networks: A theoretical model and some applications. Theoretical Economics 9(3), 695–752.

Le Quement, M., J. Rivas, and K. Kawamura (2025). Whom to ask first? a model of sequential consultation. Available at https://drive.google.com /file/d/1P41UKTAecQ0b2Lea9m6uq3VcuMyGonEk/view?usp=sharing.

Sadler, E. (2025). Making a swap: network formation with increasing marginal costs. Available at SSRN.

Saracco, F., R. Di Clemente, A. Gabrielli, and T. Squartini (2015). Randomizing bipartite networks: the case of the world trade web. Scientific reports 5(1), 10595.

Watts, D. J. and S. H. Strogatz (1998). Collective dynamics of ‘small-world’ net works. Nature 393(6684), 440–442.

Wilhite, A. (2001). Bilateral trade and ‘small-world’networks. Computational economics 18, 49–64.