Rational consensus (extended abstract)

DOI10.1145/2933057.2933088MaRDI QIDQ5361928zbMATH OpenOpenAlexFDO

Authors Joseph Y. Halpern, Xavier Vilaça

Publication date 29 September 2017

Published in Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.10141

zbMATH Keywords

consensuscrash failuresgame theory

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Applications of game theory (91A80)

Abstract: 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 emph{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 emph{ex post Nash Equilibrium}, even with only one failure. Roughly speaking, this means that there must always exist a emph{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 $pi$ on the failure patterns and initial preferences, then under minimal assumptions on $pi$, there is a Nash equilibrium that tolerates $f$ failures (i.e., $pi$ 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 emph{sequential} equilibrium (under the same assumptions about the distribution $pi$).

Recommendations

• Consensus Game: An Extension of Battle of the Sexes Game
• Consensus, communication and knowledge: an extension with Bayesian agents
• Distributed protocols for leader election: a game-theoretic perspective
• Byzantine agreement with a rational adversary
• Communication, consensus and order. Who wants to speak first?

Cited in

(7)

• De Finettian consensus
• Collective, universal, and joint rationality
• Deriving consensus in multiagent systems
• The consensus problem in the behavioral approach
• Perfectly secure message transmission against independent rational adversaries
• The role of a-priori information in networks of rational agents
• Consensus Game: An Extension of Battle of the Sexes Game

This page was built for publication: Rational consensus (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361928)