Random Zero-Sum Dynamic Games on Infinite Directed Graphs

Luc Attia, Lyuben Lichev, Dieter Mitsche, Raimundo Saona and Bruno Ziliotto
Additional contact information
Luc Attia: Université Paris Dauphine-PSL - PSL - Université Paris Sciences et Lettres, CNRS - Centre National de la Recherche Scientifique, CEREMADE - CEntre de REcherches en MAthématiques de la DEcision - Université Paris Dauphine-PSL - PSL - Université Paris Sciences et Lettres - CNRS - Centre National de la Recherche Scientifique
Lyuben Lichev: IST Austria - Institute of Science and Technology [Klosterneuburg, Austria]
Dieter Mitsche: UC - Pontificia Universidad Católica de Chile
Raimundo Saona: IST Austria - Institute of Science and Technology [Klosterneuburg, Austria]
Bruno Ziliotto: TSE-R - Toulouse School of Economics - UT Capitole - Université Toulouse Capitole - UT - Université de Toulouse - EHESS - École des hautes études en sciences sociales - CNRS - Centre National de la Recherche Scientifique - INRAE - Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement, CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

Abstract: We consider random two-player zero-sum dynamic games with perfect information on a class of infinite directed graphs. Starting from a fixed vertex, the players take turns to move a token along the edges of the graph. Every vertex is assigned a payoff known in advance by both players. Every time the token visits a vertex, Player 2 pays Player 1 the corresponding payoff. We consider a distribution over such games by assigning i.i.d. payoffs to the vertices. On the one hand, for acyclic directed graphs of bounded degree and sub-exponential expansion, we show that, when the duration of the game tends to infinity, the value 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.

Keywords: Zero-sum games; Dynamic games; Random games; Directed graphs (search for similar items in EconPapers)
Date: 2025-03
References: Add references at CitEc
Citations:

Published in Dynamic Games and Applications, 2025, ⟨10.1007/s13235-025-00636-4⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-05092326

DOI: 10.1007/s13235-025-00636-4

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().