Fault tolerance in large games

Ronen Gradwohl*, Omer Reingold

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationEC'08 - Proceedings of the 2008 ACM Conference on Electronic Commerce
Pages274-283
Number of pages10
DOIs
StatePublished - Dec 1 2008
Event2008 ACM Conference on Electronic Commerce, EC'08 - Chicago, IL, United States
Duration: Jul 8 2008Jul 12 2008

Publication series

NameProceedings of the ACM Conference on Electronic Commerce

Other

Other2008 ACM Conference on Electronic Commerce, EC'08
CountryUnited States
CityChicago, IL
Period7/8/087/12/08

Keywords

  • Byzantine faults
  • Large games
  • Nash equilibrium

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Fault tolerance in large games'. Together they form a unique fingerprint.

Cite this