On the Decomposition of Differential Game

• URL: http://arxiv.org/abs/2411.03802v1
• Date: Wed, 06 Nov 2024 09:55:01 GMT
• Title: On the Decomposition of Differential Game
• Authors: Nanxiang Zhou, Jing Dong, Yutian Li, Baoxiang Wang,
• Abstract summary: 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.
• Score: 10.44920684595193
• License:
• Abstract: To understand the complexity of the dynamic of learning in differential games, we decompose the game into components where the dynamic is well understood. One of the possible tools is Helmholtz's theorem, which can decompose a vector field into a potential and a harmonic component. This has been shown to be effective in finite and normal-form games. However, applying Helmholtz's theorem by connecting it with the Hodge theorem on $\mathbb{R}^n$ (which is the strategy space of differential game) is non-trivial due to the non-compactness of $\mathbb{R}^n$. Bridging the dynamic-strategic disconnect through Hodge/Helmoltz's theorem in differential games is then left as an open problem \cite{letcher2019differentiable}. In this work, we provide two decompositions of differential games to answer this question: the first as an exact scalar potential part, a near vector potential part, and a non-strategic part; the second as a near scalar potential part, an exact vector potential part, and a non-strategic part. We show that scalar potential games coincide with potential games proposed by \cite{monderer1996potential}, where the gradient descent dynamic can successfully find the Nash equilibrium. 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.

Related papers

• Exact dynamics of quantum dissipative $XX$ models: Wannier-Stark localization in the fragmented operator space [49.1574468325115]
  We find an exceptional point at a critical dissipation strength that separates oscillating and non-oscillating decay. We also describe a different type of dissipation that leads to a single decay mode in the whole operator subspace.
  arXiv  Detail & Related papers  (2024-05-27T16:11:39Z)
• A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights [24.800126996235512]
  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.
  arXiv  Detail & Related papers  (2024-05-12T08:58:35Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  We develop a new framework to characterize optimistic policy gradient methods in multi-player games with a single controller. Our approach relies on a natural generalization of the classical Minty property that we introduce, which we anticipate to have further applications beyond Markov games.
  arXiv  Detail & Related papers  (2023-12-19T11:34:10Z)
• Scalable and Independent Learning of Nash Equilibrium Policies in $n$-Player Stochastic Games with Unknown Independent Chains [1.0878040851638]
  We study games with independent chains and unknown transition matrices. In this class of games, players control their own internal Markov chains whose transitions do not depend on the states/actions of other players. We propose a fully decentralized mirror descent algorithm to learn an $epsilon$-NE policy.
  arXiv  Detail & Related papers  (2023-12-04T03:04:09Z)
• Local Convergence of Gradient Methods for Min-Max Games: Partial Curvature Generically Suffices [0.5439020425819]
  We study the convergence to local Nash equilibria of gradient methods for two-player zero-sum differentiable games. We show that thanks to partial curvature, conic particle methods -- which optimize over both weights and supports of the mixed strategies -- generically converge faster than fixed-support methods.
  arXiv  Detail & Related papers  (2023-05-26T21:43:56Z)
• An Explicit Expansion of the Kullback-Leibler Divergence along its Fisher-Rao Gradient Flow [8.052709336750823]
  We show that when $pirhollback$ exhibits multiple modes, $pirhollback$ is that textitindependent of the potential function. We provide an explicit expansion of $textKL. KL. KL. KL. KL. KL. KL. KL. KL. KL. KL. KL. KL.
  arXiv  Detail & Related papers  (2023-02-23T18:47:54Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• The Franke-Gorini-Kossakowski-Lindblad-Sudarshan (FGKLS) Equation for Two-Dimensional Systems [62.997667081978825]
  Open quantum systems can obey the Franke-Gorini-Kossakowski-Lindblad-Sudarshan (FGKLS) equation. We exhaustively study the case of a Hilbert space dimension of $2$.
  arXiv  Detail & Related papers  (2022-04-16T07:03:54Z)
• The world as a neural network [0.0]
  We discuss a possibility that the universe on its most fundamental level is a neural network. We identify two different types of dynamical degrees of freedom: "trainable" variables and "hidden" variables. We argue that the entropy production in such a system is a local function of the symmetries of the Onsager-Hilbert term.
  arXiv  Detail & Related papers  (2020-08-04T17:10:46Z)
• Accelerating Smooth Games by Manipulating Spectral Shapes [51.366219027745174]
  We use matrix iteration theory to characterize acceleration in smooth games. We describe gradient-based methods, such as extragradient, as transformations on the spectral shape. We propose an optimal algorithm for bilinear games.
  arXiv  Detail & Related papers  (2020-01-02T19:21:48Z)

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.