The Price of Uncertainty for Social Consensus
For researchers in social network analysis and distributed consensus, this work provides a rigorous theoretical framework quantifying the negative impact of uncertainty, though it is an incremental extension of prior work by Balcan et al.
The paper studies how uncertainty in neighbor color counts affects consensus in social networks, proving that even small perturbations (1+ε) greatly hinder consensus, with tight theoretical bounds on the price of uncertainty.
How hard is it to achieve consensus in a social network under uncertainty? In this paper we model this problem as a social graph of agents where each vertex is initially colored red or blue. The goal of the agents is to achieve consensus, which is when the colors of all agents align. Agents attempt to do this locally through steps in which an agent changes their color to the color of the majority of their neighbors. In real life, agents may not know exactly how many of their neighbors are red or blue, which introduces uncertainty into this process. Modeling uncertainty as perturbations of relative magnitude $1+\varepsilon$ to these color neighbor counts, we show that even small values of $\varepsilon$ greatly hinder the ability to achieve consensus in a social network. We prove theoretically tight upper and lower bounds on the \emph{price of uncertainty}, a metric defined in previous work by Balcan et al. to quantify the effect of uncertainty in network games.