A hierarchical network formation model

Atabati, Omid and Farzad, Babak (2015): A hierarchical network formation model.

Abstract

We present a network formation model based on a particularly interesting class of networks in social settings, where individuals' positions are determined according to a topic-based or hierarchical taxonomy. In this game-theoretic model, players are located in the leaves of a complete b-ary tree as the seed network with the objective of minimizing their collective distances to others in the network. In the grid-based model of Even-Dar and Kearns [3], they demonstrate the existence of small diameter networks with the threshold of a = 2 where the cost of a new link depends on the distance between the two endpoints to the power of a. We show the appearance of small diameter equilibrium networks with the threshold of a = 1/4 in the hierarchical or tree-based networks. Moreover, the general set of equilibrium networks in our model are guaranteed to exist and they are pairwise Nash stable with transfers [2].

• Item Type: MPRA Paper
• Language: English
• Keywords: Network formation; Hierarchical networks; Linking game
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C79 - Other; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D85 - Network Formation and Analysis: Theory

References

1] Atabati, O., and B. Farzad, A strategic model for network formation, Computational Social Networks 2 (1) (2015), 1-14.

[2] Bloch, F., and M. O. Jackson, Definitions of equilibrium in network formation games, Int J Game Theory 34 (3) (2006), 305-318.

[3] Even-Dar, E., and M. Kearns, A small world threshold for economic network formation, Advances in Neural Information Processing Systems 19 (2007), 385-392.

[4] Jackson, M. O., Social and Economic Networks, Princeton U. Press, Princeton,N.J., 2008.

[5] Kleinberg, J., Small-world phenomena and the dynamics of information, Advanced Neural Information Processing Systems 14 2001, 431-438.

[6] Milgram, S., The small world problem, Psychology Today 1 (1967), 61-67.

[7] Watts, D., Six Degrees: The Science of a Connected Age, W. W. Norton, Cambridge, Mass. 2003.

[8] Watts, D., P. Dodds, and M. Newman, Identity and search in social networks, Science 296 (2002), 1302-1305.