The Replicator Dynamic, Chain Components and the Response Graph

Oliver Biggar, Iman Shames
Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:237-258, 2023.

Abstract

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 \emph{response graph}. We settle an open problem establishing that under the replicator, \emph{sink chain components}—a topological notion of long-run outcome of a dynamical system—always exist and are approximated by the \emph{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 \emph{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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v201-biggar23a, title = {The Replicator Dynamic, Chain Components and the Response Graph}, author = {Biggar, Oliver and Shames, Iman}, booktitle = {Proceedings of The 34th International Conference on Algorithmic Learning Theory}, pages = {237--258}, year = {2023}, editor = {Agrawal, Shipra and Orabona, Francesco}, volume = {201}, series = {Proceedings of Machine Learning Research}, month = {20 Feb--23 Feb}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v201/biggar23a/biggar23a.pdf}, url = {https://proceedings.mlr.press/v201/biggar23a.html}, abstract = {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 \emph{response graph}. We settle an open problem establishing that under the replicator, \emph{sink chain components}—a topological notion of long-run outcome of a dynamical system—always exist and are approximated by the \emph{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 \emph{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.} }
Endnote
%0 Conference Paper %T The Replicator Dynamic, Chain Components and the Response Graph %A Oliver Biggar %A Iman Shames %B Proceedings of The 34th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Shipra Agrawal %E Francesco Orabona %F pmlr-v201-biggar23a %I PMLR %P 237--258 %U https://proceedings.mlr.press/v201/biggar23a.html %V 201 %X 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 \emph{response graph}. We settle an open problem establishing that under the replicator, \emph{sink chain components}—a topological notion of long-run outcome of a dynamical system—always exist and are approximated by the \emph{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 \emph{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.
APA
Biggar, O. & Shames, I.. (2023). The Replicator Dynamic, Chain Components and the Response Graph. Proceedings of The 34th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 201:237-258 Available from https://proceedings.mlr.press/v201/biggar23a.html.

Related Material