Zero-sum Random Games on Directed Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914657452687360 |
|---|---|
| author | Attia, Luc Lichev, Lyuben Mitsche, Dieter Saona, Raimundo Ziliotto, Bruno |
| author_facet | Attia, Luc Lichev, Lyuben Mitsche, Dieter Saona, Raimundo Ziliotto, Bruno |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_16252 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Zero-sum Random Games on Directed Graphs Attia, Luc Lichev, Lyuben Mitsche, Dieter Saona, Raimundo Ziliotto, Bruno Optimization and Control 91A15, 91A43 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. |
| title | Zero-sum Random Games on Directed Graphs |
| topic | Optimization and Control 91A15, 91A43 |
| url | https://arxiv.org/abs/2401.16252 |