Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952531 | Theoretical Computer Science | 2016 | 20 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Diodato Ferraioli, Paul W. Goldberg, Carmine Ventre,