IDEAS home Printed from https://ideas.repec.org/a/spr/comaot/v15y2009i2d10.1007_s10588-008-9050-2.html
   My bibliography  Save this article

The survival of the weakest in networks

Author

Listed:
  • S. Nikoletseas

    (Computer Technology Institute
    University of Patras)

  • C. Raptopoulos

    (Computer Technology Institute
    University of Patras)

  • P. Spirakis

    (Computer Technology Institute
    University of Patras)

Abstract

We study here dynamic antagonism in a fixed network, represented as a graph G of n vertices. In particular, we consider the case of k≤n particles walking randomly independently around the network. Each particle belongs to exactly one of two antagonistic species, none of which can give birth to children. When two particles meet, they are engaged in a (sometimes mortal) local fight. The outcome of the fight depends on the species to which the particles belong. Our problem is to predict (i.e. to compute) the eventual chances of species survival. We prove here that this can indeed be done in expected polynomial time on the size of the network, provided that the network is undirected.

Suggested Citation

  • S. Nikoletseas & C. Raptopoulos & P. Spirakis, 2009. "The survival of the weakest in networks," Computational and Mathematical Organization Theory, Springer, vol. 15(2), pages 127-146, June.
    • Handle: RePEc:spr:comaot:v:15:y:2009:i:2:d:10.1007_s10588-008-9050-2
    DOI: 10.1007/s10588-008-9050-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10588-008-9050-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10588-008-9050-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Kandori, Michihiro & Mailath, George J & Rob, Rafael, 1993. "Learning, Mutation, and Long Run Equilibria in Games," Econometrica, Econometric Society, vol. 61(1), pages 29-56, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Saha Atanu & Havenner Arthur & Rauschenbach Sonya, 2019. "The Rise of Dominant Firms: The Role of Chance," Open Economics, De Gruyter, vol. 2(1), pages 76-91, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ponti, Giovanni, 2000. "Cycles of Learning in the Centipede Game," Games and Economic Behavior, Elsevier, vol. 30(1), pages 115-141, January.
    2. repec:bla:reviec:v:17:y:2009:i:si:p:327-337 is not listed on IDEAS
    3. H Peyton Young, 2014. "The Evolution of Social Norms," Economics Series Working Papers 726, University of Oxford, Department of Economics.
    4. Maarten C.W. Janssen, 1997. "Focal Points," Tinbergen Institute Discussion Papers 97-091/1, Tinbergen Institute.
    5. Michael Kosfeld, 2002. "Stochastic strategy adjustment in coordination games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 20(2), pages 321-339.
    6. Gale, John & Binmore, Kenneth G. & Samuelson, Larry, 1995. "Learning to be imperfect: The ultimatum game," Games and Economic Behavior, Elsevier, vol. 8(1), pages 56-90.
    7. Burkhard C. Schipper, 2004. "Submodularity and the evolution of Walrasian behavior," International Journal of Game Theory, Springer;Game Theory Society, vol. 32(4), pages 471-477, August.
    8. Sanjeev Goyal & Fernando Vega-Redondo, 2000. "Learning, Network Formation and Coordination," Econometric Society World Congress 2000 Contributed Papers 0113, Econometric Society.
    9. Siegfried Berninghaus & Hans Haller & Alexander Outkin, 2006. "Neural networks and contagion," Revue d'économie industrielle, De Boeck Université, vol. 0(2), pages 11-11.
    10. Ennis, Huberto M. & Keister, Todd, 2005. "Government policy and the probability of coordination failures," European Economic Review, Elsevier, vol. 49(4), pages 939-973, May.
    11. Anthonisen, Niels, 1997. "On the Convergence of Beliefs within Populations in Games with Learning," Journal of Economic Theory, Elsevier, vol. 76(1), pages 169-184, September.
    12. Ianni, A., 2002. "Reinforcement learning and the power law of practice: some analytical results," Discussion Paper Series In Economics And Econometrics 203, Economics Division, School of Social Sciences, University of Southampton.
    13. Conley, John P. & Neilson, William S., 2013. "Endogenous coordination and discoordination games: Multiculturalism and assimilation," Journal of Economic Behavior & Organization, Elsevier, vol. 92(C), pages 176-191.
    14. Markus Kinateder & Luca Paolo Merlino, 2021. "The Evolution of Networks and Local Public Good Provision: A Potential Approach," Games, MDPI, vol. 12(3), pages 1-12, July.
    15. William Tracy, 2014. "Paradox Lost: The Evolution of Strategies in Selten’s Chain Store Game," Computational Economics, Springer;Society for Computational Economics, vol. 43(1), pages 83-103, January.
    16. Takuya Sekiguchi, 2023. "Fixation Probabilities of Strategies for Trimatrix Games and Their Applications to Triadic Conflict," Dynamic Games and Applications, Springer, vol. 13(3), pages 1005-1033, September.
    17. Hofbauer, Josef & Sorger, Gerhard, 1999. "Perfect Foresight and Equilibrium Selection in Symmetric Potential Games," Journal of Economic Theory, Elsevier, vol. 85(1), pages 1-23, March.
    18. Jun Honda, 2015. "Games with the Total Bandwagon Property," Department of Economics Working Papers wuwp197, Vienna University of Economics and Business, Department of Economics.
    19. Bergstrom, Theodore C & Stark, Oded, 1993. "How Altruism Can Prevail in an Evolutionary Environment," American Economic Review, American Economic Association, vol. 83(2), pages 149-155, May.
    20. Hopkins, Ed, 1999. "Learning, Matching, and Aggregation," Games and Economic Behavior, Elsevier, vol. 26(1), pages 79-110, January.
    21. , & , & ,, 2008. "Monotone methods for equilibrium selection under perfect foresight dynamics," Theoretical Economics, Econometric Society, vol. 3(2), June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:comaot:v:15:y:2009:i:2:d:10.1007_s10588-008-9050-2. See general information about how to correct material in RePEc.

    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 CitEc recognized a bibliographic reference but did not link an item in RePEc 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 RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.