Best-response dynamics, playing sequences, and convergence to equilibrium in random games
We analyze the performance of the best-response dynamic across all normalform games using a random games approach. The playing sequence—the order in which players update their actions—is essentially irrelevant in determining whether the dynamic converges to a Nash equilibrium in certain classes of g...
| Հիմնական հեղինակներ: | , , , , , , |
|---|---|
| Ձևաչափ: | Journal article |
| Լեզու: | English |
| Հրապարակվել է: |
Springer
2023
|
| Ամփոփում: | We analyze the performance of the best-response dynamic across all normalform games using a random games approach. The playing sequence—the order in which
players update their actions—is essentially irrelevant in determining whether the dynamic converges to a Nash equilibrium in certain classes of games (e.g. in potential
games) but, when evaluated across all possible games, convergence to equilibrium depends on the playing sequence in an extreme way. Our main asymptotic result shows
that the best-response dynamic converges to a pure Nash equilibrium in a vanishingly
small fraction of all (large) games when players take turns according to a fixed cyclic
order. By contrast, when the playing sequence is random, the dynamic converges to a
pure Nash equilibrium if one exists in almost all (large) games. |
|---|