Mather sets of a cascade generated by the FTRL algorithm of a two-agent zero-sum game with mixed strategies
DOI:
https://doi.org/10.3842/umzh.v77i6.9034Keywords:
cascade, FTRL algorithm, monotone twist mapping, Mather setAbstract
UDC 517.9
We establish conditions under which a two-dimensional cascade generated by the FTRL algorithm of a two-agent zero-sum game with mixed strategies, is determined by a twist mapping of the plane. For the indicated cascade, we prove the existence of Mather sets corresponding to the rotation numbers from a certain interval. In this way, we explain why, in the computer experiments, the orbits of the analyzed cascade are located on closed curves and, in a certain sense, have the property of local convexity.
References
1. E. Hairer, C. Lubich, G. Wanner, Geometric numerical integration, Structure-preserving algorithms for ordinary differential equations, 2nd ed., Springer Ser. Comput. Math., 31, Springer, Berlin (2006); DOI: 10.1007/3-540-30666-8. DOI: https://doi.org/10.1007/3-540-30666-8
2. G. Benettin, A. Giorgilli, On the Hamiltonian interpolation of near-to-the-identity symplectic mappings with application to symplectic integration algorithms, J. Stat. Phys., 74, № 5-6, 1117–1143 (1994); DOI: 10.1007/BF02188219. DOI: https://doi.org/10.1007/BF02188219
3. J. Hofbauer, Evolutionary dynamics for bimatrix games: a Hamiltonian system?, J. Math. Biol., 34, № 5-6, 675–688 (1996); DOI: 10.1007/BF02409754. DOI: https://doi.org/10.1007/BF02409754
4. J. P. Bailey, G. Gidel, G. Piliouras, Finite regret and cycles with fixed step-size via alternating gradient descent-ascent, Proceedings of Thirty Third Conference on Learning Theory, Proceedings of Machine Learning Research, 125, 391–407 (2020); https://proceedings.mlr.press/v125/bailey20a.html.
5. J. P. Bailey, G. Piliouras, Multi-agent learning in network zero-sum games is a Hamiltonian system, Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS'19, Montreal, QC, Canada, May 13–17, 2019, International Foundation for Autonomous Agents and Multiagent Systems, 233–241 (2019); http://dl.acm.org/citation.cfm?id=3306127.
6. J. P. Bailey, G. Piliouras, Multiplicative weights update in zero-sum games, Proceedings of the 2018 ACM Conference on Economics and Computation, EC'18, Association for Computing Machinery, New York, 321–338 (2018); DOI: 10.1145/3219166.3219235. DOI: https://doi.org/10.1145/3219166.3219235
7. P. Mertikopoulos, C. Papadimitriou, G. Piliouras, Cycles in adversarial regularized learning, Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January~7–10, 2018, Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); Association for Computing Machinery (ACM), New York, 2703–2717 (2018); dl.acm.org/citation.cfm?id=3175476. DOI: https://doi.org/10.1137/1.9781611975031.172
8. G. Piliouras, S. Jeff, J. S. Shamma, Optimization despite chaos: convex relaxations to complex limit sets via Poincare recurrence, 861–873 (2014); https://epubs.siam.org/doi/abs/10.1137/1.9781611973402.64. DOI: https://doi.org/10.1137/1.9781611973402.64
9. S. Aubry, P. Y. Le Daeron, The discrete Frenkel–Kontorova model and its extensions. I. Exact results for the ground-states, Phys. D, 8, № 3, 381–422 (1983); DOI: 10.1016/0167-2789(83)90233-6. DOI: https://doi.org/10.1016/0167-2789(83)90233-6
10. C. Golé, Symplectic twist maps, Advanced Series in Nonlinear Dynamics, 18, World Sci. Publ. Co., Inc., River Edge, NJ (2001); DOI: 10.1142/9789812810762. DOI: https://doi.org/10.1142/9789812810762
11. J. N. Mather, Existence of quasiperiodic orbits for twist homeomorphisms of the annulus, Topology, 21, № 4, 457–467 (1982); DOI: 10.1016/0040-9383(82)90023-4. DOI: https://doi.org/10.1016/0040-9383(82)90023-4
12. J. Moser, Recent developments in the theory of Hamiltonian systems, SIAM Rev., 28, № 4, 459–485 (1986); DOI: 10.1137/1028153. DOI: https://doi.org/10.1137/1028153
13. J. Moser, Monotone twist mappings and the calculus of variations, Ergodic Theory and Dynam. Systems, 6, № 3, 401–413 (1986); DOI: 10.1017/S0143385700003588. DOI: https://doi.org/10.1017/S0143385700003588
14. V. I. Arnold, Mathematical methods of classical mechanics, 2nd ed., Grad. Texts Math., 60, Springer-Verlag, New York (1989); DOI: 10.1007/978-1-4757-2063-1. DOI: https://doi.org/10.1007/978-1-4757-2063-1
Downloads
Published
Issue
Section
License
Copyright (c) 2025 V. Kolner, I. Parasyuk
This work is licensed under a Creative Commons Attribution 4.0 International License.
