A Hierarchical Variational Inequality Approach to Generalized Nash Equilibrium Seeking with Nonlinear Shared Constraints
In the authors' words
We study the computation of variational generalized Nash equilibria (v-GNE) in games with strongly monotone pseudo-gradients and nonlinear convex shared constraints. We show that the v-GNE problem is exactly equivalent to a hierarchical variational inequality, whose lower level is given by the gradient of a smooth convex penalty of the constraint violation over the local action sets. Building on this reformulation, we propose a hierarchical regularization scheme that operates entirely in the primal space and requires only projections onto the local action sets. In the centralized setting, we prove last-iterate squared distance convergence to the v-GNE with rate under a local error bound condition, which holds, e.g., under Slater's condition, improved to under a global error bound condition. We then extend the scheme to the partial-decision information setting, where the agents communicate over a network and maintain local estimates of the joint action. We derive a distributed algorithm with a constant stepsize operating in the primal space and converging to the v-GNE with rate .
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.