An Algorithm for Computing Stochastically Stable Distributions with Applications to Multiagent Learning in Repeated Games
John Wicks, Amy Greenwald
One of the proposed solutions to the equilibrium selection problem for agents learning in repeated games is obtained via the notion of stochastic stability. Learning algorithms are perturbed so that the Markov chain underlying the learning dynamics is necessarily irreducible and yields a unique stable distribution. The stochastically stable distribution is the limit of these stable distributions as the perturbation rate tends to zero. We present the first exact algorithm for computing the stochastically stable distribution of a Markov chain. We use our algorithm to predict the long-term dynamics of simple learning algorithms in sample repeated games.
PDF Link: /papers/05/p623-wicks.pdf
AUTHOR = "John Wicks
and Amy Greenwald",
TITLE = "An Algorithm for Computing Stochastically Stable Distributions with Applications to Multiagent Learning in Repeated Games",
BOOKTITLE = "Proceedings of the Twenty-First Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-05)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2005",
PAGES = "623--632"