id: 06070179
dt: a
an: 06070179
au: Persiano, Giuseppe
ti: Stability and metastability of the logit dynamics of strategic games.
so: Kranakis, Evangelos (ed.) et al., Fun with algorithms. 6th international
    conference, FUN 2012, Venice, Italy, June 4‒6, 2012. Proceedings.
    Berlin: Springer (ISBN 978-3-642-30346-3/pbk). Lecture Notes in
    Computer Science 7288, 2 (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-30347-0_2
ab: Summary: We consider large systems composed of stategic players and look at
    ways of describing their long term behaviour. We give evidence that the
    notion of a Nash equilibrium is not a completely satisfactory answer to
    this question and propose to look at the stationary equilibrium induced
    by the logit dynamics [4]. Here at every stage of the game a player is
    selected uniformly at random and she plays according to a noisy
    best-response dynamics where the noise level is tuned by a parameter
    $β$. Such a dynamics defines a family of ergodic Markov chains,
    indexed by $β$, over the set of strategy profiles. Being ergodic, the
    induced Markov chain admits a unique stationary distribution and, for
    any possible initial state, the chain approaches the stationary
    distribution. For games for which the mixing time is polynomial in the
    number of players, the stationary distribution can be taken as
    descriptive of the behaviour of system (having to discount only the
    short transient initial period). We show that for ptential games, the
    mixing time is related to properties of the potential landscape. For
    games for which the mixing time is super-polynomial, the system will
    spend to much time out of equilibrium and thus we look at metastable
    distributions for such systems. Joint work with: Vincenzo Auletta,
    Diodato Ferraioli, Francesco Pasquale and Paolo Penna [2,1,3].
rv: