The Invisible Hand of Stability

Speaker: Geelon So, ETH Zürich
Series: Machine learning theory

The division of labor enables us to build complex human and machine systems. Today, decentralized multi-agent systems with learned behavior are becoming more prevalent. At the same time, decentralization can come with a costly price of anarchy—agents learn to behave in ways that leave everyone worse off. Can we understand and guard against collectively irrational behavior? In this work, we formalize a close relationship between rationality (Pareto optimality) and learnability (uniform stability) for mixed Nash equilibria. This result can be understood by analogy with optimization. When optimizing a smooth objective, learning dynamics like gradient descent can in principle converge to any critical point. But, the dynamics exhibit stable convergence only around local minima. A similar story plays out in the multi-agent setting: standard learning dynamics can in principle persist at any Nash equilibrium. But, the mixed Nash equilibria that are robustly learnable are the ones that are strategically Pareto optimal. Thus, we recover a form of Adam Smith’s Invisible Hand. Individually utility-seeking dynamics behave as if the players were collectively rational. This is joint work with Yi-An Ma.