Related papers: Swim till You Sink: Computing the Limit of a Game

Swim till You Sink: Computing the Limit of a Game

URL: http://arxiv.org/abs/2408.11146v1
Date: Tue, 20 Aug 2024 19:09:21 GMT
Title: Swim till You Sink: Computing the Limit of a Game
Authors: Rashida Hakim, Jason Milionis, Christos Papadimitriou, Georgios Piliouras,
Abstract summary: We study the problem of computing the behavior of a class of natural dynamics called the noisy replicator dynamics. We show through experiments that the limit distribution of reasonably large games can be estimated quite accurately through sampling and simulation.
Score: 26.785274326413585
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: During 2023, two interesting results were proven about the limit behavior of game dynamics: First, it was shown that there is a game for which no dynamics converges to the Nash equilibria. Second, it was shown that the sink equilibria of a game adequately capture the limit behavior of natural game dynamics. These two results have created a need and opportunity to articulate a principled computational theory of the meaning of the game that is based on game dynamics. Given any game in normal form, and any prior distribution of play, we study the problem of computing the asymptotic behavior of a class of natural dynamics called the noisy replicator dynamics as a limit distribution over the sink equilibria of the game. When the prior distribution has pure strategy support, we prove this distribution can be computed efficiently, in near-linear time to the size of the best-response graph. When the distribution can be sampled -- for example, if it is the uniform distribution over all mixed strategy profiles -- we show through experiments that the limit distribution of reasonably large games can be estimated quite accurately through sampling and simulation.

Related papers

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)
Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
arXiv Detail & Related papers (2022-08-22T08:31:46Z)
Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics [28.815822236291392]
We show that no game dynamics can converge to $epsilon$-Nash equilibria. We also prove a stronger result for $epsilon$-approximate Nash equilibria.
arXiv Detail & Related papers (2022-03-26T18:27:40Z)
Provably convergent quasistatic dynamics for mean-field two-player zero-sum games [10.39511271647025]
We consider a quasistatic Wasserstein gradient flow dynamics in which one probability distribution follows the Wasserstein gradient flow, while the other one is always at the equilibrium. Inspired by the continuous dynamics of probability distributions, we derive a quasistatic Langevin gradient descent method with inner-outer iterations.
arXiv Detail & Related papers (2022-02-15T20:19:42Z)
Multiplayer Performative Prediction: Learning in Decision-Dependent Games [18.386569111954213]
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.
arXiv Detail & Related papers (2022-01-10T15:31:10Z)
Online Learning in Periodic Zero-Sum Games [27.510231246176033]
We show that Poincar'e recurrence provably generalizes despite the complex, non-autonomous nature of these dynamical systems.
arXiv Detail & Related papers (2021-11-05T10:36:16Z)
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)
Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
We present volume analyses of Multiplicative Weights Updates (MWU) and Optimistic Multiplicative Weights Updates (OMWU) in zero-sum as well as coordination games. We show that OMWU contracts volume, providing an alternative understanding for its known convergent behavior. We also prove a no-free-lunch type of theorem, in the sense that when examining coordination games the roles are reversed: OMWU expands volume exponentially fast, whereas MWU contracts.
arXiv Detail & Related papers (2020-05-28T13:47:09Z)
From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization [49.368421783733815]
We show how adapting the reward can give strong convergence guarantees in monotone games. We also show how this reward adaptation technique can be leveraged to build algorithms that converge exactly to the Nash equilibrium.
arXiv Detail & Related papers (2020-02-19T21:36:58Z)

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