Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Stochastic Approximation for Estimating the Price of Stability in
  Stochastic Nash Games   The goal in this paper is to estimate the Price of Stability (PoS) for
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 significantly with designing efficient networked systems,
including transportation networks and power market mechanisms. Motivated by the
lack of efficient methods for estimating 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. 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. Second, we develop an SA-based
algorithm to estimate the PoS. In particular, combining the proposed
extra-(sub)gradient-based method with a variance reduction technique, we derive
a confidence interval with lower and upper errors of the order
$\frac{1}{\sqrt{k}}$ and $\frac{1}{\sqrt[4]{k}}$, respectively. Such guarantees
appear to be new for estimating the PoS. To validate our theoretical findings,
we provide some preliminary simulation results on a stochastic Nash Cournot
competition over a network.

21
The categories of this paper are: adap-org
10
The categories of this paper are: q-bio
37
The categories of this paper are: supr-con
17
The categories of this paper are: q-fin
14
The categories of this paper are: math-ph
31
The categories of this paper are: ao-sci
32
The categories of this paper are: atom-ph
16
The categories of this paper are: stat
1
The categories of this paper are: cs
11
The categories of this paper are: hep-lat
23
The categories of this paper are: solv-int
36
The categories of this paper are: cmp-lg
34
The categories of this paper are: chem-ph
29
The categories of this paper are: funct-an
35
The categories of this paper are: mtrl-th
28
The categories of this paper are: alg-geom