Document Open Access Logo

The Linear Voting Model

Authors Colin Cooper, Nicolás Rivera

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.144.pdf
  • Filesize: 443 kB
  • 12 pages

Document Identifiers

Author Details

Colin Cooper
Nicolás Rivera

Cite As Get BibTex

Colin Cooper and Nicolás Rivera. The Linear Voting Model. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 144:1-144:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.144

Abstract

We study voting models on graphs. In the beginning, the vertices of a given graph have some initial opinion. Over time, the opinions on the vertices change by interactions between graph neighbours. Under suitable conditions the system evolves to a state in which all vertices have the same opinion. In this work, we consider a new model of voting, called the Linear Voting Model. This model can be seen as a generalization of several models of voting, including among others, pull voting and push voting. One advantage of our model is that, even though it is very general, it has a rich structure making the analysis tractable. In particular we are able to solve the basic question about voting, the probability that certain opinion wins the poll, and furthermore, given appropriate conditions, we are able to bound the expected time until some opinion wins.

Subject Classification

Keywords
  • Voter model
  • Interacting particles
  • Randomized algorithm
  • Probabilistic voting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, and Frederik Mallmann-Trenn. Bounds on the voter model in dynamic networks. arXiv preprint arXiv:1603.01895, 2016. Google Scholar
  2. Colin Cooper, Robert Elsasser, Hirotaka Ono, and Tomasz Radzik. Coalescing random walks and voting on connected graphs. SIAM Journal on Discrete Mathematics, 27(4):1748-1758, 2013. Google Scholar
  3. Josep Díaz, Leslie Ann Goldberg, George B Mertzios, David Richerby, Maria Serna, and Paul G Spirakis. Approximating fixation probabilities in the generalized moran process. Algorithmica, 69(1):78-91, 2014. Google Scholar
  4. Peter Donnelly and Dominic Welsh. Finite particle systems and infection models. Mathematical Proceedings of the Cambridge Philosophical Society, 94(01):167-182, 1983. Google Scholar
  5. Rick Durrett. Probability: theory and examples. Cambridge university press, 2010. Google Scholar
  6. Yehuda Hassin and David Peleg. Distributed probabilistic polling and applications to proportionate agreement. Information and Computation, 171(2):248-268, 2001. Google Scholar
  7. David Asher Levin, Yuval Peres, and Elizabeth Lee Wilmer. Markov chains and mixing times. AMS Bookstore, 2009. Google Scholar
  8. Toshio Nakata, Hiroshi Imahayashi, and Masafumi Yamashita. Probabilistic local majority voting for the agreement problem on finite graphs. In Computing and Combinatorics, pages 330-338. Springer, 1999. Google Scholar
  9. Roberto Oliveira. On the coalescence time of reversible random walks. Transactions of the American Mathematical Society, 364(4):2109-2128, 2012. Google Scholar
  10. Roberto Oliveira. Mean field conditions for coalescing random walks. The Annals of Probability, 41(5):3420-3461, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact