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

劉露萍，賈文生*

（1. 貴州大學 數學與統計學院，貴州 貴陽　550025，2. 貴州省博弈決策與控制系統重點實驗室，貴州 貴陽　550025）

0　引言

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

1　模型描述

特別地，對于2人的有限非合作博弈，即雙矩陣博弈：設參與人 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　方體剖分算法的基本思想和實現步驟

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

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

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

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

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

例考慮博弈 Γ (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)

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

4　結論

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