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.:
- Drew Fudenberg & David K. Levine, 1998.
"The Theory of Learning in Games,"
MIT Press Books,
The MIT Press,
edition 1, volume 1, number 0262061945, December.
- 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.
- Vega-Redondo,Fernando, 2007. "Complex Social Networks," Cambridge Books, Cambridge University Press, number 9780521674096, December.
- Jackson, Matthew O. & Watts, Alison, 2002.
"The Evolution of Social and Economic Networks,"
Journal of Economic Theory,
Elsevier, vol. 106(2), pages 265-295, October.
- 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.
- Vega-Redondo,Fernando, 2007. "Complex Social Networks," Cambridge Books, Cambridge University Press, number 9780521857406, December.
- 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.
- Oecd, 2001. "The Internet and Business Performance," OECD Digital Economy Papers 57, OECD Publishing.
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: (Dana Niculescu)
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.