求解兩人博弈納什平衡問題的定制臨近點(diǎn)算法

彭 拯, 江彬倩, 莊杰鵬

(福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 福建 福州 350116)

0 引言

自從Nash[1-2]對非合作博弈提出了一種被稱為納什平衡解的概念之后, 如何找到非合作博弈的納什平衡已成為一個非常經(jīng)典的問題. 納什平衡問題是經(jīng)濟(jì)學(xué)與管理科學(xué)的基礎(chǔ), 在計(jì)算機(jī)工程、 生物信息學(xué)等各個領(lǐng)域也有著廣泛的應(yīng)用[3-5].

本研究考慮一個簡單博弈問題: 有兩位局中人A和B, A控制變量x∈X?n, B控制變量y∈Y?m, A和B的支付函數(shù)分別是uA(x,y)與uB(x,y). 注意到, 局中人的支付函數(shù)不僅與自身的決策有關(guān), 還依賴于對手的決策. 出于自私性原則, 假定每位局中人以極小化自己的支付函數(shù)為目標(biāo), 且兩位局中人輪流決策. 那么, 這個簡單博弈可以數(shù)學(xué)地描述如下.

然后,B通過求解下列問題得到當(dāng)前情況下的最優(yōu)策略

由納什平衡的定義知, 偶對w*=(x*,y*)是上述博弈的一個納什平衡解當(dāng)且僅當(dāng)

x*=arg min{uA(x,y*)|x∈X},y*=arg min{uB(x*,y)|y∈Y}

針對這種博弈問題, 常見的求解算法包括正則化Gauss-Seidel算法[6], 基于Gauss-Seidel格式的直接迭代算法[7], 基于Nikaido-Isoda目標(biāo)函數(shù)松弛的迭代算法[8], 信賴域算法[9], 等. 特別地, 針對兩人非合作博弈問題,Antipin[10]提出了求納什平衡點(diǎn)的外梯度法.Zhang等[11]借助預(yù)測-校正的思想, 通過投影算法獲得博弈的廣義納什平衡點(diǎn).Han等[12]對文獻(xiàn)[11]的算法進(jìn)行修正, 提出了一種改進(jìn)的兩步投影算法, 通過改進(jìn)校正步的迭代方向來使投影算法更快地收斂.Peng等[13]將兩人輪流博弈問題建模成變分不等式組, 在預(yù)測-校正過程中利用非精確的臨近點(diǎn)交替方向法(InPDA)求得納什平衡點(diǎn). 盧延杰等[14]針對多個局中人參與的博弈提出了類似的算法.

上述這些算法均運(yùn)用了預(yù)測和校正兩個步驟來求解博弈問題. 其中校正步可以看成當(dāng)所有局中人都給出策略之后, 有“第三只手”對他們的策略進(jìn)行了一次微調(diào). 但是, 出于競爭的公平性考慮, 許多實(shí)際情況下的博弈并不允許校正. 針對這種不允許校正博弈的納什平衡問題, 提出一種不帶校正步的定制臨近點(diǎn)算法, 并在一定條件下證明了算法全局收斂到納什平衡點(diǎn).

全文通篇做如下假設(shè):

假設(shè)1 局中人的支付函數(shù)uA(x,y)與uB(x,y)都是自身控制變量的可微凸函數(shù), 即: 對于任一固定y∈m,uA(x,y)是x∈X可微凸函數(shù); 對于任一固定的x∈n,uB(x,y)是y∈Y可微凸函數(shù).

記g(x,y)=xuA(x,y),h(x,y)=yuB(x,y). 由假設(shè)1, 任意給定y∈m,g(x,y)關(guān)于x∈X單調(diào). 同樣, 任意給定x∈n,h(x,y)關(guān)于y∈Y單調(diào). 根據(jù)單調(diào)性, 有:

(1)

假設(shè)2 決策集X?n,Y?m是簡單有界閉凸集.

在上述假設(shè)條件下, 兩人博弈的納什平衡解等價(jià)于下列變分不等式組的解:

(2)

這種等價(jià)性提示人們, 借助變分不等式的求解方法來計(jì)算博弈的納什平衡點(diǎn)是一種可行的途徑[15]. 在眾多的求解變分不等式的方法中,He等[16]提出的定制臨近點(diǎn)算法 (CPPA) 適用于本文所考慮的博弈問題. 對于線性約束凸優(yōu)化問題

(3)

定制臨近點(diǎn)算法的每一輪迭代包含如下兩步:

預(yù)測步：

其中：L(x,λ)=θ(x)-λT(Ax-b)為Lagrange函數(shù),λ為Lagrange乘子.

校正步： 定義w=(λ,x),

(4)

受上述算法的啟發(fā), 提出一種定制臨近點(diǎn)算法, 用以計(jì)算前述輪流博弈問題的納什平衡. 從已知的信息(xk,yk,yk-1)出發(fā), 算法通過求解如下優(yōu)化問題獲得當(dāng)前策略(xk+1,yk+1)：

這種算法可視為定制臨近點(diǎn)算法在博弈論中的應(yīng)用. 由于算法不帶任何校正操作, 它適用于模擬一些不允許校正的實(shí)際博弈活動.

1 算法描述及收斂性分析

給出一種求解兩人輪流博弈納什平衡問題的不帶校正步的CPPA算法, 然后對算法的全局收斂性進(jìn)行分析.

算法 1： 求解兩人輪流博弈的定制臨近點(diǎn)分裂算法, 簡記為CPPA.

S0) 初始化. 令ε>0,r,s>0. 對于任意給定的初始局勢(x0,y0), 局中人B通過求解下列問題得到y(tǒng)1∈Y：

〈y-y1,h(x0,y1)+s(y1-y0)〉≥0， ?y∈Y

S1) 迭代計(jì)算. 對于給定的(xk,yk,yk-1), 局中人A和B分別求解如下變分不等式, 先后得到當(dāng)前情況下的最優(yōu)策略xk+1∈X和yk+1∈Y:

(5)

記W=X×Y,

則式(5)可以寫成如下的緊湊形式: 求wk+1∈W, 使得

〈w-wk+1,D(wk+1,wk,wk-1)+G(wk+1-wk)〉≥0, ?w∈W

(6)

為了保證算法的收斂性, 作如下假設(shè)：

假設(shè)3 若w*=(x*,y*)∈W是博弈的一個納什平衡點(diǎn), 則

(7)

假設(shè)3是必要而且合理的. 根據(jù)納什平衡的經(jīng)濟(jì)學(xué)意義, 任何一個局中人離開平衡狀態(tài)都會使得所有局中人受到損失, 但在博弈中單方面離開平衡狀態(tài)則應(yīng)該受到懲罰, 上述假設(shè)正好體現(xiàn)了這種懲罰. 具體來說, 式(7)中的第一個不等式表示若局中人A單方面離開平衡狀態(tài),則A將受到懲罰,與A保持平衡狀態(tài)而對手B離開平衡狀態(tài)的情況相比較,A的邊際損失將更大； 第二個不等式表示若局中人B單方面離開平衡狀態(tài),則B將受到懲罰,與B保持平衡狀態(tài)而對手A離開平衡狀態(tài)的情況相比較,B的邊際損失會更大. 該條件保證了所有局中人為保持利益最大化,盡量保持在平衡狀態(tài),沒有單方面離開平衡狀態(tài)的動機(jī).

引理1 對于給定的(wk,wk-1), 設(shè)wk+1是由算法CPPA所產(chǎn)生的新迭代點(diǎn), 若w*=(x*,y*)∈W是博弈問題的一個納什平衡點(diǎn), 則

〈wk+1-w*,D(wk+1,wk,wk-1)〉≥0

(8)

證明 由g(x,y)和h(x,y)的單調(diào)性, 將(x′,y′)=(xk+1,yk+1)代入式(1), 得到

(9)

將(x,y)=(2xk+1-xk, 2yk-yk-1)代入式(9), 可得

(10)

再將(x,y)=(x*,y*)代入式(9), 可得

(11)

式(10)和式(11)相加, 得到

(12)

把(x,y)=(xk+1, 2yk-yk-1)代入式(7) 的第一個不等式, 再把(x,y)=(2xk+1-xk,yk+1)代入式(7) 的第二個不等式, 得到

(13)

結(jié)合式(2)、 (12)和(13), 直接得到式(8). 證畢.

定理 1 設(shè){wk}是由算法CPPA所產(chǎn)生的序列, 若w*是所考慮博弈的一個納什平衡點(diǎn), 則

(14)

證明 令w=w*, 由式(6)可得

〈w*-wk+1,G(wk+1-wk)〉≥〈wk+1-w*,D(wk+1,wk,wk-1)〉

根據(jù)引理1有：

〈w*-wk+1,G(wk+1-wk)〉≥0

(15)

所以

結(jié)合式(15)直接可得式(14). 定理得證.

定理 2 由算法CPPA產(chǎn)生的序列{wk}收斂到所考慮博弈問題的納什平衡點(diǎn).

證明 將不等式(14) 相加可得

(16)

于是

同時{wk}是有界序列, 因此收斂. 設(shè)w∞是序列{wk}的一個聚點(diǎn), 且子序列{wkj}收斂于w∞. 將wk=wkj,wk+1=wkj+1代入式(6)得到

〈w-wkj+1,D(wkj+1,wkj,wkj-1)+G(wkj+1-wkj)〉≥0, ?w∈W

〈w-w∞,D(w∞,w∞,w∞)〉≥0, ?w∈W

因此,w∞是變分不等式(2)的解, 也是博弈問題的納什平衡點(diǎn).

另一方面, 由式(14) 可得

(17)

(18)

所以, 對于任意k≥kj, 由式(17) 和式(18) , 得到

即序列{wk}收斂于w∞. 證畢.

受文獻(xiàn)[17] 的啟發(fā), 如果局中人對其對手的本輪策略與上一輪策略采用可變權(quán)重α, 可將算法CPPA中的迭代計(jì)算步 S1 進(jìn)行簡單修正, 得到推廣算法如下.

算法 2： 算法推廣, ECPPA.

S1. 迭代計(jì)算: 對于給定的(xk,yk,yk-1), 局中人A和B通過求解如下變分不等式, 先后獲得當(dāng)前情況下的最優(yōu)策略xk+1和yk+1:

(19)

變分不等式組(19)可以寫成如下緊湊形式

?w∈W

其中

簡單變形可知

其中: Δxk=xk+1-xk(分別地, Δyk-1=yk-yk-1) 為局中人在前后兩輪博弈中決策的改變量. 參數(shù)α刻畫了局中人對其對手的策略變化情況的重視程度. 在模擬計(jì)算中, 適當(dāng)選取α的值能夠加快算法的收斂速度. 當(dāng)α=0時, 每個局中人只考慮對手當(dāng)前的決策yk(分別地,xk+1), 算法ECPPA還原成原始的臨近點(diǎn)分裂算法; 當(dāng)α>0時, 每個局中人不僅考慮對手當(dāng)前的決策, 還考慮了對手的改變量Δyk-1(分別地, Δxk); 當(dāng)α=1時, 算法ECPPA 還原為算法 CPPA. 因此, 由于采用了可變權(quán)重α, 算法ECPPA體現(xiàn)了局中人對其對手前后兩輪決策一致性的重視程度和博弈的主觀性.

當(dāng)α>0時, 采用與CPPA完全相同的分析方法, 可以證明算法ECPPA的全局收斂到所考慮博弈的納什平衡點(diǎn).

2 數(shù)值實(shí)驗(yàn)

采用數(shù)值實(shí)驗(yàn)來說明算法CPPA和ECPPA的有效性. 為了保證公平, 所有實(shí)驗(yàn)均用Matlab2013a編程, 在Asus筆記本電腦上運(yùn)行.

例1 考慮一個N=2的雙寡頭壟斷模型[18-19]. 局中人i控制變量xi∈,i=1, 2. 支付函數(shù)為

θi=xi(ρ(x1+x2)+λ-d) (i=1, 2)

其中：xi∈[-10, 10];ρ=1;λ=4;d=20. 該博弈的納什平衡為(16/3, 16/3)T. 選取相同的初始點(diǎn), 用算法InPDA[13]、 算法CPPA 和算法ECPPA 進(jìn)行計(jì)算. 在所有測試算法中, 設(shè)定r,s=2.4, 停止條件為ek≤ε=0.5×10-5, 其他參數(shù)設(shè)置為:γ=1.6,α=1.3. 隨機(jī)選取初始點(diǎn)(x,y)T=rand(2, 1)T, 進(jìn)行100次隨機(jī)實(shí)驗(yàn), 將算法的平均迭代次數(shù), 平均函數(shù)值計(jì)算次數(shù)及所獲得的解列于表1.

表1 例1數(shù)值結(jié)果Tab.1 Numerical results of example 1

由上表可知, 算法CPPA和ECPPA的迭代次數(shù)幾乎與算法InPAD 相同, 且都收斂到納什平衡點(diǎn), 但算法CPPA與ECPPA 的函數(shù)值計(jì)算次數(shù)約為算法InPAD的一半.

例2 該例取自文獻(xiàn)[20-21]. 設(shè)兩個局中人 A 和 B 輪流博弈, 他們從[0, 10]中先后選取一個數(shù)x和y, 要求x+y≤15, 使得下列支付函數(shù)最小:

該博弈的納什平衡點(diǎn)為(5, 9)T和線段[(9, 6)T, (10, 5)T]上所有的點(diǎn). 采用與例1同樣的3種算法計(jì)算, 從不同的初始點(diǎn)出發(fā), 所有算法在相同的終止條件下獲得相同的納什平衡點(diǎn)(5.000,9.000)T. 3種算法的迭代次數(shù)與函數(shù)值計(jì)算次數(shù)列于表2.

表2 例2數(shù)值結(jié)果Tab.2 Numerical results of example 2

由表2可知, 算法CPPA的迭代次數(shù)幾乎是InPDA的兩倍, 函數(shù)計(jì)算次數(shù)也接近InPDA. 而算法ECPPA 的迭代次數(shù)接近InPDA, 但函數(shù)計(jì)算次數(shù)大約是InPDA的一半. 這說明對于該算例, 算法ECPPA比算法CPPA與InPAD效率更高.

3 結(jié)語

為了保證公平性, 實(shí)踐中的許多博弈往往不允許校正, 針對不允許校正的兩人輪流博弈提出了一種計(jì)算納什平衡點(diǎn)的定制臨近點(diǎn)分裂算法(CPPA). 在算法CPPA中, 局中人綜合考慮對手當(dāng)前決策和前后兩輪決策的改變量, 通過極小化自己的支付函數(shù)進(jìn)行決策. 在一定的條件下證明了算法CPPA全局地收斂到所考慮博弈的納什平衡點(diǎn). 同時對算法CPPA進(jìn)行推廣, 對局中人的對手前后兩輪決策的改變量引入可變權(quán)重α>0, 得到推廣的不帶校正運(yùn)算的定制臨近點(diǎn)分裂算法 (ECPPA). 數(shù)值實(shí)驗(yàn)結(jié)果表明, 在所有算法都得到納什平衡點(diǎn)的條件下, 不帶校正的算法CPPA與ECPPA的迭代次數(shù)接近帶有校正的算法InPDA, 而函數(shù)計(jì)算次數(shù)也相對減少, 其中算法 ECPPA的計(jì)算效率相對更好. 因此, 該算法是一種求解不允許校正的兩人輪流博弈的有效方法.

[1] NASH J. Equilibrium points inn-person games[J]. Proceedings of the National Academy of Science, 1950, 36(1): 48-49.

[2] NASH J. Non-cooperative games[J]. Annals of Mathematics Studies, 1951, 54(3): 286-295.

[3] MYERSON R B. Nash equilibrium and the history of economic theory[J]. Journal of Economic Literature, 1999, 37(3): 1067-1082.

[4] CONTRERAS J, KLUSH M, KRAWCZYK J B. Numerical solutions to Nash-cournot equilibria in coupled constraint electricity markets[J]. IEEE Transactions on Power Systems, 2010, 19(1): 195-206.

[5] FACCHINEI F, KANZOW C. Generalized Nash equilibrium problems[J]. Annals of Operations Research, 2010, 175(1): 177-211.

[6] FACCHINEI F, PICCIALLI V, SCIANDRONE M. Decomposition algorithms for generalized potential games[J]. Computational Optimization& Applications, 2011, 50(2): 237-262.

[7] PANG J S, SCUTARI G, FACCHINEI F,etal. Distributed power allocation with rate constraints in gaussian parallel interference channels[J]. IEEE Transactions on Information Theory, 2008, 54(8): 3471-3489.

[8] URYASEV S, RUBINSTEIN R Y. On relaxation algorithms in computation of noncooperative equilibria[J]. IEEE Transactions on Automatic Control, 1994, 39(6): 1263-1267.

[9] YUAN Y X. A trust region algorithm for Nash equilibrium problems[J]. Pacific Journal of Optimization, 2011, 7(1): 125-138.

[10] ANTIPIN A. Extra-proximal methods for solving two-person nonzero-sum games[J]. Mathematical Programming, 2009, 120(1): 147-177.

[11] ZHANG J, QU B, XIU N. Some projection-like methods for the generalized Nash equilibria[J]. Computational Optimization & Applications, 2010, 45(1): 89-109.

[12] HAN D, ZHANG H, QIAN G,etal. An improved two-step method for solving generalized Nash equilibrium problems[J]. European Journal of Operational Research, 2012, 216(3): 613-623.

[13] PENG Z, ZHU W. An alternating direction method for Nash equilibrium of two-person games with alternating offers[J]. Journal of Optimization Theory and Applications, 2013, 157(2): 533-551.

[14] 盧延杰, 丁衛(wèi)平, 彭拯. 一種求解Leader-Followers博弈問題的混合分裂算法[J]. 應(yīng)用數(shù)學(xué)學(xué)報(bào), 2014, 37(6): 1042-1055.

[15] FACCHINEI F, PANG J S. Finite-dimensional variational inequalities and complementarity problems[M]//Springer Series in Operations Research& Financial Engineering. New York: Springer-Verlag, 2003: 625-1222.

[16] HE B, YUAN X, ZHANG W. A customized proximal point algorithm for convex minimization with linear constraints[J]. Computational Optimization & Applications, 2013, 56(3) : 559-572.

[17] JIANG B, PENG Z, DONG Z. A new customized proximal point algorithm for linearly constrained convex optimization [EB/OL]. (2016-4-30)[2016-5-31]. http://www.optimization- online.org/DB_HTML/2016/04/5424.html.

[18] FACHHINEI F, KANZOW C. Penalty methods for the solution of generalized Nash equilibrium problems[J]. Mathematical Programming, 2010, 20(5): 2228-2253.

[19] KRAWCZYK J B, URYASEV S. Relaxation algorithms to find Nash equilibria with economic applications[J]. Environmental Modeling and Assessment, 2000, 5(5): 63-73.

[20] HARKER P T. Generalized Nash games and quasi-variational inequalities[J]. European Journal of Operational Research, 1991, 54(1): 81-94.

[21] OUTRATA J, ZOWE J. A numerical approach to optimization problems with variational inequality constraints[J]. Mathematical Programming, 1995, 68(1): 105-130.