Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos
G Palaiopanos, I Panageas… - Advances in Neural …, 2017 - proceedings.neurips.cc
Advances in Neural Information Processing Systems, 2017•proceedings.neurips.cc
Abstract The Multiplicative Weights Update (MWU) method is a ubiquitous meta-algorithm
that works as follows: A distribution is maintained on a certain set, and at each step the
probability assigned to action $\gamma $ is multiplied by $(1-\epsilon C (\gamma))> 0$
where $ C (\gamma) $ is the``cost" of action $\gamma $ and then rescaled to ensure that the
new values form a distribution. We analyze MWU in congestion games where agents
use\textit {arbitrary admissible constants} as learning rates $\epsilon $ and prove …
that works as follows: A distribution is maintained on a certain set, and at each step the
probability assigned to action $\gamma $ is multiplied by $(1-\epsilon C (\gamma))> 0$
where $ C (\gamma) $ is the``cost" of action $\gamma $ and then rescaled to ensure that the
new values form a distribution. We analyze MWU in congestion games where agents
use\textit {arbitrary admissible constants} as learning rates $\epsilon $ and prove …
Abstract
The Multiplicative Weights Update (MWU) method is a ubiquitous meta-algorithm that works as follows: A distribution is maintained on a certain set, and at each step the probability assigned to action is multiplied by where is the``cost" of action and then rescaled to ensure that the new values form a distribution. We analyze MWU in congestion games where agents use\textit {arbitrary admissible constants} as learning rates and prove convergence to\textit {exact Nash equilibria}. Interestingly, this convergence result does not carry over to the nearly homologous MWU variant where at each step the probability assigned to action is multiplied by even for the simplest case of two-agent, two-strategy load balancing games, where such dynamics can provably lead to limit cycles or even chaotic behavior.
proceedings.neurips.cc
Showing the best result for this search. See all results