Brief Announcement: Discrete Incremental Voting

DOI10.1145/3583668.3594582MaRDI QIDQ6202261zbMATH OpenOpenAlexFDO

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)

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)

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.

Cites work

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

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)