The Price of Anarchy for Network Formation in an Adversary Model
We study network formation with n players and link cost α > 0. After the network is built, an adversary randomly deletes one link according to a certain probability distribution. Cost for player ν incorporates the expected number of players to which ν 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 + ο (1) under moderate assumptions on the adversary and n ≥ 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 Ο (1) bound on the price of anarchy for both adversaries, the constant being bounded by 15 + ο (1) and 9 + ο (1), respectively.
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Haller, Hans & Sarangi, Sudipta, 2005. "Nash networks with heterogeneous links," Mathematical Social Sciences, Elsevier, vol. 50(2), pages 181-201, September.
- Matthew O. Jackson & Asher Wolinsky, 1995.
"A Strategic Model of Social and Economic Networks,"
1098R, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- Bloch, Francis & Jackson, Matthew O., 2007.
"The formation of networks with transfers among players,"
Journal of Economic Theory,
Elsevier, vol. 133(1), pages 83-110, March.
- Matthew O. Jackson & Francis Bloch, 2004. "The Formation of Networks with Transfers among Players," Working Papers 2004.80, Fondazione Eni Enrico Mattei.
- Bloch, Francis & Jackson, Matthew, 2004. "The Formation of Networks with Transfers among Players," Working Papers 1194, California Institute of Technology, Division of the Humanities and Social Sciences.
- Hans Haller & Sudipta Sarangi, 2003.
"Nash Networks with Heterogeneous Agents,"
Discussion Papers of DIW Berlin
337, DIW Berlin, German Institute for Economic Research.
- Watts, Alison, 2001. "A Dynamic Model of Network Formation," Games and Economic Behavior, Elsevier, vol. 34(2), pages 331-341, February.
- Antoni Calvó-Armengol & Rahmi Ilkiliç, 2005.
"Pairwise-Stability and Nash Equilibria in Network Formation,"
2005.34, Fondazione Eni Enrico Mattei.
- Antoni Calvó-Armengol & Rahmi İlkılıç, 2009. "Pairwise-stability and Nash equilibria in network formation," International Journal of Game Theory, Springer, vol. 38(1), pages 51-79, March.
- Antoni Calvó-Armengol & Rahmi Ilkiliç, 2004. "Pairwise-Stability and Nash Equilibria in Network Formation," Working Papers 182, Barcelona Graduate School of Economics.
- Johari, Ramesh & Mannor, Shie & Tsitsiklis, John N., 2006. "A contract-based model for directed network formation," Games and Economic Behavior, Elsevier, vol. 56(2), pages 201-224, August.
- Venkatesh Bala & Sanjeev Goyal, 2000. "A Noncooperative Model of Network Formation," Econometrica, Econometric Society, vol. 68(5), pages 1181-1230, September.
When requesting a correction, please mention this item's handle: RePEc:gam:jgames:v:2:y:2011:i:3:p:302-332:d:13673. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (XML Conversion Team)
If references are entirely missing, you can add them using this form.