The robustness of democratic consensus

In linear models of consensus dynamics, the state of the various agents converges to a value which is a convex combination of the agents' initial states. We call it democratic if in the large scale limit (number of agents going to infinity) the vector of convex weights converges to 0 uniformly. Democracy is a relevant property which naturally shows up when we deal with opinion dynamic models and cooperative algorithms such as consensus over a network: it says that each agent's measure/opinion is going to play a negligible role in the asymptotic behavior of the global system. It can be seen as a relaxation of average consensus, where all agents have exactly the same weight in the final value, which becomes negligible for a large number of agents. We prove that starting from consensus models described by time-reversible stochastic matrices, under some mild technical assumptions, democracy is preserved when we perturb the linear dynamics in finitely many vertices. We want to stress that the local perturbation in general breaks the time-reversibility of the stochastic matrices. The main technical assumption needed in our result is the irreducibility of the large scale limit stochastic matrix, i.e. strong connectedness of the limit network of agents, and we show with an example that this assumption is indeed required. (C) 2014 Elsevier Ltd. All rights reserved.