一種修正的路徑跟蹤法求解納什(Nash)均衡雙矩陣對策問題

葛康康 趙琪

淮北理工學(xué)院 安徽淮北 235000

納什均衡問題在交通規(guī)劃、計算機、管理學(xué)及經(jīng)濟學(xué)等領(lǐng)域都有著廣泛的應(yīng)用[1-3]，是非合作博弈理論中最核心的概念。納什問題的提出和不斷完善為博弈論廣泛應(yīng)用于各個領(lǐng)域奠定了堅實的基礎(chǔ)[4-6]。如何更加有效地求解納什均衡雙矩陣對策問題仍是當(dāng)前研究的重要課題之一，該問題可等價的轉(zhuǎn)化為一個線性互補問題。這為求解納什均衡雙矩陣對策問題提供一個行之有效的路徑[1，5]。本文改進了算法的搜索步長，設(shè)計了一個新的修正的路徑跟蹤法。并基于較弱的假設(shè)條件證明了該算法的可行性和全局收斂性[4]，數(shù)值實驗的結(jié)果表明修正的路徑跟蹤法能更好地解決納什均衡雙矩陣對策問題。

1 預(yù)備知識

線性互補問題[1]的數(shù)學(xué)模型為找到x∈Rn，使得

x≥0，Mx+q≥0，xT(Mx+q)=0.

(1)

其中M∈Rn×n，q∈Rn分別為已知的矩陣和向量。

對于任意的二次規(guī)劃

(2)

其中Q∈Rn×n是對稱正定矩陣，A∈Rn×n，c∈Rn，b∈Rn分別為給定的矩陣和向量。則x為式(2)的全局最小點，當(dāng)且僅當(dāng)x是其K-K-T點。

由于式(2)的Lagrange函數(shù)為:

其中λ∈Rm為Ax≥b的Lagrange乘子向量，μ∈Rn為x≥0的Lagrange乘子向量，其K-K-T點滿足:

(3)

式(3)等價于:

2 雙矩陣對策問題轉(zhuǎn)化為互補問題

假設(shè)1 每個參與者可以采取的策略稱為純策略，假設(shè)有2個參與者且第一個參與者有m個純策略，第二個參與者有n個純策略。

定義1[2]如果混合策略對(x*，y*)∈Rm×Rn為滿足下面兩個問題的最優(yōu)解

則稱(x*，y*)為一個納什均衡。

其中x=(x1，x2，…，xm)∈Rm為第一個參與者的一個混合策略，y=(y1，y2，…，yn)∈Rn是第二個參與者的一個混合策略；A=(aij)，B=(bij)∈Rm×n分別表示兩個參與者的支付矩陣，xTAy，(x)TBy表示兩個參與者的期望支付。

定理1若(x*，y*)是關(guān)于矩陣A，B的雙矩陣對策的納什均衡，則必存在一個充分大的正數(shù)d使得對任意的i，j都有aij+d>0，bij+d>0且(x*，y*)也是新支付矩陣(aij+d)和(bij+d)的雙矩陣對策的納什均衡。

證明 根據(jù)定理1不妨設(shè)A=(aij)，B=(bij)∈Rm×n其中aij>0，bij>0。由定義1可知x*和y*分別是下面兩個問題的最優(yōu)解：

(4)

(5)

由式(4)和式(5)可知:

(6)

若(w*，v*)為式(6)的解，化簡可得

3 算法

根據(jù)定義2，求解問題(1)的基本思想可概括為：沿著中心鄰域N(β)產(chǎn)生迭代點列{(xk，yk)}來逼近問題的解。具體實施時，首先求解方程組

(7)

然后，選取適當(dāng)?shù)摩炔⒂嬎?

(8)

算法1 (修正的徑跟蹤法)

步驟2 求解方程組

得到搜索方向(Δx(β)，Δy(β))∈Rm×Rn。

步驟4 令k：=k+1，轉(zhuǎn)步驟1。

4 收斂性分析

(9)

(10)

根據(jù)式(8)和式(10)可得:

(11)

定理1 算法1，滿足:

即算法1是收斂的。

證明 由引理2可知:

(12)

對式(12)各項取極限可得:

即算法1是收斂的。

證明 由引理2和式(12)可知:

(13)

對式(13)兩邊取對數(shù):

(14)

即(xk)Tyk≤ε，進而可知算法1是可行的。

由引理2再結(jié)合定理1、定理2可知，算法1是可行的且全局收斂性。

5 數(shù)值實例

為了驗證算法1的可行性和有效性，進行如下數(shù)值實驗，納什均衡雙矩陣對策問題的初始值設(shè)定為，n=A的行數(shù)+A的列數(shù)，e=(1，1，…，1)T∈Rn，q=-e，x0=-e，y0=Mx0+q。

例1 囚徒困境[5]

取d=2，得到與之等價的矩陣

由路徑跟蹤法得：

x=(0.0000，1.0000)，y=(0.0000，1.0000).

計算時間：t=0.0312秒。

迭代次數(shù)：k=348次。

由修正的路徑跟蹤法得：x=(0.0000，1.0000)，

y=(0.0000，1.0000)。

計算時間：t=0.0080秒。

迭代次數(shù)：k=67次。

例2 免費搭乘問題，取自參考文獻[6]

經(jīng)典的對稱二人免費搭乘問題，每個人都必須做一個決策是參與還是不參與某個特定的公共設(shè)施的建設(shè)。如果參與需付費用c，如果公共設(shè)施建成，每個人享受的利益為1-c。除非有一個局中人參與，否則公共設(shè)施無法建立，可以得到的支付矩陣A和B：

取一具體數(shù)值c=0為例，則：

取d=2，得到與之等價的矩陣

由路徑跟蹤法得：

x=(0.0000，1.0000)，y=(0.0000，1.0000)

計算時間：t=0.0156秒。

迭代次數(shù)：k=311次。

由修正的路徑跟蹤法得：

x=(0.0000，1.0000)，y=(0.0000，1.0000)

計算時間：t=0.0030秒。

迭代次數(shù)：k=59次。

由上述數(shù)值實驗結(jié)果可以看出，算法1對測試的問題，具有良好的數(shù)值表現(xiàn)。其在處理納什雙矩陣均衡問題時，隨著問題的維數(shù)增加，迭代次數(shù)、計算時間均增長。但修正的路徑跟蹤法所用的迭代次數(shù)、計算時間均比原有的算法更少，即算法1更加可行有效。