Decentralized dynamics for finite opinion games.

*(English)*Zbl 1284.91019
Serna, Maria (ed.), Algorithmic game theory. 5th international symposium, SAGT 2012, Barcelona, Spain, October 22–23, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-33995-0/pbk). Lecture Notes in Computer Science 7615, 144-155 (2012).

Summary: Game theory studies situations in which strategic players can modify the state of a given system, due to the absence of a central authority. Solution concepts, such as Nash equilibrium, are defined to predict the outcome of such situations. In the spirit of the field, we study the computation of solution concepts by means of decentralized dynamics. These are algorithms in which players move in turns to improve their own utility and the hope is that the system reaches an “equilibrium” quickly.

We study these dynamics for the class of opinion games, recently introduced by D. Bindel, J. Kleinberg and S. Oren [“How bad is forming your own opinion?”, in: 2011 IEEE 52nd annual symposium on foundations of computer science (FOCS). 57–66 (2011; doi:10.1109/FOCS.2011.43)]. 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 that the convergence to Nash equilibria is polynomial in the number of players. 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.

For the entire collection see [Zbl 1257.91003].

We study these dynamics for the class of opinion games, recently introduced by D. Bindel, J. Kleinberg and S. Oren [“How bad is forming your own opinion?”, in: 2011 IEEE 52nd annual symposium on foundations of computer science (FOCS). 57–66 (2011; doi:10.1109/FOCS.2011.43)]. 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 that the convergence to Nash equilibria is polynomial in the number of players. 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.

For the entire collection see [Zbl 1257.91003].