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. Maarten C.W. Janssen, 1997. "Focal Points," Tinbergen Institute Discussion Papers 97-091/1, Tinbergen Institute.
    2. 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.
    3. 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.
    4. Siegfried Berninghaus & Hans Haller & Alexander Outkin, 2006. "Neural networks and contagion," Revue d'économie industrielle, De Boeck Université, vol. 0(2), pages 11-11.
    5. 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.
    6. 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.
    7. 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.
    8. Jun Honda, 2015. "Games with the Total Bandwagon Property," Department of Economics Working Papers wuwp197, Vienna University of Economics and Business, Department of Economics.
    9. 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.
    10. , & , & ,, 2008. "Monotone methods for equilibrium selection under perfect foresight dynamics," Theoretical Economics, Econometric Society, vol. 3(2), June.
    11. Basov, S., 2001. "An Evolutionary Model of Reciprocity," Department of Economics - Working Papers Series 812, The University of Melbourne.
    12. Ball, Richard, 2017. "Violations of monotonicity in evolutionary models with sample-based beliefs," Economics Letters, Elsevier, vol. 152(C), pages 100-104.
    13. Alos-Ferrer, Carlos & Ania, Ana B., 2001. "Local equilibria in economic games," Economics Letters, Elsevier, vol. 70(2), pages 165-173, February.
    14. Olivier Compte & Andrew Postlewaite, 2007. "Effecting Cooperation," PIER Working Paper Archive 09-019, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania, revised 29 May 2009.
    15. van Damme, E.E.C., 1995. "Game theory : The next stage," Other publications TiSEM 7779b0f9-bef5-45c7-ae6b-7, Tilburg University, School of Economics and Management.
    16. Norman, Thomas W.L., 2009. "Rapid evolution under inertia," Games and Economic Behavior, Elsevier, vol. 66(2), pages 865-879, July.
    17. Enrico Zaninotto & Alessandro Rossi & Loris Gaio, 1999. "Stochastic learning in coordination games: a simulation approach," Quaderni DISA 015, Department of Computer and Management Sciences, University of Trento, Italy, revised 29 Jun 2003.
    18. Roland Pongou & Roberto Serrano, 2009. "A dynamic theory of fidelity networks with an application to the spread of HIV/AIDS," Working Papers 2009-03, Instituto Madrileño de Estudios Avanzados (IMDEA) Ciencias Sociales.
    19. John T. Scholz & Cheng‐Lung Wang, 2009. "Learning to Cooperate: Learning Networks and the Problem of Altruism," American Journal of Political Science, John Wiley & Sons, vol. 53(3), pages 572-587, July.
    20. Jean-Michel Grandmont, 1998. "Expectations Formation and Stability of Large Socioeconomic Systems," Econometrica, Econometric Society, vol. 66(4), pages 741-782, July.

    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.