Davide Legacci

Abstract

 

Multi-agent learning studies how adaptive agents should act when their environment changes in response to the behavior of others. When interests align, potential games provide a robust framework with strong convergence guarantees for standard learning dynamics. When interests conflict, two-player zero-sum games are traditionally taken as the canonical model.

 

Yet, despite its central role, the zero-sum paradigm offers only a narrow model of competition: zero-sumness is not strategically robust, and the classical two-player minimax structure does not extend to genuinely multi-player interactions. Harmonic games, introduced by Candogan et al. (2011) as the orthogonal complement of potential games, overcome these limitations and provide a strategically robust generalization of competition to N-player games. This thesis studies their equilibrium geometry and learning dynamics, and extends the underlying notion of strategic circulation from finite to continuous games.

 

The equilibrium structure of harmonic games combines the absence of familiar pure stabilization mechanisms with complex mixed-equilibrium targets, making the class intrinsically challenging for learning. This difficulty is reflected in the long-run behavior of continuous-time FTRL dynamics, which exhibit Poincaré recurrence: almost every trajectory returns arbitrarily close to its initial condition infinitely often.

 

To stabilize these oscillations, the thesis introduces FTRL+, a general template for extrapolated learning. Its one-step analysis identifies two abstract energy-control conditions under which (a) every trajectory converges in last iterate to the Nash set while (b) every player incurs bounded cumulative regret in harmonic self-play. These conditions can be enforced either by a suitably tuned constant learning rate or, more importantly, by a decentralized adaptive policy requiring no prior knowledge of game parameters, and retaining an order-optimal O(T^{1/2}) regret guarantee against arbitrary payoff streams.

 

Finally, the thesis extends the theory of strategic competition beyond finite games. Using Riemannian methods, it translates the combinatorial circulation law underlying harmonic games into a smooth counterpart, defining the class of conservative games on continuous strategy spaces.

 

In a suitable Hessian geometry, mirror flows in this class preserve Riemannian volume and exhibit Poincaré recurrence. A novel compactification of the strategy manifold then enables a smooth Hodge-theoretic decomposition of continuous games into potential and conservative components: this recovers the finite potential--harmonic theory while accommodating nonlinear payoffs and general constrained strategy spaces.

 

Taken together, these results develop a geometric theory of competitive multi-agent learning: they identify when circulating incentives prevent vanilla no-regret dynamics from settling, and show how extrapolation and adaptivity can restore convergence.