TY - GEN

T1 - Sampling from the Gibbs distribution in congestion games

AU - Kleer, Pieter

PY - 2021/7

Y1 - 2021/7

N2 - Logit dynamics is a form of randomized game dynamics where players have a bias towards strategic deviations that give a higher improvement in cost [3, 6]. It is used extensively in practice, but not well-understood from a theoretical perspective. In congestion (or potential) games [8], the dynamics converges to the so-called Gibbs distribution over the set of all strategy profiles, when interpreted as a Markov chain (see, e.g., [2]). In general, logit dynamics might converge slowly to the Gibbs distribution (i.e., the corresponding Markov chain is slowly mixing), but beyond that, not much is known about its algorithmic aspects, nor that of the Gibbs distribution.In this work, we are interested in the following two questions for congestion games:(1) Is there an efficient algorithm for sampling from the Gibbs distribution?(2) If yes, does there also exist natural randomized dynamics that converges quickly to the Gibbs distribution?These questions can be seen as dynamic analogues of two of the most important questions regarding the computation of Nash equilibria: i) Can a Nash equilibrium be computed efficiently? ii) If yes, does there also exist natural player dynamics (e.g., best response dynamics) quickly reaching a Nash equilibrium?

AB - Logit dynamics is a form of randomized game dynamics where players have a bias towards strategic deviations that give a higher improvement in cost [3, 6]. It is used extensively in practice, but not well-understood from a theoretical perspective. In congestion (or potential) games [8], the dynamics converges to the so-called Gibbs distribution over the set of all strategy profiles, when interpreted as a Markov chain (see, e.g., [2]). In general, logit dynamics might converge slowly to the Gibbs distribution (i.e., the corresponding Markov chain is slowly mixing), but beyond that, not much is known about its algorithmic aspects, nor that of the Gibbs distribution.In this work, we are interested in the following two questions for congestion games:(1) Is there an efficient algorithm for sampling from the Gibbs distribution?(2) If yes, does there also exist natural randomized dynamics that converges quickly to the Gibbs distribution?These questions can be seen as dynamic analogues of two of the most important questions regarding the computation of Nash equilibria: i) Can a Nash equilibrium be computed efficiently? ii) If yes, does there also exist natural player dynamics (e.g., best response dynamics) quickly reaching a Nash equilibrium?

KW - Gibbs distribution

KW - logit dynamics

KW - congestion games

KW - sampling

U2 - 10.1145/3465456.3467597

DO - 10.1145/3465456.3467597

M3 - Conference contribution

SN - 9781450385541

T3 - EC '21

SP - 679

EP - 680

BT - Proceedings of the 22nd ACM Conference on Economics and Computation

PB - Association for Computing Machinery

CY - New York, NY, USA

ER -