Abstract: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 price of uncertainty, a metric defined in previous work by Balcan et al. to quantify the effect of uncertainty in network games.
From: Alec Sun [view email]
[v1]
Sun, 24 Aug 2025 23:48:37 UTC (16 KB)
[v2]
Wed, 8 Oct 2025 22:54:20 UTC (20 KB)
[v3]
Thu, 29 Jan 2026 07:43:19 UTC (20 KB)
[v4]
Mon, 4 May 2026 20:57:25 UTC (20 KB)
[v5]
Wed, 1 Jul 2026 19:13:10 UTC (22 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。