Decentralized dynamics for finite opinion games
Decentralized dynamics for finite opinion games
复制标题
DOI：
10.1016/j.tcs.2016.08.011
复制
发表时间：
2016-10-04
影响因子：
1.1
通讯作者：
Ventre, Carmine
中科院分区：
文献类型：
--
作者：
Ferraioli, Diodato;Goldberg, Paul W.;Ventre, Carmine
博弈论研究在没有中央权威的情况下，战略参与者可以修改给定系统状态的情况。定义解决方案概念（例如纳什均衡）是为了预测此类情况的结果。在多人游戏设置中，有人指出，为了现实，解决方案概念应该通过分散且相当简单的流程来获得。因此，我们通过分散动态来研究解决方案概念的计算。在这些算法中，玩家轮流移动以降低自己的成本，希望系统能够快速达到“平衡”。我们研究 Bindel 等人最近提出的意见博弈类的这些动态。 [10]。这些游戏在经济学和社会学中很重要，它们模拟了社交网络中意见的形成。我们研究最佳响应动态并显示收敛到纳什均衡的上限和下限。我们还研究了最佳响应动力学的噪声版本，称为 Logit 动力学，并证明了随着系统噪声变化其收敛速度的一系列结果。为了获得这些结果，我们使用了多种技术来限制马尔可夫链的混合时间，包括耦合、频谱特征和瓶颈比。 (C) 2016 Elsevier B.V. 保留所有权利。
Game theory studies situations in which strategic players can modify the state of a given system, in the absence of a central authority. Solution concepts, such as Nash equilibrium, have been defined in order to predict the outcome of such situations. In multi player settings, it has been pointed out that to be realistic, a solution concept should be obtainable via processes that are decentralized and reasonably simple. Accordingly we look at the computation of solution concepts by means of decentralized dynamics. These are algorithms in which players move in turns to decrease their own cost and the hope is that the system reaches an "equilibrium" quickly.We study these dynamics for the class of opinion games, recently introduced by Bindel et al. [10]. These are games, important in economics and sociology, that model the formation of an opinion in a social network. We study best-response dynamics and show upper and lower bounds on the convergence to Nash equilibria. We also study a noisy version of best-response dynamics, called logit dynamics, and prove a host of results about its convergence rate as the noise in the system varies. To get these results, we use a variety of techniques developed to bound the mixing time of Markov chains, including coupling, spectral characterizations and bottleneck ratio. (C) 2016 Elsevier B.V. All rights reserved.