The Replicator Dynamic, Chain Components and the Response Graph
This work addresses a theoretical problem in game theory and dynamical systems, providing foundational insights into long-run outcomes, but it is incremental as it builds on existing concepts like the replicator dynamic and response graphs.
The paper tackles the relationship between the replicator dynamic, chain components, and a game's response graph, establishing that sink chain components always exist and are approximated by sink connected components of the response graph, with specific results for two-player zero-sum and potential games.
In this paper we examine the relationship between the flow of the replicator dynamic, the continuum limit of Multiplicative Weights Update, and a game's response graph. We settle an open problem establishing that under the replicator, sink chain components -- a topological notion of long-run outcome of a dynamical system -- always exist and are approximated by the sink connected components of the game's response graph. More specifically, each sink chain component contains a sink connected component of the response graph, as well as all mixed strategy profiles whose support consists of pure profiles in the same connected component, a set we call the content of the connected component. As a corollary, all profiles are chain recurrent in games with strongly connected response graphs. In any two-player game sharing a response graph with a zero-sum game, the sink chain component is unique. In two-player zero-sum and potential games the sink chain components and sink connected components are in a one-to-one correspondence, and we conjecture that this holds in all games.