Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2510.02984 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909823328583680 |
|---|---|
| author | Bertrand, Nathalie Bouyer, Patricia Lapointe, Luc Mascle, Corto |
| author_facet | Bertrand, Nathalie Bouyer, Patricia Lapointe, Luc Mascle, Corto |
| contents | In repeated games, players choose actions concurrently at each step. We consider a parameterized setting of repeated games in which the players form a population of an arbitrary size. Their utility functions encode a reachability objective. The problem is whether there exists a uniform coalition strategy for the players so that they are sure to win independently of the population size. We use algebraic tools to show that the problem can be solved in polynomial space. First we exhibit a finite semigroup whose elements summarize strategies over a finite interval of population sizes. Then, we characterize the existence of winning strategies by the existence of particular elements in this semigroup. Finally, we provide a matching complexity lower bound, to conclude that repeated population games with reachability objectives are PSPACE-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_02984 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Reach together: How populations win repeated games Bertrand, Nathalie Bouyer, Patricia Lapointe, Luc Mascle, Corto Computer Science and Game Theory Formal Languages and Automata Theory F.4.3 In repeated games, players choose actions concurrently at each step. We consider a parameterized setting of repeated games in which the players form a population of an arbitrary size. Their utility functions encode a reachability objective. The problem is whether there exists a uniform coalition strategy for the players so that they are sure to win independently of the population size. We use algebraic tools to show that the problem can be solved in polynomial space. First we exhibit a finite semigroup whose elements summarize strategies over a finite interval of population sizes. Then, we characterize the existence of winning strategies by the existence of particular elements in this semigroup. Finally, we provide a matching complexity lower bound, to conclude that repeated population games with reachability objectives are PSPACE-complete. |
| title | Reach together: How populations win repeated games |
| topic | Computer Science and Game Theory Formal Languages and Automata Theory F.4.3 |
| url | https://arxiv.org/abs/2510.02984 |