Speaker: Colin Cooper (King's College London)

Title: Models of discrete random voting on graphs

Abstract:A simple model of voting on connected graphs is as follows: The voting proceeds in rounds. Initially each vertex has a distinct opinion. In each round each vertex contacts a randomly chosen neighbour and adopts their opinion. We call this model single-sample voting. The quantities of interest are the time for voting to complete, and the probability a particular opinion wins. Examples include: Single-sample voting. The relationship between single-sample voting and coalescing random walks. These processes are dual and we can use random walks to analyze the performance of voting. Using this, we give an upper bound for the expected time for voting to complete on general connected graphs. Two-party voting. In two-party voting, each vertex initially holds one of two opinions (e.g. 0 or 1). We discuss the speed-up in two-party voting when the opinion of one or more neighbour is sampled at each step. We give results for two-party voting on regular expanders when we sample two or more opinions. Compared to single-sample voting, this process is more consistent (democratic) and finishes much quicker.