A Geometric Decomposition of Finite Games: Convergence vs. Recurrence under Exponential Weights

Davide Legacci, Panayotis Mertikopoulos, Bary Pradelski
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:27137-27173, 2024.

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é 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é recurrence in harmonic games.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-legacci24a, title = {A Geometric Decomposition of Finite Games: Convergence vs. Recurrence under Exponential Weights}, author = {Legacci, Davide and Mertikopoulos, Panayotis and Pradelski, Bary}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {27137--27173}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/legacci24a/legacci24a.pdf}, url = {https://proceedings.mlr.press/v235/legacci24a.html}, 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é 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é recurrence in harmonic games.} }
Endnote
%0 Conference Paper %T A Geometric Decomposition of Finite Games: Convergence vs. Recurrence under Exponential Weights %A Davide Legacci %A Panayotis Mertikopoulos %A Bary Pradelski %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-legacci24a %I PMLR %P 27137--27173 %U https://proceedings.mlr.press/v235/legacci24a.html %V 235 %X 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é 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é recurrence in harmonic games.
APA
Legacci, D., Mertikopoulos, P. & Pradelski, B.. (2024). A Geometric Decomposition of Finite Games: Convergence vs. Recurrence under Exponential Weights. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:27137-27173 Available from https://proceedings.mlr.press/v235/legacci24a.html.

Related Material