2020/05/20 by Joseph Y. Halpern, Halpern, Joseph Y., Xavier Vilaça +2
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Physics and Astronomy · #Computer Science and Game Theory (cs.GT) #Distributed #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #Opinion Dynamics and Social Influence #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.GT
paper · pdf · doi:10.48550/arxiv.2005.10141
Appears in Proceedings of the 35th Annual ACM Symposium on Principles of Distributed Computing, 2016
arxiv created 2020/05/20 · openalex publication_date 2020/05/20 · arxiv updated 2020/05/21 · openalex created_date 2024/04/10 · openalex updated_date 2026/07/28
We provide a game-theoretic analysis of consensus, assuming that processes are controlled by rational agents and may fail by crashing. We consider agents that care only about consensus: that is, (a) an agent's utility depends only on the consensus value achieved (and not, for example, on the number of messages the agent sends) and (b) agents strictly prefer reaching consensus to not reaching consensus. We show that, under these assumptions, there is no ex post Nash Equilibrium, even with only one failure. Roughly speaking, this means that there must always exist a failure pattern (a description of who fails, when they fail, and which agents they do not send messages to in the round that they fail) and initial preferences for which an agent can gain by deviating. On the other hand, if we assume that there is a distribution π on the failure patterns and initial preferences, then under minimal assumptions on π, there is a Nash equilibrium that tolerates f failures (i.e., π puts probability 1 on there being at most f failures) if f+1 < n (where n is the total number of agents). Moreover, we show that a slight extension of the Nash equilibrium strategy is also a sequential equilibrium (under the same assumptions about the distribution π).