基于方體剖分和量子免疫粒子群算法的Nash均衡求解

劉露萍，賈文生*

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

0　引言

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

1　模型描述

特別地，對于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人非合作博弈模型的一個Nash均衡，如果x*滿足… ,n )，其中x*xi表示在均衡解的條件下只有博弈參與人i用 xi替換均衡解x*中自己的策略，其他博弈參與人都不改變各自在均衡解中的策略。

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

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

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

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

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

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

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

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

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

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

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

具體的計算搜索路徑如圖1所示：

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

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

4　結(jié)論

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