  The goal in this paper is to approximate the Price of Stability (PoS) in
stochastic Nash games using stochastic approximation (SA) schemes. PoS is
amongst the most popular metrics in game theory and provides an avenue for
estimating the efficiency of Nash games. In particular, knowing the value of
PoS can help with designing efficient networked systems, including
transportation networks and power market mechanisms. Motivated by the lack of
efficient methods for computing the PoS, first we consider stochastic
optimization problems with a nonsmooth and merely convex objective function and
a merely monotone stochastic variational inequality (SVI) constraint. This
problem appears in the numerator of the PoS ratio. We develop a randomized
block-coordinate stochastic extra-(sub)gradient method where we employ a novel
iterative penalization scheme to account for the mapping of the SVI in each of
the two gradient updates of the algorithm. We obtain an iteration complexity of
the order $\epsilon^{-4}$ that appears to be best known result for this class
of constrained stochastic optimization problems, where $\epsilon$ denotes an
arbitrary bound on suitably defined infeasibility and suboptimality metrics.
Second, we develop an SA-based scheme for approximating the PoS and derive
lower and upper bounds on the approximation error. To validate the theoretical
findings, we provide preliminary simulation results on a networked stochastic
Nash Cournot competition.
