Multiplayer Performative Prediction: Learning in Decision-Dependent Games

• URL: http://arxiv.org/abs/2201.03398v1
• Date: Mon, 10 Jan 2022 15:31:10 GMT
• Title: Multiplayer Performative Prediction: Learning in Decision-Dependent Games
• Authors: Adhyyan Narang and Evan Faulkner and Dmitriy Drusvyatskiy and Maryam Fazel and Lillian J. Ratliff
• Abstract summary: This paper formulates a new game theoretic framework for multi-player performative prediction. We focus on two distinct solution concepts, namely (i) performatively stable equilibria and (ii) Nash equilibria of the game. We show that under mild assumptions, the performatively stable equilibria can be found efficiently by a variety of algorithms.
• Score: 18.386569111954213
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning problems commonly exhibit an interesting feedback mechanism wherein the population data reacts to competing decision makers' actions. This paper formulates a new game theoretic framework for this phenomenon, called multi-player performative prediction. We focus on two distinct solution concepts, namely (i) performatively stable equilibria and (ii) Nash equilibria of the game. The latter equilibria are arguably more informative, but can be found efficiently only when the game is monotone. We show that under mild assumptions, the performatively stable equilibria can be found efficiently by a variety of algorithms, including repeated retraining and repeated (stochastic) gradient play. We then establish transparent sufficient conditions for strong monotonicity of the game and use them to develop algorithms for finding Nash equilibria. We investigate derivative free methods and adaptive gradient algorithms wherein each player alternates between learning a parametric description of their distribution and gradient steps on the empirical risk. Synthetic and semi-synthetic numerical experiments illustrate the results.

Related papers

• No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes [11.846329468283583]
  This paper investigates the challenge of learning in black-box games, where the underlying utility function is unknown to any of the agents. We provide a no-regret learning algorithm that utilizes Gaussian processes to identify the equilibrium in such games.
  arXiv  Detail & Related papers  (2024-05-14T04:58:23Z)
• A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
  We investigate learning the equilibria in non-stationary multi-agent systems. We show how to test for various types of equilibria by a black-box reduction to single-agent learning.
  arXiv  Detail & Related papers  (2023-06-12T23:48:24Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  We characterize the convergence of optimistic gradient descent (OGD) in time-varying games. Our framework yields sharp convergence bounds for the equilibrium gap of OGD in zero-sum games. We also provide new insights on dynamic regret guarantees in static games.
  arXiv  Detail & Related papers  (2023-01-26T17:25:45Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  Two-team zero-sum games are defined as multi-player games where players are split into two competing sets of agents. We focus on the solution concept of Nash equilibria (NE) We show that computing NE for this class of games is $textithard$ for the complexity class $mathrm$.
  arXiv  Detail & Related papers  (2021-11-07T21:15:35Z)
• Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
  We propose a general meta learning approach to computing approximate Nash equilibrium for finite $n$-player normal-form games. Unlike existing solutions that approximate or learn a Nash equilibrium from scratch for each of the games, our meta solver directly constructs a mapping from a game utility matrix to a joint strategy profile.
  arXiv  Detail & Related papers  (2021-08-17T07:06:46Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  It remains vastly open how to learn the Stackelberg equilibrium in general-sum games efficiently from samples. This paper initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium in two-player turn-based general-sum games.
  arXiv  Detail & Related papers  (2021-02-23T05:11:07Z)
• Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
  We look at algorithms that ensure strong performance in hindsight relative to what could have been achieved with modified behavior. We develop and advocate for this hindsight framing of learning in general sequential decision-making settings. We present examples illustrating the distinct strengths and weaknesses of each type of equilibrium in the literature.
  arXiv  Detail & Related papers  (2020-12-10T18:30:21Z)
• No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
  We study the dynamics of "follow-the-regularized-leader" (FTRL) We show that any Nash equilibrium which is not strict cannot be stable and attracting under FTRL. This result has significant implications for predicting the outcome of a learning process.
  arXiv  Detail & Related papers  (2020-10-19T13:49:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.