Ronen Gradwohl
ABSTRACT
A Nash equilibrium is an optimal strategy for each player under the assumption that others play according to their respective Nash strategies. In the presence of irrational
players or coalitions of colluding players, however, it provides no guarantees. Some recent literature has focused on measuring the potential damage caused by the presence of faulty behavior, as well as designing mechanisms that are resilient against such faults. In this paper we show that large games are naturally fault tolerant. We first 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 then show that general large games also have some non-trivial resilience against faults.
- R. J. Aumann. Acceptable points in general cooperative n-persongames. Contributions to the Theory of Games, Annals ofMathematical Studies, IV, 1959. Pages 287--324.Google Scholar
- A. Aiyer, L. Alvisi, A. Clement, M. Dahlin, J.-P. Martin, andC. Porth. BAR fault tolerance for cooperative services. Proceedings of 20th ACM Symposium on Operating Systems Principles, 2005.Pages 45--58. Google ScholarDigital Library
- I. Abraham, D. Dolev, R. Gonen, and J. Halpern.Distributed computing meets game theory: Robust mechanisms for rational secret sharingand multiparty computation. Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing, 2006.Pages 53--62. Google ScholarDigital Library
- I. Abraham, D. Dolev, and J. Halpern.Lower bounds on implementing robust and resilient mediators.To appear in 5th IACR Theory of Cryptography Conference, 2008. Google ScholarDigital Library
- N. I. Al--Najjar and R. Smorodinsky. Pivotal players and the characterizationof influence.Journal of Economic Theory 92, 2000.Pages 318--342.Google Scholar
- A. Blum, M. Hajiaghayi, K. Ligett, and A. Roth.Regret minimization and the price of total anarchy. To appear in STOC, 2008. Google ScholarDigital Library
- M. Babaioff, R. Kleinberg, and C. Papadimitriou.Congestion games with malicious players. Electronic Commerce, 2007. Google ScholarDigital Library
- B. D. Bernheim, B. Peleg, and M. Whinston. Coalition proof Nash equilibrium: Concepts. Journal of Economic Theory, 42(1), 1989. Pages 1--12.Google ScholarCross Ref
- S. Chien and A. Sinclair. Convergence to approximateNash equilibria in congestion games. SODA, 2007. Google ScholarDigital Library
- C. Daskalakis and C. Papadimitriou. Computing equilibria in anonymous games. Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007.Pages 83--93. Google ScholarDigital Library
- K. Eliaz. Fault-tolerant implementation. Review of Economic Studies, 69(3),2002. Pages 589--610.Google ScholarCross Ref
- R. Gradwohl and O. Reingold.Partial exposure in large games. Submitted.Google Scholar
- J. Halpern.A computer scientist looks at game theory. Games and Economic Behavior 45:1, 2003.Pages 114--131.Google ScholarCross Ref
- J. Halpern. Computer science and game theory: A brief survey.To appear in The New Palgrave Dictionary of Economics.Google Scholar
- D. Incinkas and A. Pelc. Impact of asynchrony on the behavior of rational selfish agents.Fundamenta Informaticae 82(1-2), 2008. Pages 113--125. Google ScholarDigital Library
- E. Kalai. Large robust games. Econometrica, Vol. 72, No. 6, November 2004.Pages 1631--1665.Google ScholarCross Ref
- E. Kalai. Partially-specified large games. Lecture Notes in Computer Science 3828, 2005.Pages 3--13. Google ScholarDigital Library
- S. Kalyanaraman and C. Umans. Algorithms for playing games with limited randomness. Proceedings of the 15th Annual European Symposium on Algorithms, 2007.Pages 323--334. Google ScholarDigital Library
- T. Moscibroda, S. Schmid, and R. Wattenhofer. When selfish meets evil: Byzantineplayers in a virus inoculation game. 25th Annual Symposium on Principles of Distributed Computing, 2006. Google ScholarDigital Library
- D. Monderer and M. Tennenholtz. Distributed games. Games and Economic Behavior 28, 1999. Pages 55--72.Google Scholar
- D. Monderer and M. Tennenholtz. Distributed games: frommechanisms to protocols. AAAI, 1999. Pages 32--37. Google ScholarDigital Library
- D. Moreno and J. Wooders. Coalition-proof equilibrium. Games and Economic Behavior,17(1), 1996. Pages 80--112.Google ScholarCross Ref
- J. B. Nielsen (editor): Summary Report on Rational Cryptographic Protocols.ECRYPT Report D. PROVI.7, March 2007.Google Scholar
- M.J. Osborne and A. Rubinstein. A Course in Game Theory,MIT Press, Cambridge, MA, 1994.Google Scholar
- S. Peled, A. Yadin, and A. Yehudayoff,The maximal probability that k-wise independent bits are all 1.arXiv:math.PR/0801.0059. Google ScholarDigital Library
- S. M. Samuels. On the number of successes in independent trials. The Annals of Mathematical Statistics, Vol. 36, No. 4, August 1965.Pages 1272--1278.Google ScholarCross Ref
- R. Selten. A reexamination of the perfectness concept for equilibrium points in extensive games. International Journal of Game Theory 4, 1975. Pages 25--55.Google Scholar
Index Terms
- Fault tolerance in large games
Recommendations
Generic Uniqueness of Equilibrium in Large Crowding Games
A crowding game is a noncooperative game in which the payoff of each player depends only on the player's action and the size of the set of players choosing that particular action: The larger the set, the smaller the payoff. Finite, n-player crowding games ...
Egalitarian Solutions of Large Games: I. A Continuum of Players
This is the first of two papers devoted to the study of egalitarian solutions for nontransferable utility NTU games with a large number of players. This paper is concerned with the construction of egalitarian solutions for the limit situation with a ...
Lipschitz Games
The Lipschitz constant of a finite normal-form game is the maximal change in some player's payoff when a single opponent changes his strategy. We prove that games with small Lipschitz constant admit pure ε-equilibria, and pinpoint the maximal Lipschitz ...
Comments