Randomness and Metastability in Game Theory and Distributed Computing

Abstract

Game theory provides a powerful framework to study strategic interactions
among agents of a system. The assumption about the “rationality” of
the agents is at the heart of classical solution concepts like Nash equilibria.
However, in several scenarios those solution concepts often fall short
of expectations when used to make predictions. The Logit dynamics is a
model for strategic interactions among players with limited rationality; it is
inspired by statistical mechanics and uses “randomness” to model the uncertainty
about the rationality level of the agents.
In the first part of this paper we will sum up our research program on
the Logit dynamics for strategic games, in which we proposed to consider
the unique stationary distribution of the induced ergodic Markov chain as the
long-term solution concept for the game, we analyzed the mixing time of the
chains for some classes of games, and we defined the concept of metastable
probability distribution for Markov chains with exponential mixing time.
The usefulness of reasoning about “metastability” goes beyond the realm
of game theory and Markov chains. In the second part of the paper, we will
discuss part of a recent work where the analysis of the metastable phase of
a simple dynamics allowed us to come up with an ecient fully-distributed
algorithm for the community detection problem.