劉露萍，賈文生*

（1. 貴州大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，貴州 貴陽(yáng)　550025，2. 貴州省博弈決策與控制系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽(yáng)　550025）

0　引言

1944年，美國(guó)著名學(xué)者馮諾依曼（Von Neumann）和摩根斯坦（Morgenstern）的名著《博弈論與經(jīng)濟(jì)行為》中提到：“博弈論是建立經(jīng)濟(jì)行為理論的最恰當(dāng)方法”。特別值得關(guān)注的是自1994年至今，諾貝爾獎(jiǎng)多次頒給博弈論的研究學(xué)者。納什（Nash）、澤爾騰（Selten）、海薩尼（Harsanyi）因在非合作博弈論研究領(lǐng)域作出貢獻(xiàn)獲得了 1994年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)，緊接著1996年頒給博弈論和信息經(jīng)濟(jì)學(xué)家莫里斯（Mirrless）和維可瑞（Vickrey），2001年頒給了對(duì)充滿不對(duì)稱信息市場(chǎng)進(jìn)行分析的博弈論學(xué)者阿克爾洛夫（Akerlof）、斯彭斯（Spence）和斯蒂格利茨（Stiglitz），2005年頒給博弈論著名學(xué)者奧曼（Aumann）和謝林（Schelling），2007年頒給機(jī)制設(shè)計(jì)方面做出突出貢獻(xiàn)的博弈論學(xué)者赫維克（Hurwicz）、馬斯金（Maskin）和邁爾森（Myerson），2012年頒給沙普利（Shapley）和羅斯（Roth），2014年頒給用博弈論分析產(chǎn)業(yè)組織理論的學(xué)者梯若爾（Tirole），2017年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)得主 Richard Thaler也是在博弈論領(lǐng)域做出突出貢獻(xiàn)，特別是在“有限理性行為”方面成就斐然。1950年，納什（Nash）在他的博士論文中提出了非合作博弈模型和解的概念，后來(lái)被人們稱之為Nash均衡。Nash均衡是非合作博弈的核心概念，也奠定了n人非合作博弈理論的堅(jiān)實(shí)基礎(chǔ)。Nash均衡不僅對(duì)社會(huì)科學(xué)領(lǐng)域影響巨大，也對(duì)包括計(jì)算機(jī)科學(xué)、人工智能、大數(shù)據(jù)等領(lǐng)域產(chǎn)生了重大影響，幾乎影響到科學(xué)研究的所有領(lǐng)域。

1　模型描述

特別地，對(duì)于2人的有限非合作博弈，即雙矩陣博弈：設(shè)參與人 1的混合策略為 x=( x1,x2,…,xm)∈X，參與人2的混合策略為y= ( y1, y2,…,yn)∈Y，Am×n，Bm×n分別為參與人1和參與人2的支付矩陣，則參與人1和參與人2的期望收益分別為 x AyT和 x ByT。

定義 1[1]x*是有限n人非合作博弈模型的一個(gè)Nash均衡，如果x*滿足… ,n )，其中x*xi表示在均衡解的條件下只有博弈參與人i用 xi替換均衡解x*中自己的策略，其他博弈參與人都不改變各自在均衡解中的策略。

引理 1[1]混合策略x*是有限n人非合作博弈的一個(gè)Nash均衡的充分必要條件是：對(duì)于任意參與i的每一個(gè)純策略。

特別地，（x*,y*）是雙矩陣博弈的一個(gè) Nash均衡的充分必要條件是：

2　方體剖分算法的基本思想和實(shí)現(xiàn)步驟

Step 1對(duì)每一個(gè)博弈參與人i∈N，對(duì)包含其策略集 Xi的方體[0,1]mi的每一維進(jìn)行m等分剖分，這樣就得到如下的一個(gè)分劃：

Step 3因 μi(x )是關(guān)于x的多線性函數(shù)，所以是連續(xù)的，從而在每一個(gè)小閉區(qū)間上是一致連續(xù)的，所以可以用 μi( y )來(lái)任意近似，而劃分是有限的，必然也是有限的，因此，一定可以在有限步驟內(nèi)找到有限n人非合作博弈的近似Nash平衡點(diǎn)。具體來(lái)說(shuō)，對(duì)于任意給定的精度ε＞0，存在，使得當(dāng)對(duì)任意的 i ∈{1,2,…,n}，j∈ { 1,2,… ,mi}滿足＜δ時(shí)，有

這樣，對(duì)每一個(gè)博弈參與人iN∈，對(duì)包含其策略集iX的方體[0,1]im的每一維進(jìn)行m等分剖分，只一定可以達(dá)到相應(yīng)的精度ε。

3　結(jié)合量子免疫粒子群算法的實(shí)例分析

Nash均衡的算法和實(shí)現(xiàn)路徑研究，是當(dāng)前國(guó)際博弈論研究領(lǐng)域的熱點(diǎn)和前沿之一。許多學(xué)者圍繞Nash均衡的計(jì)算和實(shí)現(xiàn)做了大量的工作，提出了各種各樣的算法[2-11]，但是主要分為兩大類。一類是純數(shù)學(xué)分析算法，主要借助于梯度、同倫、投影和罰函數(shù)等技巧來(lái)計(jì)算和分析。這類算法的對(duì)函數(shù)的可微性和凹凸性等性質(zhì)要求高，由實(shí)際問(wèn)題建立的博弈模型往往不一定滿足這些要求。另一類是智能算法，特別是生物演化算法，這類算法不但實(shí)現(xiàn)簡(jiǎn)單，而且更重要的是代表著一種新的方向，因?yàn)閺难莼蛯W(xué)習(xí)的角度將 Nash均衡看成是具有有限理性的博弈參與人逐步尋求最優(yōu)解的結(jié)果更貼近現(xiàn)實(shí)。關(guān)于粒子群算法也有很多改進(jìn)和應(yīng)用[11-15]，特別是文獻(xiàn)[12]提出了一種新的量子免疫粒子群算法，該算法將量子不確定性理論和免疫粒子群算法結(jié)合，為Nash均衡的實(shí)現(xiàn)路徑研究提供了一種新的探索?，F(xiàn)在將改進(jìn)的量子免疫粒子群算法與方體剖分算法結(jié)合，對(duì)下面的算例進(jìn)行計(jì)算和分析：

例考慮博弈 Γ (X, Y, A, B)，

利用上述方體剖分算法得到的近似 Nash平衡點(diǎn)為：

(x,y)=(0.33333, 0.33333, 0.33333, 0.33333,0.33333, 0.33333)。

具體的計(jì)算搜索路徑如圖1所示：

圖1　博弈 Γ ( X, Y, A, B)的方體剖分算法3維搜索路徑圖Fig.1　Cube Subdivision Algorithm of Game　 Γ( X, Y, A, B)

總之，通過(guò)實(shí)際算例的計(jì)算和分析，可以看出本文提出的方體剖分算法和量子免疫粒子群算法結(jié)合在求解有限n人非合作博弈 Nash均衡方面是有效的。而且把一個(gè)有限n人非合作連續(xù)型博弈通過(guò)對(duì)混合策略空間的方體剖分轉(zhuǎn)化為一個(gè)離散形式的有限博弈，給出了連續(xù)型博弈的一種近似可計(jì)算性結(jié)果，并借助量子免疫粒子群算法給出了具體的求解路徑。

4　結(jié)論

本文提出的方體剖分算法與以往文獻(xiàn)中的單純形剖分算法不同，單純形剖分算法的關(guān)注點(diǎn)和基礎(chǔ)在于利用不動(dòng)點(diǎn)理論和單純形剖分來(lái)計(jì)算近似Nash均衡，而且它的適用范圍往往受到博弈支付函數(shù)表達(dá)形式的限制。另外，從方體剖分算法的設(shè)計(jì)過(guò)程看，其本質(zhì)就是把一個(gè)連續(xù)型博弈通過(guò)對(duì)混合策略空間的方體剖分轉(zhuǎn)化為一個(gè)離散形式的有限博弈，因此該算法的主要意義在于從某種意義上給出了連續(xù)型博弈的一種近似可計(jì)算性結(jié)果，而且算法較為直接，更容易推廣到一般的連續(xù)函數(shù)博弈，同時(shí)本文結(jié)合了量子免疫粒子群算法給出了具體算例的Nash均衡的搜索路徑。