Fair Leader Election among Selfish Agents

The rational fair consensus problem can be informally defined as follows. Consider a network of n (selfish) rational agents, each of them initially supporting a color chosen from a finite set ?. The goal is to design a protocol that leads the network to a stable monochromatic configuration (i.e. a consensus) such that the probability that the winning color is c is equal to the fraction of the agents that initially support c, for any c in ?. Furthermore, this fairness property must be guaranteed (with high probability) even in presence of any fixed coalition of rational agents that may deviate from the protocol in order to increase the winning probability of their supported colors. A protocol having this property, in presence of coalitions of size at most t, is said to be a whp-t-strong equilibrium. We investigate, for the first time, the rational fair consensus problem in the GOSSIP communication model where, at every round, every agent can exchange a message of polylogarithmic size with only one neighbor using push/pull operations. We provide a randomized GOSSIP protocol that, starting from any initial color configuration of the complete graph, achieves rational fair consensus within O(log n) rounds using messages of O(log^2 n) size, w.h.p. More in details, we prove that our protocol is a whp-t-strong equilibrium for any t = o(n/log n) and, moreover, it tolerates worst-case permanent faults provided that the number of non-faulty agents is Ohm(n). As far as we know, our protocol is the first solution which avoids any all-to-all communication, thus resulting in o(n^2) message complexity.