Decentralized Dynamics for Finite Opinion Games

Diodato Ferraioli, Paul W. Goldberg, Carmine Ventre

Research output: Contribution to journalArticleResearchpeer-review

19 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)-
JournalTheoretical Computer Science
DOIs
Publication statusPublished - 24 Aug 2016

Fingerprint

Decentralized
Solution Concepts
Game
Dynamic Response
Nash Equilibrium
Dynamic response
Convergence to Equilibrium
Mixing Time
Logit
Game theory
Game Theory
Markov processes
Social Networks
Upper and Lower Bounds
Markov chain
Vary
Economics
Decrease
Costs
Model

Cite this

Ferraioli, Diodato ; Goldberg, Paul W. ; Ventre, Carmine. / Decentralized Dynamics for Finite Opinion Games. In: Theoretical Computer Science. 2016 ; pp. -.
@article{dcea1b990caa453e99174d38045beb22,
title = "Decentralized Dynamics for Finite Opinion Games",
abstract = "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.",
author = "Diodato Ferraioli and Goldberg, {Paul W.} and Carmine Ventre",
year = "2016",
month = "8",
day = "24",
doi = "10.1016/j.tcs.2016.08.011",
language = "English",
pages = "--",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

Decentralized Dynamics for Finite Opinion Games. / Ferraioli, Diodato; Goldberg, Paul W.; Ventre, Carmine.

In: Theoretical Computer Science, 24.08.2016, p. -.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Decentralized Dynamics for Finite Opinion Games

AU - Ferraioli, Diodato

AU - Goldberg, Paul W.

AU - Ventre, Carmine

PY - 2016/8/24

Y1 - 2016/8/24

N2 - 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.

AB - 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.

U2 - 10.1016/j.tcs.2016.08.011

DO - 10.1016/j.tcs.2016.08.011

M3 - Article

SP - -

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -