Game Connectivity and Adaptive Dynamics
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912445222617088 |
|---|---|
| author | Johnston, Tom Savery, Michael Scott, Alex Tarbush, Bassel |
| author_facet | Johnston, Tom Savery, Michael Scott, Alex Tarbush, Bassel |
| contents | We analyse the typical structure of games in terms of the connectivity properties of their best-response graphs. Our central result shows that, among games that are `generic' (without indifferences) and that have a pure Nash equilibrium, all but a small fraction are \emph{connected}, meaning that every action profile that is not a pure Nash equilibrium can reach every pure Nash equilibrium via best-response paths. This has important implications for dynamics in games. In particular, we show that there are simple, uncoupled, adaptive dynamics for which period-by-period play converges almost surely to a pure Nash equilibrium in all but a small fraction of generic games that have one (which contrasts with the known fact that there is no such dynamic that leads almost surely to a pure Nash equilibrium in \emph{every} generic game that has one). We build on recent results in probabilistic combinatorics for our characterisation of game connectivity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_10609 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Game Connectivity and Adaptive Dynamics Johnston, Tom Savery, Michael Scott, Alex Tarbush, Bassel Theoretical Economics Computer Science and Game Theory Combinatorics We analyse the typical structure of games in terms of the connectivity properties of their best-response graphs. Our central result shows that, among games that are `generic' (without indifferences) and that have a pure Nash equilibrium, all but a small fraction are \emph{connected}, meaning that every action profile that is not a pure Nash equilibrium can reach every pure Nash equilibrium via best-response paths. This has important implications for dynamics in games. In particular, we show that there are simple, uncoupled, adaptive dynamics for which period-by-period play converges almost surely to a pure Nash equilibrium in all but a small fraction of generic games that have one (which contrasts with the known fact that there is no such dynamic that leads almost surely to a pure Nash equilibrium in \emph{every} generic game that has one). We build on recent results in probabilistic combinatorics for our characterisation of game connectivity. |
| title | Game Connectivity and Adaptive Dynamics |
| topic | Theoretical Economics Computer Science and Game Theory Combinatorics |
| url | https://arxiv.org/abs/2309.10609 |