Equilibria in Repeated Games under No-Regret with Dynamic Benchmarks
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913661309681664 |
|---|---|
| author | Crippa, Ludovico Gur, Yonatan Light, Bar |
| author_facet | Crippa, Ludovico Gur, Yonatan Light, Bar |
| contents | In repeated games, strategies are often evaluated by their ability to guarantee the performance of the single best action that is selected in hindsight, a property referred to as \emph{Hannan consistency}, or \emph{no-regret}. However, the effectiveness of the single best action as a yardstick to evaluate strategies is limited, as any static action may perform poorly in common dynamic settings. Our work therefore turns to a more ambitious notion of \emph{dynamic benchmark consistency}, which guarantees the performance of the best \emph{dynamic} sequence of actions, selected in hindsight subject to a constraint on the allowable number of action changes. Our main result establishes that for any joint empirical distribution of play that may arise when all players deploy no-regret strategies, there exist dynamic benchmark consistent strategies such that if all players deploy these strategies the same empirical distribution emerges when the horizon is large enough. This result demonstrates that although dynamic benchmark consistent strategies have a different algorithmic structure and provide significantly enhanced individual assurances, they lead to the same equilibrium set as no-regret strategies. Moreover, the proof of our main result uncovers the capacity of independent algorithms with strong individual guarantees to foster a strong form of coordination. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_03152 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Equilibria in Repeated Games under No-Regret with Dynamic Benchmarks Crippa, Ludovico Gur, Yonatan Light, Bar Computer Science and Game Theory Theoretical Economics In repeated games, strategies are often evaluated by their ability to guarantee the performance of the single best action that is selected in hindsight, a property referred to as \emph{Hannan consistency}, or \emph{no-regret}. However, the effectiveness of the single best action as a yardstick to evaluate strategies is limited, as any static action may perform poorly in common dynamic settings. Our work therefore turns to a more ambitious notion of \emph{dynamic benchmark consistency}, which guarantees the performance of the best \emph{dynamic} sequence of actions, selected in hindsight subject to a constraint on the allowable number of action changes. Our main result establishes that for any joint empirical distribution of play that may arise when all players deploy no-regret strategies, there exist dynamic benchmark consistent strategies such that if all players deploy these strategies the same empirical distribution emerges when the horizon is large enough. This result demonstrates that although dynamic benchmark consistent strategies have a different algorithmic structure and provide significantly enhanced individual assurances, they lead to the same equilibrium set as no-regret strategies. Moreover, the proof of our main result uncovers the capacity of independent algorithms with strong individual guarantees to foster a strong form of coordination. |
| title | Equilibria in Repeated Games under No-Regret with Dynamic Benchmarks |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2212.03152 |