Advanced Search
MyIDEAS: Login

Dynamics in tree formation games

Contents:

Author Info

  • Arcaute, E.
  • Dyagilev, K.
  • Johari, R.
  • Mannor, S.
Registered author(s):

    Abstract

    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.

    Download Info

    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.
    File URL: http://www.sciencedirect.com/science/article/pii/S0899825613000055
    Download Restriction: Full text for ScienceDirect subscribers only

    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.

    Bibliographic Info

    Article provided by Elsevier in its journal Games and Economic Behavior.

    Volume (Year): 79 (2013)
    Issue (Month): C ()
    Pages: 1-29

    as in new window
    Handle: RePEc:eee:gamebe:v:79:y:2013:i:c:p:1-29

    Contact details of provider:
    Web page: http://www.elsevier.com/locate/inca/622836

    Related research

    Keywords: Network formation games; Network dynamics; Strong stability; Tree formation games;

    Find related papers by JEL classification:

    References

    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.:
    as in new window
    1. 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.
    2. Vega-Redondo,Fernando, 2007. "Complex Social Networks," Cambridge Books, Cambridge University Press, number 9780521674096, October.
    3. 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.
    4. Drew Fudenberg & David K. Levine, 1996. "The Theory of Learning in Games," Levine's Working Paper Archive 624, David K. Levine.
    5. Vega-Redondo,Fernando, 2007. "Complex Social Networks," Cambridge Books, Cambridge University Press, number 9780521857406, October.
    6. Matthew O. Jackson & Asher Wolinsky, 1995. "A Strategic Model of Social and Economic Networks," Discussion Papers 1098R, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    7. 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.
    8. Oecd, 2001. "The Internet and Business Performance," OECD Digital Economy Papers 57, OECD Publishing.
    9. 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.
    Full references (including those not matched with items on IDEAS)

    Citations

    Lists

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    Statistics

    Access and download statistics

    Corrections

    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 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.