← 研踪 PaperTrailarXiv:2611.16037 · v1
Plurality Consensus for $h$-Majority via First-Repetition Rules
首次提交 2026-11-12 05:46
版本更新 2026-11-12 05:46
雷达观测 2026-11-13 14:16
摘要
In the h-Majority dynamics, each of n agents holds one of k opinions and, in every synchronous round, observes the opinions of h agents chosen independently and uniformly at random and adopts a most frequent one among them, breaking ties uniformly at random. Let M_0 be the initial number of agents holding the most frequent opinion, and Delta_0 its bias, its lead over the second most frequent opinion. We show that, for every sample size h >= 3, if Delta_0 >= L sqrt(M_0 log n) max{1, n/(h^2 M_0)} for a sufficiently large constant L, then h-Majority reaches consensus on the initially most frequent opinion within O((1 + n/(h^2 M_0)) log n) rounds with high probability. This is the time bound proved for the DejaVu dynamics with h samples (arXiv:2604.03648); our bias condition is that of DejaVu when h >= sqrt(n/M_0), and larger by a factor sqrt(n/(h^2 M_0)) otherwise. Our main contribution, the analysis of one round, rests on a comparison principle: among all rules that read the same observations and treat opinions symmetrically, plurality maximizes the difference between the probability of outputting the most frequent opinion and that of outputting any fixed competitor. We apply it to the rule that adopts the first opinion repeated among h-1 observations, and otherwise the h-th observation: its output law is the law of the new opinion of a random agent after one round of DejaVu with h-1 samples. Hence, in expectation, one round of h-Majority widens the gap between the most frequent opinion and each competitor at least as much as that round of DejaVu, whose analysis we use as a black box. Independently and concurrently, d'Amore, Rybicki, Shimizu, Shiraga and Vacus (arXiv:2610.40562) obtained, among other results, the same time bound under the weaker bias condition of DejaVu, with a different analysis of one round and a martingale analysis over many rounds.
作者备注：16 pages
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-12 05:46 · 最新观测版本
Plurality Consensus for $h$-Majority via First-Repetition Rules
In the h-Majority dynamics, each of n agents holds one of k opinions and, in every synchronous round, observes the opinions of h agents chosen independently and uniformly at random and adopts a most frequent one among them, breaking ties uniformly at random. Let M_0 be the initial number of agents holding the most frequent opinion, and Delta_0 its bias, its lead over the second most frequent opinion. We show that, for every sample size h >= 3, if Delta_0 >= L sqrt(M_0 log n) max{1, n/(h^2 M_0)} for a sufficiently large constant L, then h-Majority reaches consensus on the initially most frequent opinion within O((1 + n/(h^2 M_0)) log n) rounds with high probability. This is the time bound proved for the DejaVu dynamics with h samples (arXiv:2604.03648); our bias condition is that of DejaVu when h >= sqrt(n/M_0), and larger by a factor sqrt(n/(h^2 M_0)) otherwise. Our main contribution, the analysis of one round, rests on a comparison principle: among all rules that read the same observations and treat opinions symmetrically, plurality maximizes the difference between the probability of outputting the most frequent opinion and that of outputting any fixed competitor. We apply it to the rule that adopts the first opinion repeated among h-1 observations, and otherwise the h-th observation: its output law is the law of the new opinion of a random agent after one round of DejaVu with h-1 samples. Hence, in expectation, one round of h-Majority widens the gap between the most frequent opinion and each competitor at least as much as that round of DejaVu, whose analysis we use as a black box. Independently and concurrently, d'Amore, Rybicki, Shimizu, Shiraga and Vacus (arXiv:2610.40562) obtained, among other results, the same time bound under the weaker bias condition of DejaVu, with a different analysis of one round and a martingale analysis over many rounds.
查看此版本解读 →查看此版本原文 ↗