Zero-sum random games on directed graphs
Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Zero-sum random games on directed graphs. arXiv, 2401.16252.
Download (ext.)
Preprint
| Submitted
| English
Author
Attia, Luc;
Lichev, Lyuben;
Mitsche, Dieter;
Saona, RaimundoISTA 
;
Ziliotto, Bruno
;
Ziliotto, BrunoDepartment
Abstract
This paper considers a class of two-player zero-sum games on directed graphs whose vertices are equipped with random payoffs of bounded support known by both players.
Starting from a fixed vertex, players take turns to move a token along the edges of the graph.
On the one hand, for acyclic directed graphs of bounded degree and sub-exponential expansion, we show that the value of the game converges almost surely to a constant at an exponential rate dominated in terms of the expansion.
On the other hand, for the infinite d-ary tree that does not fall into the previous class of graphs, we show convergence at a double-exponential rate in terms of the expansion.
Publishing Year
Date Published
2024-01-29
Journal Title
arXiv
Acknowledgement
This work was supported by the French Agence Nationale de la Recherche (ANR) under references ANR-21-CE40-0020 (CONVERGENCE project) and ANR-20-CE40-0002 (GrHyDy), and by Fondecyt grant 1220174. This collaboration was mainly conducted during a 1-year visit of Bruno Ziliotto to the Center for Mathematical Modeling (CMM) at University of Chile in 2023,
under the IRL program of CNRS.
Article Number
2401.16252
IST-REx-ID
Cite this
Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Zero-sum random games on directed graphs. arXiv. doi:10.48550/arXiv.2401.16252
Attia, L., Lichev, L., Mitsche, D., Saona Urmeneta, R. J., & Ziliotto, B. (n.d.). Zero-sum random games on directed graphs. arXiv. https://doi.org/10.48550/arXiv.2401.16252
Attia, Luc, Lyuben Lichev, Dieter Mitsche, Raimundo J Saona Urmeneta, and Bruno Ziliotto. “Zero-Sum Random Games on Directed Graphs.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2401.16252.
L. Attia, L. Lichev, D. Mitsche, R. J. Saona Urmeneta, and B. Ziliotto, “Zero-sum random games on directed graphs,” arXiv. .
Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Zero-sum random games on directed graphs. arXiv, 2401.16252.
Attia, Luc, et al. “Zero-Sum Random Games on Directed Graphs.” ArXiv, 2401.16252, doi:10.48550/arXiv.2401.16252.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2401.16252
Google Scholar