Fault tolerance in large games

• 成果类型: Article
• 署名作者: Gradwohl, Ronen; Reingold, Omer
• 署名单位: Northwestern University; Microsoft; Weizmann Institute of Science
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2013.06.007
• 发表日期: 2014
• 页码: 438-457
• 关键词: Nash equilibrium; Large games; Fault tolerance

摘要

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 - lambda-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. (C) 2013 Elsevier Inc. All rights reserved.