Asynchronous schemes for stochastic and misspecified potential games and nonconvex optimization
From MaRDI portal
Abstract: The distributed computation of equilibria and optima has seen growing interest in a broad collection of networked problems. We consider the computation of equilibria of convex stochastic Nash games characterized by a possibly nonconvex potential function. Our focus is on two classes of stochastic Nash games: (P1): A potential stochastic Nash game, in which each player solves a parameterized stochastic convex program; and (P2): A misspecified generalization, where the player-specific stochastic program is complicated by a parametric misspecification. In both settings, exact proximal BR solutions are generally unavailable in finite time since they necessitate solving parameterized stochastic programs. Consequently, we design two asynchronous inexact proximal BR schemes to solve the problems, where in each iteration a single player is randomly chosen to compute an inexact proximal BR solution with rivals' possibly outdated information. Yet, in the misspecified regime (P2), each player possesses an extra estimate of the misspecified parameter and updates its estimate by a projected stochastic gradient (SG) algorithm. By Since any stationary point of the potential function is a Nash equilibrium of the associated game, we believe this paper is amongst the first ones for stochastic nonconvex (but block convex) optimization problems equipped with almost-sure convergence guarantees. These statements can be extended to allow for accommodating weighted potential games and generalized potential games. Finally, we present preliminary numerics based on applying the proposed schemes to congestion control and Nash-Cournot games.
Recommendations
- On synchronous, asynchronous, and randomized best-response schemes for stochastic Nash games
- Asynchronous algorithms in non-cooperative games
- Distributed variable sample-size gradient-response and best-response schemes for stochastic Nash equilibrium problems
- Asynchronous networked aggregative games
- Distributed computation of equilibria in monotone Nash games via iterative regularization techniques
Cites work
- A class of gap functions for variational inequalities
- A survey of static and dynamic potential games
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- An operator splitting approach for distributed generalized Nash equilibria computation
- Block stochastic gradient iteration for convex and nonconvex optimization
- Broadcast Gossip Algorithms for Consensus
- Convergence of a block coordinate descent method for nondifferentiable minimization
- Convex optimization: algorithms and complexity
- Decentralized Convergence to Nash Equilibria in Constrained Deterministic Mean Field Control
- Decomposition algorithms for generalized potential games
- Delayed-response strategies in repeated games with observation lags
- Distributed algorithms for aggregative games on graphs
- Distributed Computation of Equilibria in Misspecified Convex Stochastic Nash Games
- Distributed computation of equilibria in monotone Nash games via iterative regularization techniques
- Distributed Learning for Stochastic Generalized Nash Equilibrium Problems
- Distributed Nash Equilibrium Seeking by a Consensus Based Approach
- Distributed Nash equilibrium seeking: a gossip-based algorithm
- Distributed robust adaptive equilibrium computation for generalized convex games
- Dynamics in near-potential games
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Equilibrium points in n -person games
- Exploiting problem structure in optimization under uncertainty via online convex optimization
- scientific article; zbMATH DE number 5454133 (Why is no real title available?)
- scientific article; zbMATH DE number 1233801 (Why is no real title available?)
- scientific article; zbMATH DE number 1243371 (Why is no real title available?)
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Learning the demand function in a repeated Cournot oligopoly game
- Lectures on Stochastic Programming
- MIMO Cognitive Radio: A Game Theoretical Approach
- Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
- Nash equilibria: the variational approach
- Nonlinear dynamics in the Cournot model without full information
- On synchronous, asynchronous, and randomized best-response schemes for stochastic Nash games
- On the solution of stochastic optimization and variational problems in imperfect information regimes
- On variance reduction for stochastic smooth convex optimization with multiplicative noise
- Potential games
- Rate control for communication networks: shadow prices, proportional fairness and stability
- Rationalizable Strategic Behavior
- Rationalizable Strategic Behavior and the Problem of Perfection
- Regularized Iterative Stochastic Approximation Methods for Stochastic Variational Inequality Problems
- Sample size selection in optimization methods for machine learning
- Self-Tuned Stochastic Approximation Schemes for Non-Lipschitzian Stochastic Multi-User Optimization and Nash Games
- Sensitivity Analysis in Variational Inequalities
- Two-stage non-cooperative games with risk-averse players
Cited in
(8)- Relaxation techniques and asynchronous algorithms for on-line computation of non-cooperative equilibria
- Differentially private distributed algorithms for stochastic aggregative games
- On the computation of equilibria in monotone and potential stochastic hierarchical games
- Asynchronous variance-reduced block schemes for composite non-convex stochastic optimization: block-specific steplengths and adapted batch-sizes
- Distributed variable sample-size gradient-response and best-response schemes for stochastic Nash equilibrium problems
- On synchronous, asynchronous, and randomized best-response schemes for stochastic Nash games
- Equilibrium analysis of distributed aggregative game with misinformation.
- A distributed iterative Tikhonov method for networked monotone stochastic and hierarchical aggregative games
This page was built for publication: Asynchronous schemes for stochastic and misspecified potential games and nonconvex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144794)
