Asynchronous Schemes for Stochastic and Misspecified Potential Games and Nonconvex Optimization

Jinlong Lei () and Uday V. Shanbhag ()
Additional contact information
Jinlong Lei: Department of Industrial and Manufacturing Engineering, Pennsylvania State University, State College, Pennsylvania 16801
Uday V. Shanbhag: Department of Industrial and Manufacturing Engineering, Pennsylvania State University, State College, Pennsylvania 16801

Operations Research, 2020, vol. 68, issue 6, 1742-1766

Abstract: 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.

Keywords: stochastic Nash equilibrium problems; potential games; stochastic nonconvex optimization; stochastic approximation (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1946 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:68:y:2020:i:6:p:1742-1766

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().