Hypergraph Coloring Games and Voter Models
Hypergraph Coloring Games and Voter Models
复制标题
超图着色游戏和选民模型
作者：
F. C. Graham;Alexander Tsiatas
摘要我们分析了一个基于超图的网络着色博弈，超图也可以描述一个投票者模型。每个节点代表一个投票者，并根据其首选候选人（或未定）进行着色。每个超边都是可以相互作用和影响的选民子集。在每一轮博弈中，随机选择一个超边，超边的投票者可以根据某种指定的概率分布改变他们的颜色。我们分析这个互动模型的基础上随机游走相关联的加权有向状态图。在一定的“无记忆”限制下，我们可以利用半群谱方法显式地确定状态图的谱，并且状态图上的随机游动在O（mlog n）步内收敛到其平稳分布，其中n是选民数，m是超边数.然后，我们可以通过模拟O（log（1/ε）mlog n）轮的投票游戏来估计事件发生在误差界ε内的概率。我们还考虑了一个部分无记忆的游戏，使用无记忆的游戏进行比较和分析，这是一个近似的实际互动动态。
Abstract We analyze a network coloring game on hypergraphs that 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 voters that can interact and influence one another. In each round of the game, one hyperedge is chosen randomly, and the voters in the hyperedge can change their colors according to some prescribed probability distribution. We analyze this interaction model based on random walks on the associated weighted directed state graph. Under certain “memoryless” restrictions, we can use semigroup spectral methods to explicitly determine the spectrum of the state graph, and the random walk on the state graph converges to its stationary distribution in O(mlog n) steps, where n is the number of voters and m the number of hyperedges. We can then estimate probabilities that events occur within an error bound of ε by simulating the voting game for O(log (1/ε)mlog n) rounds. We also consider a partially memoryless game using the memoryless game for comparison and analysis, which serves as an approximation of the actual interaction dynamics.