We analyze a network coloring game which can also describe a voter model. Each node represents a voter and is colored according to its
preferred candidate, or undecided. Each hyperedge is a subset of nodes and can be viewed as a chat group. We consider interaction-based strategies involving chat groups: in each round of the game, one chat group is chosen randomly, and voters in the group can change colors
based on informed discussion. We analyze the game as a random walk on the associated
weighted directed state graph. Under certain `memoryless' conditions on the interaction
strategies, the spectrum of the state graph can be explicitly determined and the random walk on the state graph converges to its stationary distribution in $O(m \log n)$ time,
where $n$ denotes the number of voters and $m$ denotes the number of chat groups.
This can then be used to determine the appropriate cut-off time for voting. For
example, we show that the problem of estimating the probability that `blue' wins within an error bound of $\epsilon$ takes $O((\log 1/\epsilon) m \log n)$ rounds, provided the interaction strategies are memoryless.
This is a joint work with Alex Tsiatas and based on previous work with
Ron Graham.
Copyright. All Rights Reserved.