Stochastic Approximation for Estimating the Price of Stability in Stochastic Nash Games
Stochastic Approximation for Estimating the Price of Stability in Stochastic Nash Games
复制标题
DOI：
10.1145/3632525
复制
发表时间：
2022-03
影响因子：
0.9
通讯作者：
A. Jalilzadeh;Farzad Yousefian;M. Ebrahimi
中科院分区：
文献类型：
--
作者：
A. Jalilzadeh;Farzad Yousefian;M. Ebrahimi
本文的目的是利用随机逼近(SA)方案来逼近随机纳什博弈中的稳定代价。POS是博弈论中最流行的指标之一，为估计纳什博弈的效率提供了一条途径。特别是，评估POS有助于设计高效的联网系统，包括通信网络和电力市场机制。由于缺乏有效的方法来计算POS，我们首先考虑了目标函数为非光滑的单调随机变分不等式(SVI)约束的随机优化问题。这个问题出现在POS比率的分子中。我们提出了一种随机块坐标随机额外(次)梯度方法，其中我们使用了一种新的迭代惩罚方案来考虑算法的两次梯度更新中的SVI映射。对于这类约束随机优化问题，我们得到了一个ϵ-4阶的迭代复杂度，它似乎是这类约束随机优化问题的最好结果，其中ϵ表示适当定义的不可行和次最优度的任意界。其次，我们提出了一种基于SA的方法来逼近POS，并给出了逼近误差的上下界。为了验证理论结果，我们给出了一个网络随机纳什·古诺竞赛的初步模拟结果。
The goal in this article is to approximate the Price of Stability (PoS) in stochastic Nash games using stochastic approximation (SA) schemes. PoS is among the most popular metrics in game theory and provides an avenue for estimating the efficiency of Nash games. In particular, evaluating the PoS can help with designing efficient networked systems, including communication networks and power market mechanisms. Motivated by the absence 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 ϵ -4 that appears to be best known result for this class of constrained stochastic optimization problems, where ϵ 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.