Voting protocols on the star graph

DOI10.1007/S44146-024-00125-XMaRDI QIDQ6548057zbMATH OpenFDO

Authors Kamilla Kátai-Urbán, András Pongrácz, Csaba Szabó

Publication date 31 May 2024

Published in Acta Scientiarum Mathematicarum (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S44146-024-00125-X

zbMATH Keywords

discordant votingpullpushstar graph

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Evolutionary games (91A22)

Review text

The authors considered a finite graph together with an initial assignment, which represents the opinion of each vertex. The paper provides procedures for deriving asymptotically sharp results for the worst expected runtime. The results generated 3 lemmas and 2 theorems.

Recommendations

• Discordant voting protocols for cyclically linked agents
• Discordant voting processes on finite graphs
• Quasi-majority functional voting on expander graphs
• Coalescing random walks and voting on graphs
• Fast plurality consensus in regular expanders

Cites work

• A survey of gossiping and broadcasting in communication networks
• Coalescing random walks and voting on connected graphs
• Discordant voting protocols for cyclically linked agents
• Distributed probabilistic polling and applications to proportionate agreement
• Evolving voter model on dense random graphs
• Finite particle systems and infection models
• Graph fission in an evolving voter model
• scientific article; zbMATH DE number 3934150 (Why is no real title available?)
• Mean field conditions for coalescing random walks
• On the coalescence time of reversible random walks
• The Linear Voting Model

Cited in

(1)

• On asymptotic fairness in voting with greedy sampling

This page was built for publication: Voting protocols on the star graph

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