Convergence rates of random-order best-response dynamics in public good games on networks
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918343674429440 |
|---|---|
| author | Misiak, Wojciech Dziubiński, Marcin |
| author_facet | Misiak, Wojciech Dziubiński, Marcin |
| contents | We study convergence rates of random-order best-response dynamics in games on networks with linear best responses and strategic substitutes. Combining formal analysis with numerical simulations we identify phenomena that lead to slow convergence. One of the key such phenomena is convergence to stable strategy profiles in parts of the network neighboring sets of nodes which remain inactive until the dynamics is close to converging and then switch to activity, initiating convergence to profiles with a new set of active agents and possibly leading to another iteration of such behavior. We identify structural properties of graphs which make such phenomena more likely. These properties go beyond the spectrum of a graph, which we demonstrate analyzing convergence rates on co-spectral mates. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_15986 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Convergence rates of random-order best-response dynamics in public good games on networks Misiak, Wojciech Dziubiński, Marcin Computer Science and Game Theory Theoretical Economics We study convergence rates of random-order best-response dynamics in games on networks with linear best responses and strategic substitutes. Combining formal analysis with numerical simulations we identify phenomena that lead to slow convergence. One of the key such phenomena is convergence to stable strategy profiles in parts of the network neighboring sets of nodes which remain inactive until the dynamics is close to converging and then switch to activity, initiating convergence to profiles with a new set of active agents and possibly leading to another iteration of such behavior. We identify structural properties of graphs which make such phenomena more likely. These properties go beyond the spectrum of a graph, which we demonstrate analyzing convergence rates on co-spectral mates. |
| title | Convergence rates of random-order best-response dynamics in public good games on networks |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2602.15986 |