Optimization Online


Computation of Stochastic Nash Equilibrium via Variable Sample Distributed Methods

Dali Zhang(dali.zhang***at***outlook.com)
Lizhi Wang(lzwang***at***iastate.edu)
Ming Dong(mdong***at***sjtu.edu.cn)

Abstract: In this paper, we propose a variable sample distributed algorithm for the computation of stochastic Nash equilibrium in which the objective functions are replaced, at each iteration, by sample average approximations. We investigate the contraction mapping properties of the variable sample distributed algorithm and show that the accuracy of estimators yielded in the algorithms to their true counterparts are determined by both the sample size schedules and the contraction mapping parameters. We also investigate conditions on the sample size schedule under which the accumulation point generated by the algorithm asymptotically converges to the true Nash equilibrium. In the numerical tests, we comparatively analyze the accuracy and precision errors of estimators with different sample size schedules with respect to the sampling loads and the computational times. Finally, we present numerical results on the effectiveness of different cumulative sampling schemes for the algorithm.

Keywords: Monte Carlo methods, distributed algorithm; stochastic Nash equilibrium

Category 1: Stochastic Programming

Category 2: Other Topics (Game Theory )


Download: [PDF]

Entry Submitted: 11/18/2013
Entry Accepted: 11/18/2013
Entry Last Modified: 11/18/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society