Journal Article

On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games

Pang, Jong-Shi, Sen, Suvrajeet, Shanbhag, Uday V., Lei, Jinlong

2020

Overview

In this paper, we consider a stochastic Nash game in which each player minimizes a parameterized expectation-valued convex objective function. In deterministic regimes, proximal best-response (BR) schemes have been shown to be convergent under a suitable spectral property associated with the proximal BR map. However, a direct application of this scheme to stochastic settings requires obtaining exact solutions to stochastic optimization problems at each iteration. Instead, we propose an inexact generalization of this scheme in which an inexact solution to the BR problem is computed in an expected-value sense via a stochastic approximation (SA) scheme. On the basis of this framework, we present three inexact BR schemes: (i) First, we propose a synchronous inexact BR scheme where all players simultaneously update their strategies. (ii) Second, we extend this to a randomized setting where a subset of players is randomly chosen to update their strategies while the other players keep their strategies invariant. (iii) Third, we propose an asynchronous scheme, where each player chooses its update frequency while using outdated rival-specific data in updating its strategy. Under a suitable contractive property on the proximal BR map, we proceed to derive almost sure convergence of the iterates to the Nash equilibrium (NE) for (i) and (ii) and mean convergence for (i)–(iii). In addition, we show that for (i)–(iii), the generated iterates converge to the unique equilibrium in mean at a linear rate with a prescribed constant rather than a sublinear rate. Finally, we establish the overall iteration complexity of the scheme in terms of projected stochastic gradient (SG) steps for computing an ɛ -NE 2 (or ɛ -NE ∞ ) and note that in all settings, the iteration complexity is O ( 1 / ɛ 2 ( 1 + c ) + δ ) , where c = 0 in the context of (i), and c > 0 represents the positive cost of randomization in (ii) and asynchronicity and delay in (iii). Notably, in the synchronous regime, we achieve a near-optimal rate from the standpoint of solving stochastic convex optimization problems by SA schemes. The schemes are further extended to settings where players solve two-stage stochastic Nash games with linear and quadratic recourse. Finally, preliminary numerics developed on a multiportfolio investment problem and a two-stage capacity expansion game support the rate and complexity statements.

• Publisher: INFORMS,Institute for Operations Research and the Management Sciences
• Subject: 91A15 / 91A20 / 91B28 / Approximation / best-response schemes / Complexity / Computational geometry / Convergence / Convexity / Exact solutions / Game theory / Games / Iterative methods / Learning models (Stochastic processes) / Mathematical research / noncooperative games / Operations research / Optimization / Players / Primary: 91A10 / Primary: Games/group decisions: noncooperative/stochastic programming: stochastic / Randomization / Stochastic models / stochastic Nash games / stochastic optimization