PRIN Grant 2022R45NBB (2023-2025) “Targeted Learning Dynamics: Computing Efficient and Fair Equilibria through No-Regret Algorithms"

Abstract

The majority of modern machine learning (ML) methods are built with the goal of optimizing the objective function of a single agent,
under the assumption that the application environment is isolated, and not affected by the behavior of the ML system. However, in
the coming years, complex ecologies of ML systems are likely to proliferate: in consumer and financial markets, in autonomous
driving scenarios, in cyber and physical security, and in smart cities. In such settings, ML systems cannot make decisions ``in the
vacuum’’, ignoring the presence of other artificial agents and humans that interact in the same environment. Indeed, ML systems
should aim at finding an equilibrium point that takes into account all the objectives of the participants, who can be viewed as players
in a common game.
The leading paradigm to compute equilibrium points in complex multi-player games is to employ decentralized learning dynamics,
which offer a parallel and scalable avenue for the computation of equilibria. We argue that there is one key limitation to the current
learning dynamics available for equilibrium learning: they guarantee that the collective behavior will converge to one equilibrium
point, but they do not provide any guarantee on the quality or properties of such a point. ML systems need to overcome this
limitation, in order to guarantee outcomes which are optimal with respect to some relevant objective. The goal of this project is to
develop decentralized learning dynamics with guarantees on their solution quality, with a particular focus on building learning
algorithms that can guarantee fair and socially good equilibrium outcomes even in presence of strategic behaviors. We are planning
to explore the application of such techniques to routing problems and repeated auctions problems, which are both relevant for
industrial applications.