On the Sampling-based Computation of Nash Equilibria under Uncertainty via the Nikaido-Isoda Function
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_ | 1866908616948187136 |
|---|---|
| author | Marrinan, Luke Yousefian, Farzad Shanbhag, Uday V. |
| author_facet | Marrinan, Luke Yousefian, Farzad Shanbhag, Uday V. |
| contents | We consider the computation of an equilibrium of a stochastic Nash equilibrium problem, where the player objectives are assumed to be $L_0$-Lipschitz continuous and convex given rival decisions with convex and closed player-specific feasibility sets. To address this problem, we consider minimizing a suitably defined value function associated with the Nikaido-Isoda function. Such an avenue does not necessitate either monotonicity properties of the concatenated gradient map or potentiality requirements on the game but does require a suitable regularity requirement under which a stationary point is a Nash equilibrium. We design and analyze a sampling-enabled projected gradient descent-type method, reliant on inexact resolution of a player-level best-response subproblem. By deriving suitable Lipschitzian guarantees on the value function, we derive both asymptotic guarantees for the sequence of iterates as well as rate and complexity guarantees for computing a stationary point by appropriate choices of the sampling rate and inexactness sequence. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_23851 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Sampling-based Computation of Nash Equilibria under Uncertainty via the Nikaido-Isoda Function Marrinan, Luke Yousefian, Farzad Shanbhag, Uday V. Optimization and Control We consider the computation of an equilibrium of a stochastic Nash equilibrium problem, where the player objectives are assumed to be $L_0$-Lipschitz continuous and convex given rival decisions with convex and closed player-specific feasibility sets. To address this problem, we consider minimizing a suitably defined value function associated with the Nikaido-Isoda function. Such an avenue does not necessitate either monotonicity properties of the concatenated gradient map or potentiality requirements on the game but does require a suitable regularity requirement under which a stationary point is a Nash equilibrium. We design and analyze a sampling-enabled projected gradient descent-type method, reliant on inexact resolution of a player-level best-response subproblem. By deriving suitable Lipschitzian guarantees on the value function, we derive both asymptotic guarantees for the sequence of iterates as well as rate and complexity guarantees for computing a stationary point by appropriate choices of the sampling rate and inexactness sequence. |
| title | On the Sampling-based Computation of Nash Equilibria under Uncertainty via the Nikaido-Isoda Function |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2510.23851 |