Brief Announcement: Discrete Incremental Voting

DOI10.1145/3583668.3594582arXiv2305.15632OpenAlexW4380873876MaRDI QIDQ6202261FDOQ6202261

Authors: Colin Cooper, Tomasz Radzik, Takeharu Shiraga 

Publication date: 26 March 2024

Published in: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: We consider a type of pull voting suitable for discrete numeric opinions which can be compared on a linear scale, for example, 1 ('disagree strongly'), 2 ('disagree'), $ldots,$ 5 ('agree strongly'). On observing the opinion of a random neighbour, a vertex changes its opinion incrementally towards the value of the neighbour's opinion, if different. For opinions drawn from a set $1,2,ldots,k$, the opinion of the vertex would change by $+1$ if the opinion of the neighbour is larger, or by $-1$, if it is smaller. It is not clear how to predict the outcome of this process, but we observe that the total weight of the system, that is, the sum of the individual opinions of all vertices, is a martingale. This allows us analyse the outcome of the process on some classes of dense expanders such as clique graphs $K_n$ and random graphs $G_{n,p}$ for suitably large $p$. If the average of the original opinions satisfies $ileclei+1$ for some integer $i$, then the asymptotic probability that opinion $i$ wins is $i+1-c$, and the probability that opinion $i+1$ wins is $c-i$. With high probability, the winning opinion cannot be other than $i$ or $i+1$. To contrast this, we show that for a path and opinions $0,1,2$ arranged initially in non-decreasing order along the path, the outcome is very different. Any of the opinions can win with constant probability, provided that each of the two extreme opinions $0$ and $2$ is initially supported by a constant fraction of vertices.

Full work available at URL: https://arxiv.org/abs/2305.15632

zbMATH Keywords

pull votingrandom distributed processes

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• Coalescing random walks and voting on graphs
• Distributed probabilistic polling and applications to proportionate agreement
• Global majority consensus by local majority polling on graphs of a given degree sequence
• Title not available (Why is that?)
• The Power of Two Choices in Distributed Voting
• Plurality consensus in the gossip model
• Stabilizing Consensus with Many Opinions
• Nearly-tight analysis for 2-choice and 3-majority consensus dynamics
• Fast plurality consensus in regular expanders
• Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
• Tight bounds for coalescing-branching random walks on regular graphs
• Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models

This page was built for publication: Brief Announcement: Discrete Incremental Voting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202261)