License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.144
URN: urn:nbn:de:0030-drops-62883
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6288/
Go to the corresponding LIPIcs Volume Portal

Cooper, Colin ; Rivera, Nicolás

The Linear Voting Model

pdf-format:
LIPIcs-ICALP-2016-144.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{cooper_et_al:LIPIcs:2016:6288,
  author =	{Colin Cooper and Nicol{\'a}s Rivera},
  title =	{{The Linear Voting Model}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{144:1--144:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6288},
  URN =		{urn:nbn:de:0030-drops-62883},
  doi =		{10.4230/LIPIcs.ICALP.2016.144},
  annote =	{Keywords: Voter model, Interacting particles, Randomized algorithm, Probabilistic voting}
}

Keywords: Voter model, Interacting particles, Randomized algorithm, Probabilistic voting
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI