Source-linked AI summary
Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos
Gerasimos Palaiopanos, Ioannis Panageas, Georgios Piliouras
TL;DR
Although the two MWU variants share regret-minimizing properties, their constant-rate behavior in congestion games can differ. The paper analyzes the linear variant using a Baum-Eagon inequality and proves convergence to exact Nash equilibria, while the exponential variant can cycle or behave chaotically.
Problem
The two nearly identical MWU variants share regret-minimizing properties, but their behavior with constant learning rates in congestion games differs.
Source: §1 · p. 1Method
The paper analyzes the linear MWU variant in congestion games using a generalization of the Baum-Eagon inequality to show a potential function increases unless the state is fixed.
Source: §4 · p. 6, §6 · p. 14Results
MWUℓ converges to exact Nash equilibria for arbitrary admissible constant learning rates, whereas MWUe can have limit cycles or chaotic behavior, with periodic behavior also observed numerically between convergent and chaotic regions.
Source: §1 · p. 1, §6 · p. 14Takeaways & Limitations
The variants’ shared regret-minimizing property does not imply equivalent constant-rate convergence behavior in congestion games.
Source: §1 · p. 1, §6 · p. 14The non-convergent MWUe examples rely on symmetric initial conditions; whether such trajectories occur from generic initial conditions is unknown.
Source: §6 · p. 15
Abstract
from arXiv · showhide
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 element $\gamma$ is multiplied by $(1 -\epsilon C(\gamma))>0$ where $C(\gamma)$ is the "cost" of element $\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 convergence to \textit{exact Nash equilibria}. Our proof leverages a novel connection between MWU and the Baum-Welch algorithm, the standard instantiation of the Expectation-Maximization (EM) algorithm for hidden Markov models (HMM). Interestingly, this convergence result does not carry over to the nearly homologous MWU variant where at each step the probability assigned to element $\gamma$ is multiplied by $(1 -\epsilon)^{C(\gamma)}$ even for the most innocuous case of two-agent, two-strategy load balancing games, where such dynamics can provably lead to limit cycles or even chaotic behavior.
1 Introduction
The paper asks whether MWU can behave well in congestion games with constant learning rates, despite known concerns about large fixed rates. It proves convergence for linear MWU and contrasts this with non-convergent behavior in the exponential variant.
1 Introduction
- MWU is typically introduced in two nearly identical variants: the linear variant multiplies action γ’s probability by (1 − ϵC(γ)), while the exponential variant uses (1 − ϵ)C(γ); both have the same advantageous regret-minimizing property.Source: §1 · p. 1
Our contribution.
- The exponential variant can exhibit limit cycles or chaos even in two-agent, two-strategy load-balancing games.For unequal edge costs, the paper reports periodic orbits of every positive length and uncountably many initial conditions with Li-Yorke chaos.Source: §1 · p. 1, Our contribution · p. 2
1 Introduction
- For exponential MWU, the paper attributes the concern to large fixed rates: simultaneous cost reduction can cancel agents' gains and produce non-convergent behavior.The paper contrasts this with the usual approach of monitoring and successively reducing the learning rate.Source: §1 · p. 2
Our contribution.
- Linear MWU converges to exact Nash equilibria in congestion games for arbitrary admissible constant learning rates.The rates may differ by agent; each agent's multiplicative factor must remain positive for every strategy outcome.Source: Our contribution · p. 2
- The paper's convergence proof connects linear MWU in congestion games to the Baum-Eagon class, which also includes Baum-Welch, the EM algorithm for HMMs.The proof establishes that the mixed-state potential strictly decreases along every nontrivial trajectory.Source: Our contribution · p. 2
2 Related Work
Prior work establishes convergence in several related settings, but the paper positions its results as a deterministic convergence guarantee for general atomic congestion games and a first formal demonstration of limit cycles and chaos there.
2 Related Work
- Congestion games are isomorphic to potential games and have been used in many modeling problems, including studies of equilibrium efficiency.The passage describes price-of-anarchy analysis in congestion games as a developed area of algorithmic game theory.Source: §2 · p. 3
- The paper reports no prior deterministic convergence result to exact Nash equilibria for general atomic congestion games, contrasting its result with randomized exponential MWU convergence for sufficiently small rates.Concurrent moves do not guarantee convergence in general; the cited randomized result converges with high probability to pure Nash equilibria.Source: §2 · p. 3
- MWU is used in online learning and algorithmic game theory, where its time-average behavior yields approximate coarse correlated equilibria with price-of-anarchy guarantees.The passage also reviews links between MWU, haploid evolution, and coordination games.Source: §2 · p. 3
- The paper presents its analysis as the first formal proof of non-convergent MWU behavior in congestion games, including limit cycles and chaos in the minimal two-balls, two-bins case.Earlier non-convergence results discussed in the passage concern other settings or variants, including Shapley and perturbed zero-sum games.Source: §2 · p. 3
3 Preliminaries
The preliminaries define congestion-game costs and mixed strategies, introduce the dynamical-systems concepts used to analyze convergence and chaos, and present the Baum-Eagon connection and the two MWU updates.
3.1 Congestion Games
- In congestion games, agents choose resource sets and incur costs determined by resource load; mixed strategies assign probabilities to each agent's strategies.An agent's strategy cost is its expected cost against the other agents' mixed strategies.Source: §3.1 · pp. 3–4
3.2 Dynamical Systems and Chaos
- A Lyapunov or potential function can establish convergence when it strictly increases along every non-fixed-point update; the paper defines limit cycles and Li-Yorke chaos for discrete dynamics.The paper uses period-three behavior as the premise for its cited Li-Yorke theorem on periodic points of every length.Source: §3.2 · p. 4
3.3 Baum-Eagon Inequality, Baum-Welch and EM
- The Baum-Eagon inequality makes a nonnegative-coefficient homogeneous polynomial strictly increase under its associated update unless the point is unchanged.The paper places both Baum-Welch and linear MWU in congestion games within this iterative-process class, using different polynomials.Source: §3.3 · p. 5
3.4 Multiplicative Weights Update
- Linear and exponential MWU use distinct update rules; the linear rule requires positive update factors, while the exponential rule uses a constant rate below one.The two dynamics have the same fixed points, which include the game's Nash equilibria.Source: §3.4 · pp. 5–6
4 Convergence of MWUℓto Nash Equilibria
MWUℓ converges to fixed points because the expected potential decreases along nontrivial trajectories. With isolated fixed points, interior initial distributions converge to Nash equilibria.
4 Convergence of MWUℓto Nash Equilibria
- Q is constructed as a polynomial with nonnegative coefficients, allowing the Baum–Eagon result to apply to the MWUℓ update.The proof establishes nonnegative coefficients for Q and relates it to the expected potential by Ψ = const − Q.Source: §4 · pp. 6–7
- The proof uses a generalized Baum–Eagon result to make an auxiliary function Q strictly increase under MWUℓ.The extension handles non-homogeneous polynomials by adding a dummy variable fixed at one.Source: §4 · pp. 6, 8
- Since Q increases unless the dynamics reach a fixed point, the expected potential decreases and the set of limit points consists only of fixed points.The argument uses boundedness of the expected potential and the invariance of the set of limit points.Source: §4 · p. 8
- MWUℓ trajectories converge to fixed points, with the expected potential decreasing strictly except at fixed points.The expected potential is nonincreasing over time, with equality only at fixed points.Source: §4 · pp. 6, 8
- With isolated fixed points, every interior initial distribution converges to a Nash equilibrium.The result assumes the initial distribution lies in the interior of the strategy simplices.Source: §4 · p. 8
5 Non-Convergence of MWUe: Limit Cycle and Chaos
The section contrasts MWUe’s non-convergent dynamics with MWUℓ’s convergence in simple two-agent congestion games. It analyzes a symmetric one-dimensional reduction to establish periodic orbits and chaos.
5 Non-Convergence of MWUe: Limit Cycle and Chaos
- With equal learning rates and equal initial mixed strategies, symmetry keeps both agents’ probabilities equal, reducing the MWUe dynamics to one variable.The examples use symmetric two-agent, two-strategy congestion games.Source: §5 · p. 9
5.1.1 The signs of the derivative of H(H(x))
- For 0 < y0 < x0 < 1/2 < x1 < y1 < 1, H(H(x)) is strictly increasing on [0, y0], [x0, x1], and [y1, 1], and strictly decreasing on [y0, x0] and [x1, y1].Source: §5.1.1 · p. 9
5.1.2 The fixed points of H(H(x))
- There are five fixed points of H(H(x)); its difference from x is positive on (0, ρ1) and (1/2, ρ2), and negative on (ρ1, 1/2) and (ρ2, 1).The noncentral points satisfy 0 < ρ1 < 1/2 < ρ2 < 1, with ρ2 = 1 − ρ1.Source: §5.1.2 · p. 11
5.1.3 Periodic orbits
- For almost all initial conditions, MWUe converges to the two-cycle {ρ1, ρ2}, with H exchanging its points; in contrast, MWUℓ converges to the equilibrium at 1/2.The exceptional initial-condition set has measure zero.Source: §5.1.3 · pp. 11, 13, Figure 2 · p. 12
5.2 Analyzing xt+1 = G(xt)
- G has fixed points 0, 3/4, and 1, and also has a periodic orbit of length three.The length-three orbit is established by finding a point y with G(G(G(y))) = y that is not fixed by G or G².Source: §5.2 · p. 13
- MWUe admits periodic orbits of every natural-number length and uncountably many scrambled initial conditions, while MWUℓ converges to the Nash equilibrium at 3/4 in the example.The period-three orbit yields the Li-Yorke chaos result.Source: §5.2 · p. 13, Figure 3 · p. 14
6 Conclusion and Future Work
MWUℓ converges to exact Nash equilibria in congestion games with arbitrary admissible constant learning rates, while MWUe can exhibit limit cycles or chaos. The authors identify open questions about MWUe’s periodic behavior and the initial conditions needed for non-convergence.
6 Conclusion and Future Work
- MWUℓ converges to exact Nash equilibria in congestion games with arbitrary admissible constant learning rates.The conclusion contrasts this result with the nearly homologous exponential variant.Source: §6 · p. 14
- MWUe can exhibit limit cycles or chaotic behavior, unlike the convergence result established for MWUℓ.For sufficiently small learning rates, MWUe approaches replicator dynamics and convergence is again guaranteed.Source: §6 · p. 14
- Numerical experiments find periodic behavior between MWUe’s convergent and chaotic learning-rate regions, with period doubling identified as an open connection to explore.The authors also pose the broader question of what regularities occur in these non-equilibrium systems.Source: §6 · p. 14
- The known non-convergent MWUe examples critically rely on symmetric initial conditions; whether such trajectories occur from generic initial conditions remains unknown.Despite this non-generic scope, the examples rule out leveraging Baum-Eagon techniques for MWUe.Source: §6 · p. 15