Sink equilibria and the attractors of learning in games

Oliver Biggar, Christos H. Papadimitriou
Proceedings of The 37th International Conference on Algorithmic Learning Theory, PMLR 313:1-21, 2026.

Abstract

Characterizing the limit behavior—that is, the attractors—of learning dynamics is one of the most fundamental open questions in game theory. In recent work on this front, it was conjectured that the attractors of the replicator dynamic are in one-to-one correspondence with the sink equilibria of the game—the sink strongly connected components of a game’s preference graph—, and it was established that they do stand in at least one-to-many correspondence with them. Here, we show that the one-to-one conjecture is false. We disprove this conjecture over the course of three theorems: the first disproves a stronger form of the conjecture, while the weaker form is disproved separately in the two-player and $N$-player ($N>2$) cases. By showing how the conjecture fails, we lay out the obstacles that lie ahead for characterizing attractors of the replicator, and introduce new ideas with which to tackle them. All three counterexamples derive from an object called a local source—a point lying within the sink equilibrium, and yet which is ‘locally repelling’; we prove that the absence of local sources is necessary, but not sufficient, for the one-to-one property to be true. We complement this with a sufficient condition: we introduce a local property of a sink equilibrium called pseudoconvexity, and establish that when the sink equilibria of a two-player game are pseudoconvex then they precisely define the attractors. Pseudoconvexity generalizes the previous cases—such as zero-sum games and potential games—where this conjecture was known to hold, and reformulates these cases in terms of a simple graph property.

Cite this Paper

BibTeX
@InProceedings{pmlr-v313-biggar26a, title = {Sink equilibria and the attractors of learning in games}, author = {Biggar, Oliver and Papadimitriou, Christos H.}, booktitle = {Proceedings of The 37th International Conference on Algorithmic Learning Theory}, pages = {1--21}, year = {2026}, editor = {Telgarsky, Matus and Ullman, Jonathan}, volume = {313}, series = {Proceedings of Machine Learning Research}, month = {23--26 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v313/main/assets/biggar26a/biggar26a.pdf}, url = {https://proceedings.mlr.press/v313/biggar26a.html}, abstract = {Characterizing the limit behavior—that is, the attractors—of learning dynamics is one of the most fundamental open questions in game theory. In recent work on this front, it was conjectured that the attractors of the replicator dynamic are in one-to-one correspondence with the sink equilibria of the game—the sink strongly connected components of a game’s preference graph—, and it was established that they do stand in at least one-to-many correspondence with them. Here, we show that the one-to-one conjecture is false. We disprove this conjecture over the course of three theorems: the first disproves a stronger form of the conjecture, while the weaker form is disproved separately in the two-player and $N$-player ($N>2$) cases. By showing how the conjecture fails, we lay out the obstacles that lie ahead for characterizing attractors of the replicator, and introduce new ideas with which to tackle them. All three counterexamples derive from an object called a local source—a point lying within the sink equilibrium, and yet which is ‘locally repelling’; we prove that the absence of local sources is necessary, but not sufficient, for the one-to-one property to be true. We complement this with a sufficient condition: we introduce a local property of a sink equilibrium called pseudoconvexity, and establish that when the sink equilibria of a two-player game are pseudoconvex then they precisely define the attractors. Pseudoconvexity generalizes the previous cases—such as zero-sum games and potential games—where this conjecture was known to hold, and reformulates these cases in terms of a simple graph property.} }
Endnote
%0 Conference Paper %T Sink equilibria and the attractors of learning in games %A Oliver Biggar %A Christos H. Papadimitriou %B Proceedings of The 37th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Matus Telgarsky %E Jonathan Ullman %F pmlr-v313-biggar26a %I PMLR %P 1--21 %U https://proceedings.mlr.press/v313/biggar26a.html %V 313 %X Characterizing the limit behavior—that is, the attractors—of learning dynamics is one of the most fundamental open questions in game theory. In recent work on this front, it was conjectured that the attractors of the replicator dynamic are in one-to-one correspondence with the sink equilibria of the game—the sink strongly connected components of a game’s preference graph—, and it was established that they do stand in at least one-to-many correspondence with them. Here, we show that the one-to-one conjecture is false. We disprove this conjecture over the course of three theorems: the first disproves a stronger form of the conjecture, while the weaker form is disproved separately in the two-player and $N$-player ($N>2$) cases. By showing how the conjecture fails, we lay out the obstacles that lie ahead for characterizing attractors of the replicator, and introduce new ideas with which to tackle them. All three counterexamples derive from an object called a local source—a point lying within the sink equilibrium, and yet which is ‘locally repelling’; we prove that the absence of local sources is necessary, but not sufficient, for the one-to-one property to be true. We complement this with a sufficient condition: we introduce a local property of a sink equilibrium called pseudoconvexity, and establish that when the sink equilibria of a two-player game are pseudoconvex then they precisely define the attractors. Pseudoconvexity generalizes the previous cases—such as zero-sum games and potential games—where this conjecture was known to hold, and reformulates these cases in terms of a simple graph property.
APA
Biggar, O. & Papadimitriou, C.H.. (2026). Sink equilibria and the attractors of learning in games. Proceedings of The 37th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 313:1-21 Available from https://proceedings.mlr.press/v313/biggar26a.html.

Related Material