Stochastic learning dynamics and speed of convergence in population games
We study how long it takes for large populations of interacting agents to come close to Nash equilibrium when they adapt their behavior using a stochastic better reply dynamic. Prior work considers this question mainly for 2 × 2 games and potential games; here we characterize convergence times for g...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Econometric Society
2016
|
| _version_ | 1797064700212543488 |
|---|---|
| author | Arieli, I Young, H |
| author_facet | Arieli, I Young, H |
| author_sort | Arieli, I |
| collection | OXFORD |
| description | We study how long it takes for large populations of interacting agents to come close to Nash equilibrium when they adapt their behavior using a stochastic better reply dynamic. Prior work considers this question mainly for 2 × 2 games and potential games; here we characterize convergence times for general weakly acyclic games, including coordination games, dominance solvable games, games with strategic complementarities, potential games, and many others with applications in economics, biology, and distributed control. If players' better replies are governed by idiosyncratic shocks, the convergence time can grow exponentially in the population size; moreover, this is true even in games with very simple payoff structures. However, if their responses are sufficiently correlated due to aggregate shocks, the convergence time is greatly accelerated; in fact, it is bounded for all sufficiently large populations. We provide explicit bounds on the speed of convergence as a function of key structural parameters including the number of strategies, the length of the better reply paths, the extent to which players can influence the payoffs of others, and the desired degree of approximation to Nash equilibrium. |
| first_indexed | 2024-03-06T21:18:05Z |
| format | Journal article |
| id | oxford-uuid:407b0e16-824b-4b7e-b7cb-567cc7285e51 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T21:18:05Z |
| publishDate | 2016 |
| publisher | Econometric Society |
| record_format | dspace |
| spelling | oxford-uuid:407b0e16-824b-4b7e-b7cb-567cc7285e512022-03-26T14:38:10ZStochastic learning dynamics and speed of convergence in population gamesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:407b0e16-824b-4b7e-b7cb-567cc7285e51Symplectic Elements at OxfordEconometric Society2016Arieli, IYoung, HWe study how long it takes for large populations of interacting agents to come close to Nash equilibrium when they adapt their behavior using a stochastic better reply dynamic. Prior work considers this question mainly for 2 × 2 games and potential games; here we characterize convergence times for general weakly acyclic games, including coordination games, dominance solvable games, games with strategic complementarities, potential games, and many others with applications in economics, biology, and distributed control. If players' better replies are governed by idiosyncratic shocks, the convergence time can grow exponentially in the population size; moreover, this is true even in games with very simple payoff structures. However, if their responses are sufficiently correlated due to aggregate shocks, the convergence time is greatly accelerated; in fact, it is bounded for all sufficiently large populations. We provide explicit bounds on the speed of convergence as a function of key structural parameters including the number of strategies, the length of the better reply paths, the extent to which players can influence the payoffs of others, and the desired degree of approximation to Nash equilibrium. |
| spellingShingle | Arieli, I Young, H Stochastic learning dynamics and speed of convergence in population games |
| title | Stochastic learning dynamics and speed of convergence in population games |
| title_full | Stochastic learning dynamics and speed of convergence in population games |
| title_fullStr | Stochastic learning dynamics and speed of convergence in population games |
| title_full_unstemmed | Stochastic learning dynamics and speed of convergence in population games |
| title_short | Stochastic learning dynamics and speed of convergence in population games |
| title_sort | stochastic learning dynamics and speed of convergence in population games |
| work_keys_str_mv | AT arielii stochasticlearningdynamicsandspeedofconvergenceinpopulationgames AT youngh stochasticlearningdynamicsandspeedofconvergenceinpopulationgames |