Semidecentralized Zeroth-Order Algorithms for Stochastic Generalized Nash Equilibrium Seeking

In this article, we address the problem of stochastic generalized Nash equilibrium (SGNE) seeking, where a group of noncooperative heterogeneous players aim at minimizing their expected cost under some unknown stochastic effects. Each player's strategy is constrained to a convex and compact set and should satisfy some global affine constraints. In order to decouple players' strategies under the global constraints, an extra player is introduced aiming at minimizing the violation of the coupling constraints, which transforms the original SGNE problems to extended stochastic Nash equilibrium problems. Due to the unknown stochastic effects in the objective, the gradient of the objective function is infeasible and only noisy objective values are observable. Instead of gradient-based methods, a semidecentralized zeroth-order method is developed to achieve the SGNE under a two-point gradient estimation. The convergence proof is provided for strongly monotone stochastic generalized games. We demonstrate the proposed algorithm through the Cournot model for resource allocation problems.