Fault tolerance in large games

Ronen Gradwohl; Omer Reingold

doi:10.1016/j.geb.2013.06.007

Fault tolerance in large games

Ronen Gradwohl^*, Omer Reingold

^*Corresponding author for this work

Managerial Economics, Decision Sciences and Operations

Research output: Contribution to journal › Article › peer-review

18 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, 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.

Original language	English (US)
Pages (from-to)	438-457
Number of pages	20
Journal	Games and Economic Behavior
Volume	86
DOIs	https://doi.org/10.1016/j.geb.2013.06.007
State	Published - Jul 2014

Funding

This research was supported in part by grant 1300/05 from the Israel Science Foundation . The authors would also like to thank Ariel Yadin for helpful discussions throughout the course of this research, and the anonymous referees for their comments.

Keywords

Fault tolerance
Large games
Nash equilibrium

ASJC Scopus subject areas

Finance
Economics and Econometrics

Access to Document

10.1016/j.geb.2013.06.007

Cite this

@article{32045a05bbcb48e38c53f60e25e3e7bc,

title = "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, 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.",

keywords = "Fault tolerance, Large games, Nash equilibrium",

author = "Ronen Gradwohl and Omer Reingold",

note = "Funding Information: This research was supported in part by grant 1300/05 from the Israel Science Foundation . The authors would also like to thank Ariel Yadin for helpful discussions throughout the course of this research, and the anonymous referees for their comments. ",

year = "2014",

month = jul,

doi = "10.1016/j.geb.2013.06.007",

language = "English (US)",

volume = "86",

pages = "438--457",

journal = "Games and Economic Behavior",

issn = "0899-8256",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Fault tolerance in large games

AU - Gradwohl, Ronen

AU - Reingold, Omer

N1 - Funding Information: This research was supported in part by grant 1300/05 from the Israel Science Foundation . The authors would also like to thank Ariel Yadin for helpful discussions throughout the course of this research, and the anonymous referees for their comments.

PY - 2014/7

Y1 - 2014/7

N2 - 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.

AB - 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.

KW - Fault tolerance

KW - Large games

KW - Nash equilibrium

UR - http://www.scopus.com/inward/record.url?scp=84902087273&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902087273&partnerID=8YFLogxK

U2 - 10.1016/j.geb.2013.06.007

DO - 10.1016/j.geb.2013.06.007

M3 - Article

AN - SCOPUS:84902087273

SN - 0899-8256

VL - 86

SP - 438

EP - 457

JO - Games and Economic Behavior

JF - Games and Economic Behavior

ER -

Fault tolerance in large games

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this