Machine Learning and Strategic Agents: Dynamics and Algorithm Design

Machine learning algorithms are increasingly being deployed into environments in which they must contend with other strategic agents with potentially misaligned objectives. The presence of these other agents breaks many of the underlying assumptions on which machine learning algorithms are built and can cause non-stationarity in the environment that can give rise to surprising dynamics and behaviors. In this talk, we will explore the challenges and opportunities available to algorithm designers in such scenarios and show how one can take advantage of the game theoretic interactions in the environment to give performance and convergence guarantees to game theoretically meaningful solutions. In particular, we will focus on two sets of problems: 1. a dynamic model of strategic classification in which a learner seeks to train a machine learning in the presence of adaptive agents and 2. matching markets where individual agents attempt to learn their most preferred match while competing with other agents over firms. In strategic classification we will show that the presence of strategic agents means that the learning rate or speed of learning becomes a design choice that can be used to select for different equilibria. In matching markets we will design a family of algorithms that allow agents to optimally learn in structured matching markets while competing with other agents even without full observation of the market. Both of these results suggest that dealing with game theoretic interactions requires re-evaluating long-standing assumptions underlying in machine learning, but that if one can leverage the underlying game theoretic structure, one can still give strong performance guarantees.