Approximating N-Player Nash Equilibrium through Gradient Descent
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913637103304704 |
|---|---|
| author | Wang, Dongge Yan, Xiang Dou, Zehao Huang, Wenhan Yang, Yaodong Deng, Xiaotie |
| author_facet | Wang, Dongge Yan, Xiang Dou, Zehao Huang, Wenhan Yang, Yaodong Deng, Xiaotie |
| contents | Decoding how rational agents should behave in shared systems remains a critical challenge within theoretical computer science, artificial intelligence and economics studies. Central to this challenge is the task of computing the solution concept of games, which is Nash equilibrium (NE). Although computing NE in even two-player cases are known to be PPAD-hard, approximation solutions are of intensive interest in the machine learning domain. In this paper, we present a gradient-based approach to obtain approximate NE in N-player general-sum games. Specifically, we define a distance measure to an NE based on pure strategy best response, thereby computing an NE can be effectively transformed into finding the global minimum of this distance function through gradient descent. We prove that the proposed procedure converges to NE with rate $O(1/T)$ ($T$ is the number of iterations) when the utility function is convex. Experimental results suggest our method outperforms Tsaknakis-Spirakis algorithm, fictitious play and regret matching on various types of N-player normal-form games in GAMUT. In addition, our method demonstrates robust performance with increasing number of players and number of actions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_03001 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximating N-Player Nash Equilibrium through Gradient Descent Wang, Dongge Yan, Xiang Dou, Zehao Huang, Wenhan Yang, Yaodong Deng, Xiaotie Computer Science and Game Theory Decoding how rational agents should behave in shared systems remains a critical challenge within theoretical computer science, artificial intelligence and economics studies. Central to this challenge is the task of computing the solution concept of games, which is Nash equilibrium (NE). Although computing NE in even two-player cases are known to be PPAD-hard, approximation solutions are of intensive interest in the machine learning domain. In this paper, we present a gradient-based approach to obtain approximate NE in N-player general-sum games. Specifically, we define a distance measure to an NE based on pure strategy best response, thereby computing an NE can be effectively transformed into finding the global minimum of this distance function through gradient descent. We prove that the proposed procedure converges to NE with rate $O(1/T)$ ($T$ is the number of iterations) when the utility function is convex. Experimental results suggest our method outperforms Tsaknakis-Spirakis algorithm, fictitious play and regret matching on various types of N-player normal-form games in GAMUT. In addition, our method demonstrates robust performance with increasing number of players and number of actions. |
| title | Approximating N-Player Nash Equilibrium through Gradient Descent |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2501.03001 |