Dynamics in tree formation games
Network formation games capture two conflicting objectives of selfish nodes in a network: such nodes wish to form a well-connected network and, at the same time, to minimize their cost of participation. We consider three families of such models where nodes avoid forming edges beyond those necessary for connectivity, thus forming tree networks. We focus on two local two-stage best-response dynamics in these models, where nodes can only form links with others in a restricted neighborhood. Despite this locality, both our dynamics converge to efficient outcomes in two of the considered families of models. In the third family of models, both our dynamics guarantee at most constant efficiency loss. This is in contrast with the standard best-response dynamics whose efficiency loss is unbounded in all three families of models. Thus we present a globally constrained network formation game where local dynamics naturally select desirable outcomes.
If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
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.:
- Oecd, 2001. "The Internet and Business Performance," OECD Digital Economy Papers 57, OECD Publishing.
- 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.
- Matthew O. Jackson & Asher Wolinsky, 1994.
"A Strategic Model of Social and Economic Networks,"
1098, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- repec:cup:cbooks:9780521674096 is not listed on IDEAS
- Matthew O. Jackson, 2003.
"A Survey of Models of Network Formation: Stability and Efficiency,"
Game Theory and Information
- Matthew O. Jackson, 2003. "A survey of models of network formation: Stability and efficiency," Working Papers 1161, California Institute of Technology, Division of the Humanities and Social Sciences.
- Jackson, Matthew O., 1998.
"The Evolution of Social and Economic Networks,"
1044, California Institute of Technology, Division of the Humanities and Social Sciences.
- Drew Fudenberg & David K. Levine, 1996.
"The Theory of Learning in Games,"
Levine's Working Paper Archive
624, David K. Levine.
- repec:cup:cbooks:9780521857406 is not listed on IDEAS
- Ma Jinpeng, 1995. "Stable Matchings and Rematching-Proof Equilibria in a Two-Sided Matching Market," Journal of Economic Theory, Elsevier, vol. 66(2), pages 352-369, August.
When requesting a correction, please mention this item's handle: RePEc:eee:gamebe:v:79:y:2013:i:c:p:1-29. 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: (Zhang, Lei)
If references are entirely missing, you can add them using this form.