Multiplayer Performative Prediction: Learning in Decision-Dependent Games
Adhyyan Narang, Evan Faulkner, Dmitriy Drusvyatskiy, Maryam Fazel, Lillian J. Ratliff; 24(202):1−56, 2023.
Abstract
This paper introduces a new game theoretic framework called multi-player performative prediction to address learning problems with feedback mechanisms where the population data reacts to competing decision makers’ actions. The focus is on two solution concepts: performatively stable equilibria and Nash equilibria. While Nash equilibria provide more informative solutions, they are computationally difficult to find due to being solutions of non-monotone games. Under mild assumptions, the paper shows that performatively stable equilibria can be efficiently found using various algorithms, such as repeated retraining and the repeated (stochastic) gradient method. Transparent sufficient conditions for strong monotonicity of the game are established to develop algorithms for finding Nash equilibria. Derivative free methods and adaptive gradient algorithms are investigated, where each player alternates between learning a parametric description of their distribution and gradient steps on the empirical risk. Synthetic and semi-synthetic numerical experiments are conducted to illustrate the results.
[abs]