Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games
From MaRDI portal
Abstract: In this paper, we consider stochastic monotone Nash games where each player's strategy set is characterized by possibly a large number of explicit convex constraint inequalities. The majority of the existing methods for solving this class of constrained problems rely on employing projected stochastic approximation (SA) methods. However, the projected SA methods perform poorly when the constraint set is afflicted by the presence of a large number of possibly nonlinear functional inequalities. Motivated by the absence of performance guarantees for computing the Nash equilibrium in constrained games, we develop a single timescale randomized Lagrangian multiplier stochastic approximation method where in the primal space, we employ an SA scheme, and in the dual space, we employ a randomized block-coordinate scheme where only a randomly selected Lagrangian multiplier is updated. We derive a convergence rate of for suitably defined suboptimality and infeasibility metrics in a mean sense.
Recommendations
- Paths to constrained Nash equilibria
- On synchronous, asynchronous, and randomized best-response schemes for stochastic Nash games
- Stochastic approximation for estimating the price of stability in stochastic Nash games
- Soft-constrained stochastic Nash games for weakly coupled large-scale systems
- Accelerated iterations for finding the soft-constrained stochastic Nash games equilibrium
Cites work
- A fast stochastic approximation-based subgradient extragradient algorithm with variance reduction for solving stochastic variational inequality problems
- A Generalized Proximal Point Algorithm for the Variational Inequality Problem in a Hilbert Space
- A method with convergence rates for optimization problems with variational inequality constraints
- A primal-dual algorithm with line search for general convex-concave saddle point problems
- Accelerated stochastic algorithms for convex-concave saddle-point problems
- Accelerating block-decomposition first-order methods for solving composite saddle-point and two-player Nash equilibrium problems
- An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems
- An accelerated non-Euclidean hybrid proximal extragradient-type algorithm for convex-concave saddle-point problems
- An existence theorem for the complementarity problem
- An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities
- Convergence Rates in Forward--Backward Splitting
- Distributed computation of equilibria in monotone Nash games via iterative regularization techniques
- Dual variational inequalities
- Engineering and Economic Applications of Complementarity Problems
- Extragradient Method with Variance Reduction for Stochastic Variational Inequalities
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- Game-Theoretic Power Allocation and the Nash Equilibrium Analysis for a Multistatic MIMO Radar Network
- Generalized Nash equilibrium problems
- scientific article; zbMATH DE number 3511879 (Why is no real title available?)
- scientific article; zbMATH DE number 3534286 (Why is no real title available?)
- Lagrangian Duality and Related Multiplier Methods for Variational Inequality Problems
- Learning generalized Nash equilibria in monotone games: a hybrid adaptive extremum seeking control approach
- Monotone (nonlinear) operators in Hilbert space
- Non-cooperative games
- On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems
- On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemes
- On the ergodic convergence rates of a first-order primal-dual algorithm
- Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Proximal extrapolated gradient methods for variational inequalities
- Regularized Iterative Stochastic Approximation Methods for Stochastic Variational Inequality Problems
- Robust Stochastic Approximation Approach to Stochastic Programming
- Smooth methods of multipliers for complementarity problems
- Solving variational inequalities with stochastic mirror-prox algorithm
- Stochastic Approximation Approaches to the Stochastic Variational Inequality Problem
- Subgradient methods for saddle-point problems
- The Approximation of Fixed Points of a Continuous Mapping
- Theory of games and economic behavior.
- Using EPECs to Model Bilevel Games in Restructured Electricity Markets with Locational Prices
- Variance-based extragradient methods with line search for stochastic variational inequalities
Cited in
(2)
This page was built for publication: Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6191973)
