求解廣義Nash均衡問(wèn)題的同倫方法

范曉娜， 陳 燕， 蔣 俐

(南京郵電大學(xué) 理學(xué)院， 江蘇 南京 210023)

廣義Nash均衡問(wèn)題(GNEP)由經(jīng)典Nash均衡問(wèn)題發(fā)展而來(lái). 不同之處在于廣義Nash均衡問(wèn)題中的每一位博弈者的決策都不僅依賴于自身的決策變量，還取決于其他博弈者所做的決策. 因此廣義Nash均衡問(wèn)題更具有現(xiàn)實(shí)意義，更適用于模擬競(jìng)爭(zhēng)市場(chǎng)的真實(shí)狀況. 隨著對(duì)廣義Nash均衡問(wèn)題的深入研究，廣義Nash均衡在金融經(jīng)濟(jì)、政治、軍事、電子通信、生物科技、工程技術(shù)、環(huán)境和交通運(yùn)輸?shù)缺姸嗌鐣?huì)領(lǐng)域都有其廣泛的應(yīng)用價(jià)值. 不可否認(rèn)的是，當(dāng)前對(duì)廣義Nash均衡問(wèn)題的研究還遠(yuǎn)不如對(duì)經(jīng)典Nash均衡問(wèn)題的研究那樣豐富和完善. 2009年，Xu、Yu[1]等人在有界域內(nèi)用同倫方法對(duì)GNEP進(jìn)行研究和求解，該方法克服了已有方法(文獻(xiàn)[2—5])的收斂困難、收斂條件強(qiáng)等缺點(diǎn)，得到了較好的收斂結(jié)果. 2019年，F(xiàn)an[6]等在文獻(xiàn)[1]的基礎(chǔ)上給出一種新的同倫方法求解GNEP，該方法擴(kuò)大了初始點(diǎn)的選取范圍，為問(wèn)題的解決帶來(lái)了方便. 本文考慮改進(jìn)文獻(xiàn)[6]的結(jié)果，通過(guò)引入兩個(gè)輔助映射，從而擴(kuò)大收斂的范圍并加快收斂的速度.

1 預(yù)備知識(shí)

考慮一個(gè)共有N人的非合作博弈，每個(gè)博弈者的決策集不僅依賴于自身的決策變量，還取決于其他博弈者所做的決策.給定一個(gè)集值映射Xi:

x=(x1,…,xi,…,xN)T=(xi,x-i)T,xi∈Rni.

對(duì)任意x-i∈Rn-i，gi:Rn→Rmi,hi:Rni→Rli,第i個(gè)博弈者的決策集記為Xi(x-i)≡{xi∈Rni:gi(x)≤0,hi(xi)=0}.記指標(biāo)集為

其中

Xi(x-i)的內(nèi)部記為Xi(x-i)0≡{xi∈Rni:gi(x)<0,hi(xi)=0}，邊界集記為?(Xi(x-i))≡{xi∈Rni:gi(x)=0,hi(xi)=0，j∈Ii(x)}.

對(duì)于GNEP，每個(gè)博弈者做出的決策都依賴于其他玩家的決策.當(dāng)其他競(jìng)爭(zhēng)對(duì)手的決策確定以后，第i個(gè)博弈者的目標(biāo)就是要選擇一個(gè)決策xi解決最優(yōu)化問(wèn)題:

其中ui稱為第i個(gè)博弈者的效用函數(shù).

為了簡(jiǎn)化起見(jiàn)，本文引用以下符號(hào)

其中m=m1+…+mN,l=l1+…+lN,n=n1+…+nN.

2 同倫方程的構(gòu)造

基于KKT系統(tǒng):

(1)

H(ω,ω(0),μ)=

(2)

在一定的假設(shè)條件下，同倫路徑的存在性和收斂性可以得到證明.

從而得到x=x(0)，β=β(0)=h(x(0))，由于g(x(0))<0，故λ=λ(0).因此,方程H(ω,ω(0),1)=0有唯一解ω=ω(0).當(dāng)μ=0時(shí)，上述同倫方程即簡(jiǎn)化為GNEP中的KKT系統(tǒng).

為得到本文的主要結(jié)果，先介紹以下引理.

則y∈Rp是φ的一個(gè)正則值.

引理3(一維光滑流形分類定理)[8]一維光滑流形與單位圓或單位區(qū)間同胚.

假設(shè)1

3 主要結(jié)果

(4)

將(4)式的第1個(gè)方程變形，并在等式兩邊同時(shí)乘以(x(k)-z)，z∈C，則有

(x(k)-z)T(□u(x(k))+μkα(x(k))V(k)2em+

μkγ(x(k))U(k)2el)=

(x(k)-z)T□g(x(k))V(k)em-

(x(k)-z)T□h(x(k))U(k)el，

即

(z-x(k))T(□u(x(k))+

μkα(x(k))V(k)2em+μkγ(x(k))U(k)2el)=

(x(k)-z)T□g(x(k))V(k)em+

(x(k)-z)T□h(x(k))U(k)el≥

(g(x(k))-g(z))TV(k)em+

(h(x(k))-h(z))TU(k)el=

μkg(x(0))TV(0)em-g(z)TV(0)em+

μkelTU(k)TU(k)el≥

μkg(x(0))TV(0)em+μkelTU(k)TU(k)el=

(1-μk)g(x(0))TV(0)em+

(1-μk)elTU(k)TU(k)el]=

(1-μk)g(x(0))TV(0)em+

(1-μk)elTU(k)TU(k)el].

根據(jù)函數(shù)g的凸性和h的線性性質(zhì)可推出第一個(gè)不等式，即

(x(k)-z)T□g(x(k))=

(x(k)-z)T□h(x(k))=

由方程(4)的第2個(gè)式子可推出第2個(gè)等式，推導(dǎo)如下：

(g(x(k))-g(z))TV(k)em=

(g1(x(k))-g1(z),…,gm(x(k))-gm(z))×

(1-μk)g(x(0))TV(0)em+

(1-μk)elTU(k)TU(k)el>M，

故(z-x(k))T(□u(x(k))+μkα(x(k))V(k)2em+

μkγ(x(k))U(k)2el)>0，即(x(k)-z)T(□u(x(k))+μkα(x(k))V(k)2em+μkγ(x(k))U(k)2el)<0，這與假設(shè)(C4)矛盾，因此ω的分量x是有界的.

(1-μk)(?xiui(x(k,-i),x(k,i))+?xigi(x(k,-i),x(k,i))λ(k,i)+

μkαxi(x(k,-i),x(k,i))(λ(k,i))2+?xihi(x(k,i))β(k,i)+

μkγxi(x(k,-i),x(k,i))(β(k,i))2)+μk(x(k)-x(0))=0.

(5)

對(duì)于μ*∈[0,1]，分以下兩種情況討論β(k)的有界性：

方程(5)可改寫為

(1-μk)?xiui(x(k,-i),x(k,i))+μk(x(k,i)-x(0,i))+

μkγxi(x(k,-i),x(k,i))(β(k,i))2]=0.

(6)

(ⅰ)當(dāng)μ*=1時(shí)，將(5)式改寫為

μk(x(k,i)-x(0,i))=

(7)

根據(jù)引理5以及上述分析，令k→∞，x(k)→x*，β(k)→β*，由(7)式得

(8)

與假設(shè)(C2)矛盾.

從而x(*,i)+υαxi(x(*,-i),x(*,i))=x(0,i)，與假設(shè)(C5)矛盾.

這與假設(shè)(C2)矛盾.

(9)

拆分(9)式的第1個(gè)等式，我們得到以下結(jié)果.

定理2同倫路徑Γω(0)由以下常微分方程組的初值問(wèn)題決定:

且對(duì)于μ(s*)=0，方程(9)的解(ω(s*),μ(s*))的分量x是GNEP的解.

根據(jù)定理1和定理2，可以用標(biāo)準(zhǔn)預(yù)估矯正法對(duì)同倫路徑Γω(0)進(jìn)行數(shù)值追蹤，從而找到同倫方程(3)的解.

4 數(shù)值例子

在MATLAB中用Euler Newton算法對(duì)同倫路徑進(jìn)行追蹤，并將產(chǎn)生的結(jié)果與已有的同倫方法作比較.對(duì)以下所有算例，選取相同的精確度參數(shù)：ε1=10-4,ε2=10-1,ε3=10-6,μ0=1.0.數(shù)值結(jié)果見(jiàn)表1和表2，其中A1表示本文構(gòu)建的同倫方法，A2表示文獻(xiàn)[6]中所用的同倫方法.IT表示迭代次數(shù)，CPU表示程序運(yùn)行時(shí)間，x0表示初始點(diǎn)，x*表示問(wèn)題的近似解. 數(shù)值結(jié)果表明本文的同倫方法對(duì)于求解GNEP是有效的.

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

表2 例2的數(shù)值結(jié)果

例1

例2

例3

x1+x2=1;

x3+x4=1.

表3 例3的數(shù)值結(jié)果

5 結(jié)語(yǔ)

對(duì)于求解帶有等式和不等式約束的GNEP，本文通過(guò)引入2個(gè)二次連續(xù)可微映射α(x)，γ(x) 構(gòu)造出一個(gè)新的同倫方程，并在給出的假設(shè)條件下，證明了同倫路徑的存在性和全局收斂性.相較于文獻(xiàn)[1]中的同倫方法，本方法同樣減弱了收斂的條件，擴(kuò)大了初始點(diǎn)的選取范圍，并且相較于文獻(xiàn)[6]中的同倫方法具有更高的計(jì)算效率. 數(shù)值例子證明了新的同倫方法的有效性.