TY - JOUR
T1 - Revisiting log-linear learning
T2 - Asynchrony, completeness and payoff-based implementation
AU - Marden, Jason R.
AU - Shamma, Jeff S.
N1 - ✩ Research supported by the Social and Information Sciences Laboratory at the California Institute of Technology, AFOSR grants #FA9550-09-1-0538, #FA9550-08-1-0375 and #FA9550-05-1-0321, and NSF grant #ECS-0501394. * Corresponding author. E-mail addresses: [email protected] (J.R. Marden), [email protected] (J.S. Shamma).
PY - 2012/7
Y1 - 2012/7
N2 - Log-linear learning is a learning algorithm that provides guarantees on the percentage of time that the action profile will be at a potential maximizer in potential games. The traditional analysis of log-linear learning focuses on explicitly computing the stationary distribution and hence requires a highly structured environment. Since the appeal of log-linear learning is not solely the explicit form of the stationary distribution, we seek to address to what degree one can relax the structural assumptions while maintaining that only potential function maximizers are stochastically stable. In this paper, we introduce slight variants of log-linear learning that provide the desired asymptotic guarantees while relaxing the structural assumptions to include synchronous updates, time-varying action sets, and limitations in information available to the players. The motivation for these relaxations stems from the applicability of log-linear learning to the control of multi-agent systems where these structural assumptions are unrealistic from an implementation perspective.
AB - Log-linear learning is a learning algorithm that provides guarantees on the percentage of time that the action profile will be at a potential maximizer in potential games. The traditional analysis of log-linear learning focuses on explicitly computing the stationary distribution and hence requires a highly structured environment. Since the appeal of log-linear learning is not solely the explicit form of the stationary distribution, we seek to address to what degree one can relax the structural assumptions while maintaining that only potential function maximizers are stochastically stable. In this paper, we introduce slight variants of log-linear learning that provide the desired asymptotic guarantees while relaxing the structural assumptions to include synchronous updates, time-varying action sets, and limitations in information available to the players. The motivation for these relaxations stems from the applicability of log-linear learning to the control of multi-agent systems where these structural assumptions are unrealistic from an implementation perspective.
KW - Distributed control
KW - Equilibrium selection
KW - Potential games
UR - http://www.scopus.com/inward/record.url?scp=84860623901&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84860623901&partnerID=8YFLogxK
U2 - 10.1016/j.geb.2012.03.006
DO - 10.1016/j.geb.2012.03.006
M3 - Article
AN - SCOPUS:84860623901
SN - 0899-8256
VL - 75
SP - 788
EP - 808
JO - Games and Economic Behavior
JF - Games and Economic Behavior
IS - 2
ER -