2024/09/19 by Colin Cooper, Cooper, Colin, Tomasz Radzik +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Game Theory and Voting Systems #Internet Traffic Analysis and Secure E-voting
paper · pdf · doi:10.48550/arxiv.2409.12615
openalex publication_date 2024/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Pull voting is a random process in which vertices of a connected graph have initial opinions chosen from a set of k distinct opinions, and at each step a random vertex alters its opinion to that of a randomly chosen neighbour. If the system reaches a state where each vertex holds the same opinion, then this opinion will persist forthwith. In general the opinions are regarded as incommensurate, whereas in this paper we consider a type of pull voting suitable for integer opinions such as \1,2,…,k\ which can be compared on a linear scale; for example, 1 ('disagree strongly'), 2 ('disagree'), …, 5 ('agree strongly'). On observing the opinion of a random neighbour, a vertex updates its opinion by a discrete change towards the value of the neighbour's opinion, if different. Discrete incremental voting is a pull voting process which mimics this behaviour. At each step a random vertex alters its opinion towards that of a randomly chosen neighbour; increasing its opinion by +1 if the opinion of the chosen neighbour is larger, or decreasing its opinion by -1, if the opinion of the neighbour is smaller. If initially there are only two adjacent integer opinions, for example \0,1\, incremental voting coincides with pull voting, but if initially there are more than two opinions this is not the case. For an n-vertex graph G=(V,E), let λ be the absolute second eigenvalue of the transition matrix P of a simple random walk on G. Let the initial opinions of the vertices be chosen from \1,2,…,k\. Let c=∑v ∈ V πv Xv, where Xv is the initial opinion of vertex v, and πv is the stationary distribution of the vertex. Then provided λk=o(1) and k=o(n/log n), with high probability the final opinion is the initial weighted average c suitably rounded to \lfloor c \rfloor or \lceil c\rceil.