Efficient structure of noisy communication networks

Breitmoser, Yves and Vorjohann, Pauline (2012): Efficient structure of noisy communication networks.

Abstract

In the canonical network model, the connections model, only three specific network structures are generically efficient: complete, empty, and star networks. This renders many plausible network structures inefficient. We show that requiring robustness with respect to stochastic transmission failures rehabilitates incomplete, circular network structures. Specifically, we show that near the "bifurcation" where both star and complete network are efficient in the standard connections model, star and complete network are generally inefficient as transmission failures become possible. As for four-player networks, we additionally show that the circle network is uniquely efficient and robust near this bifurcation.

• Item Type: MPRA Paper
• Language: English
• Keywords: communication network, information flow, stochastics, robustness, efficiency, connections model
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C70 - General; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D85 - Network Formation and Analysis: Theory

References

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

Bala, V. and Goyal, S. (2000b). A strategic analysis of network reliability. Review of Economic Design, 5(3):205–228.

Billand, P., Bravard, C., and Sarangi, S. (2008). Existence of nash networks in one-way flow models. Economic Theory, 37(3):491–507.

Bloch, F. and Dutta, B. (2009). Communication networks with endogenous link strength. Games and Economic Behavior, 66(1):39–56.

Bloch, F. and Jackson, M. (2007). The formation of networks with transfers among players. Journal of Economic Theory, 133(1):83–110.

Deroïan, F. (2009). Endogenous link strength in directed communication networks. Mathematical Social Sciences, 57(1):110–116.

Dutta, B., Ghosal, S., and Ray, D. (2005). Farsighted network formation. Journal of Economic Theory, 122(2):143–164.

Galeotti, A. (2006). One-way flow networks: the role of heterogeneity. Economic Theory, 29(1):163–179.

Galeotti, A., Goyal, S., and Kamphorst, J. (2006). Network formation with heterogeneous players. Games and Economic Behavior, 54(2):353–372.

Haller, H., Kamphorst, J., and Sarangi, S. (2007). (Non-) existence and scope of Nash networks. Economic Theory, 31(3):597–604.

Haller, H. and Sarangi, S. (2005). Nash networks with heterogeneous links. Mathematical Social Sciences, 50(2):181–201.

Harrison, R. and Muñoz, R. (2008). Stability and equilibrium selection in a link formation game. Economic Theory, 37(2):335–345.

Hojman, D. and Szeidl, A. (2008). Core and periphery in networks. Journal of Economic Theory, 139(1):295–309.

Hoory, S., Linial, N., and Wigderson, A. (2006). Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439–561.

Jackson, M. and Rogers, B. (2005). The economics of small worlds. Journal of the European Economic Association, 3(2-3):617–627.

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

Kannan, R., Ray, L., and Sarangi, S. (2007). The structure of information networks. Economic Theory, 30(1):119–134.

Kim, C. and Wong, K. (2007). Network formation and stable equilibrium. Journal of Economic Theory, 133(1):536–549.