Consensus in Equilibrium: Can One Against All Decide Fairly?

About the Project

Joint work with Tel-Aviv University students Itay HarelAmit Jacob Fanani, and Moshe Sulamy.
Is there an equilibrium for distributed consensus when all agents except one collude to steer the decision value towards their preference? If an equilibrium exists, then an n-1 size coalition cannot do better by deviating from the algorithm, even if it prefers a different decision value. We show that an equilibrium exists under this condition only if the number of agents in the network is odd and the decision is binary (among two possible input values). That is, in this framework we provide a separation between binary and multi-valued consensus. Moreover, the input and output distribution must be uniform, regardless of the communication model (synchronous or asynchronous).
Itay HarelAmit Jacob FananiMoshe Sulamy, Yehuda Afek:
Consensus in Equilibrium: Can One Against All Decide Fairly? OPODIS 2019: 20:1-20:17 

Project Details