This paper is concerned with voting processes on graphs where each vertex holds one of two different opinions. In particular, we study the and the . Here at each synchronous and discrete time step, each vertex updates its opinion to match the majority among the opinions of two random neighbors and itself (the Best-of-two) or the opinions of three random neighbors (the Best-of-three). Previous studies have explored these processes on complete graphs and expander graphs, but we understand significantly less about their properties on graphs with more complicated structures. In this paper, we study the Best-of-two and the Best-of-three on the stochastic block model @math , which is a random graph consisting of two distinct Erdős-Renyi graphs @math joined by random edges with density @math . We obtain two main results. First, if @math and @math is a constant, we show that there is a phase transition in @math with threshold @math (specifically, @math for the Best-of-two, and @math for the Best-of-three). If @math , the process reaches consensus within @math steps for any initial opinion configuration with a bias of @math . By contrast, if @math , we show that, for any initial opinion configuration, the process reaches consensus within @math steps. To the best of our knowledge, this is the first result concerning multiple-choice voting for arbitrary initial opinion configurations on non-complete graphs.
Other studies have focused on voting processes with more general updating rules. Cooper and Rivera @cite_5 studied the linear voting model , whose updating rule is characterized by a set of @math binary matrices. This model covers the synchronous pull and the asynchronous push pull voting processes. However, it does not cover the Best-of-two and the Best-of-three. Schoenebeck and Yu @cite_0 studied asynchronous voting processes whose updating functions are majority-like (including the asynchronous Best-of- @math voting processes). They gave upper bounds on the consensus times of such models on dense Erd o s-R 'enyi random graphs using a potential technique.
@cite_0 @cite_5
2589531210 2533034710
We study consensus processes on the complete graph of n nodes. Initially, each node supports one up to n different opinions. Nodes randomly and in parallel sample the opinions of constantly many nodes. Based on these samples, they use an update rule to change their own opinion. The goal is to reach consensus, a configuration where all nodes support the same opinion. We compare two well-known update rules: 2-Choices and 3-Majority. In the former, each node samples two nodes and adopts their opinion if they agree. In the latter, each node samples three nodes: If an opinion is supported by at least two samples the node adopts it, otherwise it randomly adopts one of the sampled opinions. Known results for these update rules focus on initial configurations with a limited number of colors (say n1 3), or typically assume a bias, where one opinion has a much larger support than any other. For such biased configurations, the time to reach consensus is roughly the same for 2-Choices and 3-Majority. Interestingly, we prove that this is no longer true for configurations with a large number of initial colors. In particular, we show that 3-Majority reaches consensus with high probability in O(n3 4 · log7 8 n) rounds, while 2-Choices can need Ω(n log n) rounds. We thus get the first unconditional sublinear bound for 3-Majority and the first result separating the consensus time of these processes. Along the way, we develop a framework that allows a fine-grained comparison between consensus processes from a specific class. We believe that this framework might help to classify the performance of more consensus processes. 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.