Fault tolerance in large games |
| |
| Institution: | 1. Kellogg School of Management, Northwestern University, 2001 Sheridan Road, Evanston, IL 60208, United States;2. Microsoft Research Silicon Valley, 1065 La Avenida, Mountain View, CA, 94043, United States;3. The Weizmann Institute of Science, Rehovot 76100, Israel;1. Center of Economic Research at ETH Zürich (CER-ETH), Switzerland;2. Department of Economics, Maastricht University, Netherlands;1. Google Research, 111 8th Avenue, New York, NY 10011, United States;2. Computer Science Department, Cornell University, Ithaca, NY 14853, United States;1. Guanghua School of Management, Peking University, Beijing, China;2. University of Pittsburgh, United States;1. Singapore Management University, Singapore;2. Indian Statistical Institute, New Delhi, India |
| |
| 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: | Nash equilibrium Large games Fault tolerance |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
