Asynchronous Schemes for Stochastic and Misspecified Potential Games and Nonconvex Optimization

• 成果类型: Article
• 署名作者: Lei, Jinlong; Shanbhag, Uday, V
• 署名单位: Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1946
• 发表日期: 2020
• 页码: 1742-1766
• 关键词: stochastic Nash equilibrium problems; potential games; stochastic nonconvex optimization; stochastic approximation

摘要

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 non-convex 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.