max planck institut
informatik

# MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Rational Fair Consensus in the GOSSIP Model Giacomo Scornavacca University of L'Aquila AG1 Mittagsseminar (own work) D1We use this to send out email in the morning. AG Audience English
Date: Tuesday, 12 September 2017 13:00 30 Minutes Saarbrücken E1 4 024
 The \emph{rational fair consensus problem} can be informally defined as follows. Consider a network of $n$ (selfish) \emph{rational agents}, each of them initially supporting a \emph{color} chosen from a finite set $\Sigma$. 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 \Sigma$. Furthermore, this fairness property must be guaranteed (with high probability) even in presence of any fixed \emph{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 \emph{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 actively contact at most one neighbor via a \emph{push$/$pull} operation. 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^2n)$ 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 $\Omega(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.
Name(s): Emanuele Natale