IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v86y2014icp438-457.html
   My bibliography  Save this article

Fault tolerance in large games

Author

Listed:
  • Gradwohl, Ronen
  • Reingold, Omer

Abstract

A Nash equilibrium is an optimal strategy for each player under the assumption that others play according to their respective Nash strategies, but it provides no guarantees in the presence of irrational players or coalitions of colluding players. In fact, no such guarantees exist in general. However, in this paper we show that large games are innately fault tolerant. We quantify the ways in which two subclasses of large games – λ-continuous games and anonymous games – are resilient against Byzantine faults (i.e. irrational behavior), coalitions, and asynchronous play. We also show that general large games have some non-trivial resilience against faults.

Suggested Citation

  • Gradwohl, Ronen & Reingold, Omer, 2014. "Fault tolerance in large games," Games and Economic Behavior, Elsevier, vol. 86(C), pages 438-457.
    • Handle: RePEc:eee:gamebe:v:86:y:2014:i:c:p:438-457
    DOI: 10.1016/j.geb.2013.06.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825613000894
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2013.06.007?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. Chen, Jing & Micali, Silvio, 2012. "Collusive dominant-strategy truthfulness," Journal of Economic Theory, Elsevier, vol. 147(3), pages 1300-1312.
    2. Moreno, Diego & Wooders, John, 1996. "Coalition-Proof Equilibrium," Games and Economic Behavior, Elsevier, vol. 17(1), pages 80-112, November.
    3. Kfir Eliaz, 2002. "Fault Tolerant Implementation," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 69(3), pages 589-610.
    4. Gradwohl, Ronen & Reingold, Omer, 2010. "Partial exposure in large games," Games and Economic Behavior, Elsevier, vol. 68(2), pages 602-613, March.
    5. Monderer, Dov & Tennenholtz, Moshe, 1999. "Distributed Games," Games and Economic Behavior, Elsevier, vol. 28(1), pages 55-72, July.
    6. Deheuvels, Paul & Puri, Madan L. & Ralescu, Stefan S., 1989. "Asymptotic expansions for sums of nonidentically distributed Bernoulli random variables," Journal of Multivariate Analysis, Elsevier, vol. 28(2), pages 282-303, February.
    7. Halpern, Joseph Y., 2003. "A computer scientist looks at game theory," Games and Economic Behavior, Elsevier, vol. 45(1), pages 114-131, October.
    8. Ehud Kalai, 2004. "Large Robust Games," Econometrica, Econometric Society, vol. 72(6), pages 1631-1665, November.
    9. Martin J. Osborne & Ariel Rubinstein, 1994. "A Course in Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262650401, April.
    10. Al-Najjar, Nabil I. & Smorodinsky, Rann, 2000. "Pivotal Players and the Characterization of Influence," Journal of Economic Theory, Elsevier, vol. 92(2), pages 318-342, June.
    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. Kalai, Adam Tauman & Kalai, Ehud, 2024. "Beyond dominance and Nash: Ranking equilibria by critical mass," Games and Economic Behavior, Elsevier, vol. 144(C), pages 378-394.
    2. Duk Gyoo Kim & Daehong Min & John Wooders, 2022. "Viable Nash Equilibria: An Experiment," CESifo Working Paper Series 9913, CESifo.

    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. Deb, Joyee & Kalai, Ehud, 2015. "Stability in large Bayesian games with heterogeneous players," Journal of Economic Theory, Elsevier, vol. 157(C), pages 1041-1055.
    2. Yaron Azrieli & Eran Shmaya, 2013. "Lipschitz Games," Mathematics of Operations Research, INFORMS, vol. 38(2), pages 350-357, May.
    3. Joseph Y. Halpern, 2007. "Computer Science and Game Theory: A Brief Survey," Papers cs/0703148, arXiv.org.
    4. Gradwohl, Ronen & Reingold, Omer, 2010. "Partial exposure in large games," Games and Economic Behavior, Elsevier, vol. 68(2), pages 602-613, March.
    5. Hitoshi Matsushima, 2007. "Behavioral Aspects of Implementation Theory ( The further revision was subsequently published in "Economics Letters". )," CARF F-Series CARF-F-112, Center for Advanced Research in Finance, Faculty of Economics, The University of Tokyo.
    6. Dirk Bergemann & Stephen Morris, 2012. "Robust Mechanism Design," World Scientific Book Chapters, in: Robust Mechanism Design The Role of Private Information and Higher Order Beliefs, chapter 2, pages 49-96, World Scientific Publishing Co. Pte. Ltd..
    7. Hitoshi Matsushima, 2013. "Process manipulation in unique implementation," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 41(4), pages 883-893, October.
    8. Matsushima, Hitoshi, 2008. "Role of honesty in full implementation," Journal of Economic Theory, Elsevier, vol. 139(1), pages 353-359, March.
    9. Alex Centeno, 2022. "A Structural Model for Detecting Communities in Networks," Papers 2209.08380, arXiv.org, revised Oct 2022.
    10. Hitoshi Matsushima, 2004. "Non-Consequential Moral Preferences, Detail-Free Implementation, and Representative Systems," CIRJE F-Series CIRJE-F-304, CIRJE, Faculty of Economics, University of Tokyo.
    11. Valeska Groenert, 2013. "Trimmed equilibrium," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(1), pages 99-114, February.
    12. Al-Najjar, Nabil I. & Smorodinsky, Rann, 2007. "The efficiency of competitive mechanisms under private information," Journal of Economic Theory, Elsevier, vol. 137(1), pages 383-403, November.
    13. Hitoshi Matsushima, 2004. "Non-Consequential Moral Preferences, Detail-Free Implementation, and Representative Systems ( Revised as CARF-F-062(2006) )," CARF F-Series CARF-F-015, Center for Advanced Research in Finance, Faculty of Economics, The University of Tokyo.
    14. Hitoshi Matsushima, 2008. "Implementation and Social Influence," CARF F-Series CARF-F-140, Center for Advanced Research in Finance, Faculty of Economics, The University of Tokyo.
    15. Jing Chen & Silvio Micali, 2016. "Leveraging Possibilistic Beliefs in Unrestricted Combinatorial Auctions," Games, MDPI, vol. 7(4), pages 1-19, October.
    16. Laslier, Jean-François & Weibull, Jörgen, 2008. "Commitee decisions: optimality and equilibrium," SSE/EFI Working Paper Series in Economics and Finance 692, Stockholm School of Economics, revised 11 Mar 2008.
    17. Kalai, Ehud & Shmaya, Eran, 2018. "Large strategic dynamic interactions," Journal of Economic Theory, Elsevier, vol. 178(C), pages 59-81.
    18. Kets, W., 2008. "Networks and learning in game theory," Other publications TiSEM 7713fce1-3131-498c-8c6f-3, Tilburg University, School of Economics and Management.
    19. Hitoshi Matsushima, 2009. "Implementation and Mind Control," CARF F-Series CARF-F-174, Center for Advanced Research in Finance, Faculty of Economics, The University of Tokyo.
    20. Hitoshi Matsushima, 2007. "Role of Honesty in Full Implementation ( Revised version of CARF-F-062(2006); The further revision was subsequently published in "Journal of Economic Theory" as a short article. )," CARF F-Series CARF-F-109, Center for Advanced Research in Finance, Faculty of Economics, The University of Tokyo.

    More about this item

    Keywords

    Nash equilibrium; Large games; Fault tolerance;
    All these keywords.

    JEL classification:

    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games

    Statistics

    Access and download statistics

    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:eee:gamebe:v:86:y:2014:i:c:p:438-457. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    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.