Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization

Ian M. Gemp, Luke Marris, G. Piliouras
10/1/2023

No confident code implementation found for this paper. 1 possible match can be shown below.

Abstract

We propose the first loss function for approximate Nash equilibria of normal-form games that is amenable to unbiased Monte Carlo estimation. This construction allows us to deploy standard non-convex stochastic optimization techniques for approximating Nash equilibria, resulting in novel algorithms with provable guarantees. We complement our theoretical analysis with experiments demonstrating that stochastic gradient descent can outperform previous state-of-the-art approaches.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 1 weaker match is hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Enabling First-Order Gradient-Based Learning for Equilibrium Computation in Markets

81% match1 repo242023

Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games

80% match2023

Competitive Gradient Descent

80% match1 repo252019

A survey on algorithms for Nash equilibria in finite normal-form games

79% match2023

Learning to Play Stochastic Two-player Perfect-Information Games without Knowledge

79% match2023

Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games

79% match2023

Cite this paper

@article{gemp2023approximating,
  title  = {Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization},
  author = {Ian M. Gemp and Luke Marris and G. Piliouras},
  year   = {2023},
  eprint = {2310.06689},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/pdf/2310.06689},
  journal = {ICLR 2023 2023}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2310.06689.svg)](https://codeofpaper.com/paper/2310.06689)

Discussion