Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
An Algorithm for Computing Stochastically Stable Distributions with Applications to Multiagent Learning in Repeated Games
John Wicks, Amy Greenwald
Abstract:
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.
Keywords:
Pages: 623-632
PS Link:
PDF Link: /papers/05/p623-wicks.pdf
BibTex:
@INPROCEEDINGS{Wicks05,
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"
}


hosted by DSL   •   site info   •   help