We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Asynchronous Schemes for Stochastic and Misspecified Potential Games and Nonconvex Optimization.
- Authors
Lei, Jinlong; Shanbhag, Uday V.
- Abstract
In "Asynchronous Schemes for Stochastic and Misspecified Potential Games and Nonconvex Optimization," Lei and Shanbhag consider a class of convex stochastic Nash games, possibly corrupted by parametric misspecification and characterized by a possibly nonconvex potential function. The authors present an asynchronous inexact proximal best-response (BR) scheme in which, at any step, a randomly selected player computes an inexact BR step (via stochastic approximation) and other players keep their strategies invariant. Misspecification is addressed by a simultaneous learning process reliant on an increasing batch size of sampled gradients. Almost-sure convergence guarantees are provided to the set of Nash equilibria, and such claims can be extended to delay-afflicted regimes, generalized potential games (with coupled strategy sets), and weighted potential games. In fact, equilibria of this potential game are stationary points of the potential function and asynchronous inexact BR schemes are, in essence, randomized block-coordinate schemes for a subclass of stochastic nonconvex optimization problems. The distributed computation of equilibria and optima has seen growing interest in a broad collection of networked problems. We consider the computation of Nash equilibria of convex stochastic noncooperative games characterized by a possibly nonconvex potential function. Since any stationary point of the potential function is a Nash equilibrium, there is an equivalence between asynchronous best-response (BR) schemes applied on a noncooperative game and block-coordinate descent (BCD) schemes implemented on the associated potential function. We focus on two classes of such games: (Problem 1): a potential game, in which each player solves a parameterized stochastic convex program, and (Problem 2): a misspecified generalization, in which the player-specific stochastic program is complicated by a parametric misspecification with the unknown parameter being the solution to a stochastic convex optimization problem. In both settings, exact proximal BR solutions are generally unavailable in finite time because they necessitate solving stochastic programs. Consequently, we design two asynchronous inexact proximal BR schemes to solve Problems 1 and 2, respectively, in which in each iteration, a single player is randomly chosen to compute an inexact proximal BR solution (via stochastic approximation) with delayed rival information while the other players keep their strategies invariant. In the misspecified regime (Problem 2), each player possesses an extra estimate of the misspecified parameter by using a projected stochastic gradient algorithm with an increasing batch of sampled gradients. By imposing suitable conditions on the inexactness sequences, we prove that the iterates produced by both schemes converge almost surely to a connected subset of the set of Nash equilibria. When the player-specific problems are strongly convex, an inexact pure BR scheme (without a proximal term) is shown to be convergent. In effect, we provide what we believe is among the first randomized BCD schemes for stochastic nonconvex (but block-wise convex) optimization with almost sure convergence properties. We further show that the associated gap function converges to zero in mean. These statements can be extended to allow for accommodating weighted potential games and generalized potential games. Finally, we present preliminary numerics by applying the proposed schemes to congestion control and Nash–Cournot competition.
- Subjects
NONCOOPERATIVE games (Mathematics); NASH equilibrium; POTENTIAL functions; STOCHASTIC approximation
- Publication
Operations Research, 2020, Vol 68, Issue 6, p1742
- ISSN
0030-364X
- Publication type
Article
- DOI
10.1287/opre.2019.1946