A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights

• URL: http://arxiv.org/abs/2405.07224v2
• Date: Sat, 18 May 2024 07:16:24 GMT
• Title: A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights
• Authors: Davide Legacci, Panayotis Mertikopoulos, Bary Pradelski,
• Abstract summary: We decompose games into simpler components where the dynamics' long-run behavior is well understood. In particular, the dynamics of exponential / multiplicative weights (EW) schemes is not compatible with the Euclidean underpinnings of Helmholtz's theorem. We establish a deep connection with a well-known decomposition of games into a potential and harmonic component.
• Score: 24.800126996235512
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In view of the complexity of the dynamics of learning in games, we seek to decompose a game into simpler components where the dynamics' long-run behavior is well understood. A natural starting point for this is Helmholtz's theorem, which decomposes a vector field into a potential and an incompressible component. However, the geometry of game dynamics - and, in particular, the dynamics of exponential / multiplicative weights (EW) schemes - is not compatible with the Euclidean underpinnings of Helmholtz's theorem. This leads us to consider a specific Riemannian framework based on the so-called Shahshahani metric, and introduce the class of incompressible games, for which we establish the following results: First, in addition to being volume-preserving, the continuous-time EW dynamics in incompressible games admit a constant of motion and are Poincar\'e recurrent - i.e., almost every trajectory of play comes arbitrarily close to its starting point infinitely often. Second, we establish a deep connection with a well-known decomposition of games into a potential and harmonic component (where the players' objectives are aligned and anti-aligned respectively): a game is incompressible if and only if it is harmonic, implying in turn that the EW dynamics lead to Poincar\'e recurrence in harmonic games.

Related papers

• On the Decomposition of Differential Game [10.44920684595193]
  We decompose differential games into components where the dynamic is well understood. We show that scalar potential games coincide with potential games proposed by citemondererpotential1996. For the vector potential game, we show that the individual gradient field is divergence-free, in which case the gradient descent dynamic may either be divergent or recurrent.
  arXiv  Detail & Related papers  (2024-11-06T09:55:01Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  We characterize the convergence of optimistic gradient descent (OGD) in time-varying games. Our framework yields sharp convergence bounds for the equilibrium gap of OGD in zero-sum games. We also provide new insights on dynamic regret guarantees in static games.
  arXiv  Detail & Related papers  (2023-01-26T17:25:45Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics [28.815822236291392]
  We show that no game dynamics can converge to $epsilon$-Nash equilibria. We also prove a stronger result for $epsilon$-approximate Nash equilibria.
  arXiv  Detail & Related papers  (2022-03-26T18:27:40Z)
• Online Learning in Periodic Zero-Sum Games [27.510231246176033]
  We show that Poincar'e recurrence provably generalizes despite the complex, non-autonomous nature of these dynamical systems.
  arXiv  Detail & Related papers  (2021-11-05T10:36:16Z)
• Entanglement dynamics of spins using a few complex trajectories [77.34726150561087]
  We consider two spins initially prepared in a product of coherent states and study their entanglement dynamics. We adopt an approach that allowed the derivation of a semiclassical formula for the linear entropy of the reduced density operator.
  arXiv  Detail & Related papers  (2021-08-13T01:44:24Z)
• Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [65.64512759706271]
  We study the existence of simple, uncoupled no-regret dynamics that converge to correlated equilibria in normal-form games. We introduce a notion of trigger regret in extensive-form games, which extends that of internal regret in normal-form games. We give an efficient no-regret algorithm which guarantees with high probability that trigger regrets grow sublinearly in the number of iterations.
  arXiv  Detail & Related papers  (2021-04-04T02:26:26Z)
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
  We present volume analyses of Multiplicative Weights Updates (MWU) and Optimistic Multiplicative Weights Updates (OMWU) in zero-sum as well as coordination games. We show that OMWU contracts volume, providing an alternative understanding for its known convergent behavior. We also prove a no-free-lunch type of theorem, in the sense that when examining coordination games the roles are reversed: OMWU expands volume exponentially fast, whereas MWU contracts.
  arXiv  Detail & Related papers  (2020-05-28T13:47:09Z)
• No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [76.78447814623665]
  We give the first uncoupled no-regret dynamics that converge to correlated equilibria in normal-form games. We introduce a notion of trigger regret in extensive-form games, which extends that of internal regret in normal-form games. Our algorithm decomposes trigger regret into local subproblems at each decision point for the player, and constructs a global strategy of the player from the local solutions.
  arXiv  Detail & Related papers  (2020-04-01T17:39:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.