Paper 2010/330

Distributed Rational Consensus

Amjed Shareef

Abstract

The \textit{consensus} is a very important problem in distributed computing, where among the $n$ players, the honest players try to come to an agreement even in the presence of $t$ malicious players. In game theoretic environment, \textit{the group choice problem} is similar to the \textit{rational consensus problem}, where every player $p_i$ prefers come to consensus on his value $v_i$ or to a value which is as close to it as possible. All the players need to come to an agreement on one value by amalgamating individual preferences to form a group or social choice. In rational consensus problem, there are no malicious players. We consider the rational consensus problem in the presence of few malicious players. The players are assumed to be rational rather than honest and there exist few malicious players among them. Every rational player primarily prefers to come to consensus on his value and secondarily, prefers to come to consensus on other player's value. In other words, if $w_1$, $w_2$ and $w_3$ are the payoffs obtained when $p_i$ comes to consensus on his value, $p_i$ comes to consensus on other's value and $p_i$ does not come to consensus respectively, then $w_1 > w_2 > w_3$. We name it as \textit{distributed rational consensus problem} DRC. The players can have two values, either 1 or 0, i.e binary consensus. The rational majority is defined as number of players, who wants to agree on one particular value, and they are more than half of the rational players. Similarly rational minority can be defined. We have considered EIG protocol, and characterized the rational behaviour, and shown that EIG protocol will not work in rational environment. We have proved that, there exists no protocol, which solves distributed consensus problem in fixed running time, where players have knowledge of other players values during the protocol. This proof is based on Maskin's monotonicity property. The good news is, if the players do not have knowledge about other players values, then it can be solved. This can be achieved by verifiable rational secret sharing, where players do not exchange their values directly, but as pieces of it.