演講公告

演講主題：Graph coloring games and voter models
主講人：金芳蓉院士 ( University of California, San Diego, USA)
演講日期：2014年07月10日（星期四）11:10-12:00
演講地點：中山大學理學院四樓理SC 4009-1室
摘要內容：
We investigate certain random processes on graphs which are related to the so-called Tsetlin library random walks as well as to some variants of classical voter model. A specific example can be described as a hypergraph coloring game. 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. In each round of the game, one chat group is chosen randomly, and voters in the group can change colors based on interactions. We analyze the game as a random walk on the associated weighted directed state graph. Under certain `memoryless' conditions, the spectrum of the state graph can be explicitly determined by using semigroup spectral theory. It can be shown that 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. We also consider a partial memoryless version which can be used to approximate general voter games.
This is based on joint papers with Ron Graham and Alex Tsiatas.

$返回$ go back