Variable-sample method for the computation of stochastic Nash equilibrium

This article proposes a variable-sample method for the computation of stochastic stable Nash equilibrium, in which the objective functions are approximated, in each iteration, by the sample average approximation with different sample sizes. We start by investigating the contraction mapping properties under the variable-sample framework. Under some moderate conditions, it is shown that the accumulation points attained from the algorithm satisfy the first-order equilibrium conditions with probability one. Moreover, we use the asymptotic unbiasedness condition to prove the convergence of the accumulation points of the algorithm into the set of fixed points and prove the finite termination property of the algorithm. We also verify that the algorithm converges to the equilibrium even if the optimization problems in each iteration are solved inexactly. In the numerical tests, we comparatively analyze the accuracy error and the precision error of the estimators with different sample size schedules with respect to the sampling loads and the computational times. The results validate the effectiveness of the algorithm.

Automated summary

This article proposes a variable-sample method for computing stochastic stable Nash equilibrium using sample average approximation with different sample sizes. The contraction mapping properties under the variable-sample framework are investigated, and it is shown that the algorithm attains accumulation points that satisfy the equilibrium conditions with probability one under certain conditions. The convergence and termination properties of the algorithm are proven, and numerical tests validate its effectiveness.