王中興

（沈陽職業(yè)技術(shù)學(xué)院，遼寧沈陽510665）

?

求解隨機廣義納什均衡問題的樣本均值方法

王中興

（沈陽職業(yè)技術(shù)學(xué)院，遼寧沈陽510665）

研究隨機廣義納什均衡問題.給出了隨機廣義納什均衡問題變分不等式形式的再定式.利用期望殘差最小化方法，獲得了求解該問題的一種新的模型.并通過擬蒙特卡羅方法給出了該模型的求解方法.

隨機廣義納什均衡問題；變分不等式；期望殘差最小化；擬蒙特卡羅

§1　引　言

廣義納什均衡問題（generalized Nash equilibrium problem簡記為GNEP）是標準的納什均衡問題的一種推廣.它考慮每個局中人的決策集都有可能與競爭者的決策集有關(guān)的情形.最近，由于其在不同領(lǐng)域都有著廣泛的應(yīng)用，廣義納什均衡問題引起了眾多學(xué)者的關(guān)注.最早關(guān)于廣義納什均衡問題的研究是由Arrow，Debreu［1］和Debreu［2］給出的，他們把這類問題看作是一類抽象經(jīng)濟.更多的關(guān)于廣義納什均衡問題的研究成果可見［3-6］.

這里廣義納什均衡問題是有N個局中人的非合作博弈問題.以后把第v個局中人簡單的記作v.用nv維向量xv表示局中人v的策略，其中nv為正整數(shù).將所有局中人的策略用向量x =（x1，···，xN）∈Rn表示，其中n = n1+···+ nN，（x1，···，xN）:=（（x1）T，···，（xN）T）T.此外，當(dāng)要強調(diào)局中某一特殊的局中人v時，也常將x表示成x =（xv，x-v），其中x-v為n-nv維向量（x1，···，xv-1，xv+1，···，xN），表示除局中人v以外的所有策略.為方便起見，記n-v= n - nv.廣義納什均衡問題是為了找到一個解x?=（x?，1，···，x?，N），使得其中對每一個v = 1，···，N，x?，v都是以下優(yōu)化問題的解:

其中θv:，都是連續(xù)可微的，并且對每一個確定的x-v∈），i = 1，···，mv都是凸函數(shù).為方便起見，對每一個v = 1，···，N，，i = 1，···，mv為分量的向量函數(shù).值得一提的是上述優(yōu)化問題的約束條件中含有其它局中人的策略x-v，這在實際應(yīng)用中是十分必要的.如果對于每一個局中人，與其它局中人的決策相關(guān)的約束條件hv≤0不存在，那么廣義納什均衡問題就變成了經(jīng)典的納什均衡問題.

因為在實際應(yīng)用中經(jīng)常會有含有隨機因素的問題，所以隨機廣義納什均衡問題也引起越來越多學(xué)者的關(guān)注.如文獻［7］中，Xu將隨機Stackelberg-Nash-Cournot均衡問題再定式為帶有互補約束的數(shù)學(xué)規(guī)劃問題進行求解.

本文主要研究如下的隨機廣義納什均衡問題（stochastic generalized Nash equilibrium problem簡記為SGNEP）.即使得對每一個局中人v的決策變量x?，v都是以下優(yōu)化問題的解:

其中ω:?→Ξ?Rk是定義在測度空間（?，F(xiàn)，P）上的隨機向量，并且“a.s.”是英文“almost surely（幾乎真）”的縮寫.

本文中假設(shè)樣本空間?是非空緊集，并且概率密度函數(shù)ρ（ω）在?上是連續(xù)的.此外，還假定函數(shù)θv（xv，x?，-v，ω）和hvi（xv，x?，-v），i = 1，···，lv關(guān)于xv都是二次連續(xù)可微的，θv（·，x?，-v，ω）是關(guān)于xv的擬凸函數(shù)，且θv（xv，x?，-v，ω）關(guān)于ω也是連續(xù)的.

§2　隨機廣義納什均衡問題的再定式

在給出求解隨機廣義納什均衡問題的確定性的新模型之前，一方面給出隨機變分不等式的定義.令S?Rn為非空閉凸集，（?，F(xiàn)，P）為概率空間，F(xiàn)為S×?→Rn的映射.隨機變分不等式問題（Stochastic Variational Inequality Problem，簡記為SVIP）

上述問題也記為SVI（F，S）.目前，關(guān)于隨機變分不等式的研究較多，主要有樣本路徑優(yōu)化方法，樣本平均方法，隨機近似方法，期望殘差最小化方法等.

另一方面，選取一個參數(shù)α＞0和一個n×n對稱正定矩陣G.定義SVI（F，S）的正則化價值函數(shù)g : Rn×?→［0，∞）為:

不難看出，對任意的x∈Rn和任意的ω∈?，

其中

定理2.1令函數(shù)F : Rn→Rn為那么在本文給出的條件下，SVI（F，S）的解即為隨機廣義納什均衡問題的解.其中，S :=

證設(shè)ˉx是SVI（F，S）的一個解.令xv是滿足約束hv（xv，x-v）≤0的任意一點.顯然，y := （ˉx1，···，ˉxv-1，xv，ˉxv+1，···，ˉxN）T也滿足上述約束條件.由于ˉx是SVI（F，S）的解，有

再根據(jù)假設(shè)θv是擬凸函數(shù)及最小原理知，ˉxv是隨機廣義納什均衡問題的解.

基于以上事實，受Luo和Lin［8］利用正則化價值函數(shù)給出求解SVI（F，S）的期望殘差最小化（expected residual minimization，簡記為ERM）模型的啟發(fā)，給出如下的求解隨機廣義納什均衡問題的確定性模型.即找一個向量x?∈S使它滿足:

這里E表示關(guān)于隨機變量ω∈?的數(shù)學(xué)期望，ρ:?→［0，∞）表示概率密度函數(shù)，它滿足

以后稱上述問題為ERM模型或ERM問題.

特別地，由于這個ERM問題中含有一個數(shù)學(xué)期望.通常情況下，對數(shù)學(xué)期望求值是非常困難的，利用擬蒙特卡羅方法給出ERM問題的近似問題如下:

值得注意的是，根據(jù)擬蒙特卡羅數(shù)列的特點［9］，有如下結(jié)論成立:

§3　近似問題解的收斂性

定理3.1假設(shè)對每個k，xk是相應(yīng)近似問題的解且x?是｛xk｝的一個聚點.那么有x?是ERM問題的解.

證不失一般性，假設(shè)limk→∞xk= x?.顯然x?∈S.由▽xG在緊集S×?上的連續(xù)性可知存在常數(shù)C＞0滿足

此外，根據(jù)中值定理可知對每個xk和每個ωi都存在

其中αki∈［0，1］滿足

基于以上事實，有

因為

再由擬蒙特卡羅數(shù)列的特點及以上證明可得

由于xk是近似問題的最優(yōu)解，這就表示

上式兩邊都對k取極限，再根據(jù)擬蒙特卡羅數(shù)列的特點可得

這就表示x?是ERM問題的最優(yōu)解.

§4　數(shù)值算例

基于［10］中的模型，本部分討論關(guān)于大規(guī)模汽油市場中供應(yīng)商競爭的隨機廣義納什均衡問題.采用提出的ERM近似方法來解決這個問題.

考慮一個具有K個供應(yīng)商的汽油現(xiàn)貨市場，這K個供應(yīng)商在市場需求未知的情況下以非合作的形式對汽油分配進行出價.逆需求函數(shù)p（q，ω）描述了市場需求，其中q是市場總供應(yīng)，ω是一個隨機變量.

市場需求確定之前，供應(yīng)商v的供應(yīng)量為qi.這個供應(yīng)商的利潤公式為

其中q-v表示供應(yīng)商v的競爭者的總出價，q = qv+ q-v表示市場所有供應(yīng)商的總出價，qvp（q，ω）表示供應(yīng)商v的總收益，Cv表示供應(yīng)商v的費用函數(shù).由于供應(yīng)商v的生產(chǎn)力與其他競爭者有關(guān)，并且可能會受到一些像隨氣候變化的汽油價格等不確定因素的影響，假定供應(yīng)商v的約束為Gv（q，ω）≤0.此處，函數(shù)p（q，ω），Cv（qv）和Gv（q，ω）只關(guān)于qv局部Lipschitz連續(xù).

每個供應(yīng)商的目的都是在其他供應(yīng)不變的情況下增加它的利潤Rv.如果q?，v，（v = 1，···，K）是如下問題的解

稱（q?，1，···，q?，K）為一個隨機廣義均衡，這明顯是一個SGNEP.因此，可以采用ERM近似方法來解這個問題.接下來，考慮以三個供應(yīng)商為例給出數(shù)值算例.數(shù)據(jù)如下:

·逆需求函數(shù)為

·費用函數(shù)為

·約束為

在上面的公式中，ω是［0，1］上的均勻分布隨機變量.在這個例子中，用擬蒙特卡羅方法獲得相應(yīng)的近似問題.在試驗中，用Matlab R2010a中的rand命令生成隨機序列，并且用命令fminunc解近似問題.此外，選取初始點為（0，0，0）T.

在表1中，Ξ=｛ωτ|τ= 1，2，···，k｝中的k表示給定的樣本大小.對于每一個給定的k，qk= xk表示此例中ERM近似問題的解.表1的計算結(jié)果顯示至少對于試驗的例子來說，ERM近似方法能夠成功地解問題SGNEP.

表1　數(shù)值結(jié)果

［1］Arrow K J，Debreu G. Existence of an equilibrium for a competitive economy［J］. Econometrica，1954，22（3）: 265-893.

［2］Debreu G. A social equilibrium existence theorem［J］. Proceedings of the National Academy of Sciences of the United States of America，1952，38（10）: 886-893.

［3］Von Heusinger A，Kanzow C. Optimization reformulation of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions［J］. Comput Optim Appl，2009，43（3）: 353-377.

［4］Pang Jongshi，F(xiàn)ukushima M. Quasi-variational inequalities，generalized Nash equilibria and multi-leader-follower games［J］. Comput Manag，2005，2（1）: 21-56.

［5］Facchinei F，Kanzow C. Generalized Nash equilibrium problems［J］. Ann Oper Res，2010，175（1）: 177-211.

［6］Facchinei F，Kanzow C. Penalty methods for the solution of generalized Nash equilibrium problems［J］. SIAM J Optim，2010，20（5）: 2228-2253.

［7］Xu Huifu. An MPCC approach for stochastic Stackelberg-Nash-Cournot equilibrium［J］. Optim，2005，54（1）: 27-57.

［8］Luo Meiju，Lin Guihua. Convergence Results of the ERM Method for Nonlinear Stochastic Variational Inequality Problems［J］. J Optim Theory Appl，2009，142（3）: 569-581.

［9］Niederreiter H. Random number generation and quasi-Monte Carlo methods［M］. Philadelphia: SIAM，1992.

［10］Li Peiyu，He Zhifeng，Lin Guihua. Sampling average approximation method for a class of stochastic Nash equilibrium problems［J］. Optimization Methods and Software，2013，28（4）: 785-795.

MR Subject Classification: 90C30

Sample average method for solving stochastic generalized Nash equilibrium problem

WANG Zhong-xing
（Shenyang polytechnic College，Shenyang 110045，China）

This paper is concerned with the stochastic generalized Nash equilibrium problem. A variational inequality form reformulation for SGNEP is proposed. Then by employing the expected residual minimization method，a new model is obtained to solve this problem. Finally，by using quasi-Monte Carlo method，this model can be solved.

stochastic generalized Nash equilibrium problem；variational inequality；expected residual minimization；quasi Monte Carlo method

O225

A

1000-4424（2016）01-0057-06

2014-11-25

2015-12-29