Network formation in the presence of contagious risk

ABSTRACT

There are a number of domains where agents must collectively form a network in the face of the following trade-off: each agent receives benefits from the direct links it forms to others, but these links expose it to the risk of being hit by a cascading failure that might spread over multi-step paths. Financial contagion, epidemic disease, and the exposure of covert organizations to discovery are all settings in which such issues have been articulated.

Here we formulate the problem in terms of strategic network formation, and provide asymptotically tight bounds on the welfare of both optimal and stable networks. We find that socially optimal networks are, in a precise sense, situated just beyond a phase transition in the behavior of the cascading failures, and that stable graphs lie slightly further beyond this phase transition, at a point where most of the available welfare has been lost. Our analysis enables us to explore such issues as the trade-offs between clustered and anonymous market structures, and it exposes a fundamental sense in which very small amounts of "over-linking" in networks with contagious risk can have strong consequences for the welfare of the participants.

References

1. R. Albert, H. Jeong, and A.-L. Barabási. Error and attack tolerance in complex networks. Nature, 406:378--382, 2000.
2. F. Allen and A. Babus. Networks in finance. Technical Report 08-07, Wharton Financial Institutions Center, Aug. 2008.
3. F. Allen and D. M. Gale. Financial contagion. Journal of Political Economy, 108(1):1--33, Feb. 2000.
4. N. Alon, I. Benjamini, and A. Stacey. Percolation on finite graphs and isoperimetric inequalities. Annals of Probability, 32:1727--1745, 2004.
5. N. Alon and J. Spencer. The Probabilistic Method. John Wiley & Sons, second edition, 2000.
6. E. Anshelevich, A. Dasgupta, É. Tardos, and T. Wexler. Near-optimal network design with selfish agents. In Proc. 35th ACM Symposium on Theory of Computing, pages 511--520, 2003.
7. V. Bala and S. Goyal. A non-cooperative model of network formation. Econometrica, 68:1181--1229, Sept. 2000.
8. M. A. Barnard. Needle sharing in context: Patterns of sharing among men and women injectors and HIV risks. Addiction, 88:805--812, 1993.
9. E. A. Bender and E. R. Canfield. The asymptotic number of labeled graphs with given degree sequences. Journal of Combinatorial Theory (Series A), 24:296--307, 1978.
10. B. Bollobás. Random Graphs. Cambridge University Press, second edition, 2001.
11. R. J. Caballero and A. Simsek. Fire sales in a model of complexity. Technical Report 15479, National Bureau of Economic Research (NBER), Nov. 2009.
12. J. Corbo and D. C. Parkes. The price of selfish behavior in bilateral network formation. In Proc. 24th ACM Symposium on Principles of Distributed Computing, pages 99--107, 2005.
13. A. Fabrikant, A. Luthra, E. N. Maneva, C. H. Papadimitriou, and S. Shenker. On a network creation game. In Proc. 22nd ACM Symposium on Principles of Distributed Computing, pages 347--351, 2003.
14. S. Goyal and A. Vigier. Robust networks, Apr. 2010. Working paper, Cambridge University.
15. A. Gutfraind. Mathematical terrorism, 2010. Ph.D. Thesis, Cornell University.
16. A. G. Haldane and R. M. May. Systemic risk in banking ecosystems. Nature, 469:351--355, 2011.
17. M. O. Jackson. Social and Economic Networks. Princeton University Press, 2008.
18. M. O. Jackson and A. Wolinsky. A strategic model of social and economic networks. Journal of Economic Theory, 71(1):44--74, 1996.
19. J. A. Jacquez, C. P. Simon, J. Koopman, L. Sattenspiel, and T. Perry. Modeling and analyzing HIV transmission: The effect of contact patterns. Mathematical Biosciences, 102(2):119--199, Dec. 1988.
20. R. M. Karp. The transitive closure of a random digraph. Random Structure and Algorithms, 1(1):73--93, 1990.
21. É. Tardos and T. Wexler. Network formation games and the potential function method. In N. Nisan, T. Roughgarden, É. Tardos, and V. Vazirani, editors, Algorithmic Game Theory, pages 487--516. Cambridge University Press, 2007.
22. N. C. Wormald. Some problems in the enumeration of labelled graphs. PhD thesis, Newcastle University, 1978.

Index Terms

• Theory of computation