×

zbMATH — the first resource for mathematics

The price of anarchy for network formation in an adversary model. (English) Zbl 1311.91058
Summary: We study network formation with \(n\) players and link cost \(\alpha>0\). After the network is built, an adversary randomly deletes one link according to a certain probability distribution. Cost for player \(v\) incorporates the expected number of players to which \(v\) will become disconnected. We focus on unilateral link formation and Nash equilibrium. We show existence of Nash equilibria and a price of stability of \(1+o(1)\) under moderate assumptions on the adversary and \(n\geq 9\). We prove bounds on the price of anarchy for two special adversaries: one removes a link chosen uniformly at random, while the other removes a link that causes a maximum number of player pairs to be separated. We show an \(O(1)\) bound on the price of anarchy for both adversaries, the constant being bounded by \(15+o(1)\) and \(9+o(1)\), respectively.

MSC:
91A43 Games involving graphs
91A06 \(n\)-person games, \(n>2\)
PDF BibTeX XML Cite
Full Text: DOI
References:
[9] Bala, A strategic analysis of network reliability, Rev. Econ. Des 5 pp 205– (2000)
[10] Chakrabarti, Network potentials, Rev. Econ. Des. 11 pp 13– · Zbl 1274.91358
[12] Jackson, A Survey of Models of Network Formation: Stability and Efficiency, Group Formation in Economics; Networks, Clubs and Coalitions Chapter 1 (2004)
[14] Jackson, A strategic model of social and economic networks, J. Econ. Theor. 71 pp 44– (1996) · Zbl 0871.90144 · doi:10.1006/jeth.1996.0108
[16] Sarangi, Nash Networks with Heterogeneous Agents. (2003)
[17] Haller, Nash networks with heterogeneous links, Math. Soc. Sci. 50 pp 181– (2005) · Zbl 1115.91041 · doi:10.1016/j.mathsocsci.2005.02.003
[18] Bala, A noncooperative model of network formation, Econometrica 68 pp 1181– (2000) · Zbl 1022.91047 · doi:10.1111/1468-0262.00155
[19] Myerson, Game Theory: Analysis of Conflict (2002)
[20] Watts, A dynamic model of network formation, Games Econ. Behav. 34 pp 331– (2001) · Zbl 0989.90011 · doi:10.1006/game.2000.0803
[21] Calvó-Armengol, Pairwise Stability and Nash Equilibria in Network Formation (2005)
[23] Bloch, The formation of networks with transfers among players, J. Econ. Theor. 133 pp 83– (2007) · Zbl 1280.91034 · doi:10.1016/j.jet.2005.10.003
[24] Bloch, Definitions of equilibrium in network formation games, Int. J. Game Theor. 34 pp 305– (2006) · Zbl 1178.91033 · doi:10.1007/s00182-006-0022-9
[25] Anshelevich, Near-optimal network design with selfish agents, Theor. Comput. 4 pp 77– (2008) · Zbl 1213.68698 · doi:10.4086/toc.2008.v004a004
[29] Johari, A contract-based model for directed network formation, Games Econ. Behav. 56 pp 201– (2006) · Zbl 1177.91059 · doi:10.1016/j.geb.2005.08.010
[32] Lin, On the price of anarchy of a network creation game (2003)
[43] Diestel, Graph Theory (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.