## Hypergraph coloring games and memoryless voter models

#### Fan Chung-GrahamUniversity of California, San Diego (UCSD)Computer Science

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.

Back to Algorithmic Game Theory