Fault tolerance in large games

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.

REFERENCES

• 1: R. J. Aumann. Acceptable points in general cooperative n-persongames. Contributions to the Theory of Games, Annals ofMathematical Studies, IV, 1959. Pages 287--324.
• 2: Amitanand S. Aiyer , Lorenzo Alvisi , Allen Clement , Mike Dahlin , Jean-Philippe Martin , Carl Porth, BAR fault tolerance for cooperative services, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 3: Ittai Abraham , Danny Dolev , Rica Gonen , Joe Halpern, Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146393]
• 4: 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.
• 5: N. I. Al--Najjar and R. Smorodinsky. Pivotal players and the characterizationof influence.Journal of Economic Theory 92, 2000.Pages 318--342.
• 6: Avrim Blum , MohammadTaghi Hajiaghayi , Katrina Ligett , Aaron Roth, Regret minimization and the price of total anarchy, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374430]
• 7: Moshe Babaioff , Robert Kleinberg , Christos H. Papadimitriou, Congestion games with malicious players, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250926]
• 8: B. D. Bernheim, B. Peleg, and M. Whinston. Coalition proof Nash equilibrium: Concepts. Journal of Economic Theory, 42(1), 1989. Pages 1--12.
• 9: Steve Chien , Alistair Sinclair, Convergence to approximate Nash equilibria in congestion games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.169-178, January 07-09, 2007, New Orleans, Louisiana
• 10: Constantinos Daskalakis , Christos Papadimitriou, Computing Equilibria in Anonymous Games, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.83-93, October 21-23, 2007 [doi>10.1109/FOCS.2007.19]
• 11: K. Eliaz. Fault-tolerant implementation. Review of Economic Studies, 69(3),2002. Pages 589--610.
• 12: R. Gradwohl and O. Reingold.Partial exposure in large games. Submitted.
• 13: J. Halpern.A computer scientist looks at game theory. Games and Economic Behavior 45:1, 2003.Pages 114--131.
• 14: J. Halpern. Computer science and game theory: A brief survey.To appear in The New Palgrave Dictionary of Economics.
• 15: David Ilcinkas , Andrzej Pelc, Impact of Asynchrony on the Behavior of Rational Selfish Agents, Fundamenta Informaticae, v.82 n.1-2, p.113-125, August 2008
• 16: E. Kalai. Large robust games. Econometrica, Vol. 72, No. 6, November 2004.Pages 1631--1665.
• 17: E. Kalai. Partially-specified large games. Lecture Notes in Computer Science 3828, 2005.Pages 3--13.
• 18: 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.
• 19: Thomas Moscibroda , Stefan Schmid , Roger Wattenhofer, When selfish meets evil: byzantine players in a virus inoculation game, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146391]
• 20: D. Monderer and M. Tennenholtz. Distributed games. Games and Economic Behavior 28, 1999. Pages 55--72.
• 21: Dov Monderer , Moshe Tennenholtz, Distributed games: from mechanisms to protocols, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.32-37, July 18-22, 1999, Orlando, Florida, United States
• 22: D. Moreno and J. Wooders. Coalition-proof equilibrium. Games and Economic Behavior,17(1), 1996. Pages 80--112.
• 23: J. B. Nielsen (editor): Summary Report on Rational Cryptographic Protocols.ECRYPT Report D. PROVI.7, March 2007.
• 24: M.J. Osborne and A. Rubinstein. A Course in Game Theory,MIT Press, Cambridge, MA, 1994.
• 25: S. Peled, A. Yadin, and A. Yehudayoff,The maximal probability that k-wise independent bits are all 1.arXiv:math.PR/0801.0059.
• 26: 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.
• 27: R. Selten. A reexamination of the perfectness concept for equilibrium points in extensive games. International Journal of Game Theory 4, 1975. Pages 25--55.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

General Terms:
Economics, Theory

Keywords:
byzantine faults, large games, nash equilibrium