Sampling from the Gibbs distribution in congestion games

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


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?
Original languageEnglish
Title of host publicationProceedings of the 22nd ACM Conference on Economics and Computation
Place of PublicationNew York, NY, USA
PublisherAssociation for Computing Machinery
ISBN (Print)9781450385541
Publication statusPublished - Jul 2021

Publication series

NameEC '21
PublisherAssociation for Computing Machinery


  • Gibbs distribution
  • logit dynamics
  • congestion games
  • sampling


Dive into the research topics of 'Sampling from the Gibbs distribution in congestion games'. Together they form a unique fingerprint.

Cite this