Voting Models on Graphs

Student thesis: Doctoral ThesisDoctor of Philosophy

Abstract

This thesis deals with voting processes. A Voting process models the exchange of opinions in a population of agents, commonly represented by vertices of a graph. Usually, an opinion represents the current state of the agent, and by interacting with neighbouring agents, such an opinion may change over time.
Depending on the context, the set of valid opinions can be, for instance, {0, 1},{+, −}, {agree, disagree}, and {healthy, infected} among others. The main research questions about a voting process are: i) Does the system reach consensus?, that is, if the system reaches a stable configuration where all vertices share the same opinion. ii) Subject to reaching consensus, what is the final opinion of the system? iii) How long does it take to reach consensus?
Throughout this thesis, we study three stochastic models of voting. Firstly, we introduce and study the Linear Voting model. The main motivation to introduce this model is to make a step toward unifying certain models of voting on graphs in a common framework. In this regard, our model is proven to be flexible enough to cover several other models as particular instances without compromising tractability. As a particular case, our model subsumes well-known models as the voter model (pull voting) and push voting. Moreover, due to its tractability, we are able to extend several of the well-known techniques used to study pull voting, to properties of this much richer model. Among the studied properties, we include consensus time, winning probabilities, and the construction of a dual process.
Secondly, we analyse the Coalescing and Branching random walks (COBRA) pro-
cess, which is a model of rumour spreading on a connected graph. Here, we establish a duality relation between the COBRA process and an infection process called BIPS. The BIPS process can be seen as a voting model with bias toward a fix opinion. The advantage of our approach, is that the BIPS process is much more tractable than the original COBRA process. By using this dual process, we obtain several results concerting the cover time of the Cobra process, which corresponds to the first time such that all vertices are informed.
Finally, we study three versions of discordant voting processes on graphs. In discordant voting, only vertices with different opinions are allowed to interact. In first place, we study discordant voting processes on several classes of graphs, showing that the expected consensus time can be polynomial in the number of vertices of the graph, or exponential, depending on the graph topology. Later, we define a general discordant process, parametrised in β ∈ [0, 1], and study it on the complete graph. We compute the expected consensus time for all values of β, showing that several phase transitions occur as β moves from 0 to 1. Indeed, the expected consensus time is Θ(n log n) when β = 0, Θ(n2) when β = 1/2, and Θ(2n) when β = 1.
Date of Award2018
Original languageEnglish
Awarding Institution
  • King's College London
SupervisorTomasz Radzik (Supervisor) & Colin Cooper (Supervisor)

Cite this

'