RT Journal Article
SR Electronic
T1 Best reply structure and equilibrium convergence in generic games
JF Science Advances
JO Sci Adv
FD American Association for the Advancement of Science
SP eaat1328
DO 10.1126/sciadv.aat1328
VO 5
IS 2
A1 Pangallo, Marco
A1 Heinrich, Torsten
A1 Doyne Farmer, J.
YR 2019
UL http://advances.sciencemag.org/content/5/2/eaat1328.abstract
AB Game theory is widely used to model interacting biological and social systems. In some situations, players may converge to an equilibrium, e.g., a Nash equilibrium, but in other situations their strategic dynamics oscillate endogenously. If the system is not designed to encourage convergence, which of these two behaviors can we expect a priori? To address this question, we follow an approach that is popular in theoretical ecology to study the stability of ecosystems: We generate payoff matrices at random, subject to constraints that may represent properties of real-world games. We show that best reply cycles, basic topological structures in games, predict nonconvergence of six well-known learning algorithms that are used in biology or have support from experiments with human players. Best reply cycles are dominant in complicated and competitive games, indicating that in this case equilibrium is typically an unrealistic assumption, and one must explicitly model the dynamics of learning.