博弈論中反應(yīng)函數(shù)法的改進(jìn)

楊 莉

（外交學(xué)院 國際經(jīng)濟(jì)學(xué)院，北京 100037）

0 引言

反應(yīng)函數(shù)法，也稱最優(yōu)反應(yīng)函數(shù)法，主要用于連續(xù)、無限策略博弈的求解，是完全信息靜態(tài)博弈、完全信息動態(tài)博弈、不完全信息靜態(tài)博弈、不完全信息動態(tài)博弈的相關(guān)應(yīng)用中運用最為廣泛的方法[1]，原理是固定其他人策略不變，求參與人i的最優(yōu)策略，使參與人 i的收益 ui=ui(x1，x2，…，xn)達(dá)到最大值。目前在博弈論的各種書中看到的求解主要是針對單目標(biāo)函數(shù)，且對目標(biāo)支付函數(shù)有要求：函數(shù)形式簡單，一、二階導(dǎo)數(shù)好求，容易求出駐點，判斷是否極值點容易，并且一般是無約束的單目標(biāo)優(yōu)化問題。但存在以下兩種問題無法處理：

（1）當(dāng)ui的形態(tài)較復(fù)雜時，可能會出現(xiàn)不連續(xù)、多值等情況，甚至的解未必是最優(yōu)策略，單獨用求導(dǎo)數(shù)或求偏導(dǎo)找出駐點或?qū)?shù)不存在的點，用拉格朗日乘除法或海賽矩陣求最優(yōu)值是不可能的。

（2）利用最優(yōu)反應(yīng)函數(shù)法求解博弈模型，對模型的條件要求苛刻，局中人往往只能限制為兩個人，模型中的參數(shù)也常常有一定的限制。例如在異質(zhì)產(chǎn)品價格競爭模型、多階段可觀察行動動態(tài)博弈模型——公共資源問題，若將局中人擴大成三個或更多，模型的復(fù)雜度大大提高，求解將變得困難，甚至用常規(guī)方法無法求解。

本文結(jié)合數(shù)學(xué)優(yōu)化領(lǐng)域進(jìn)化技術(shù)的新進(jìn)展,利用多目標(biāo)優(yōu)化算法進(jìn)行求解。這里的求解不僅僅是以支付收益的最大化作為目標(biāo)函數(shù)，而是探討復(fù)雜的有約束的、多目標(biāo)的支付函數(shù)的博弈模型的求解，博弈中每一步的納什均衡在最優(yōu)或非劣解中進(jìn)行尋找。

1 連續(xù)策略的一般描述

設(shè)有n個參與人的博弈，參與人i的策略空間為Ai，Ai為實數(shù)區(qū)間，xi∈Ai代表一個策略，收益（效用）函數(shù)為ui=ui(x1，x2，…，xn)為連續(xù)函數(shù)。 策略組合是一個納什均衡，如果對于每一個參與人i，給定其他參與人的選擇情況下第i個參與人的最優(yōu)策略（使 ui或 Eui最大化的策略），即：?xi∈Ai，i=1，2，…，n 成立。

支付函數(shù)是關(guān)于所有參與人各種可能的策略組合的函數(shù)。如果支付函數(shù)是策略的多元連續(xù)函數(shù)，則可以求得每個參與人針對其他參與人所有策略組合的最優(yōu)反應(yīng)構(gòu)成的函數(shù)，稱為反應(yīng)函數(shù)（一般地定義為其他人策略不變時，參與人i的最優(yōu)策略，記為Ri(x-i)，反應(yīng)函數(shù)由決定，即固定其他人策略不變，求ui=ui(x1，x2，…，xn)的最大值）而各參與人的反應(yīng)函數(shù)的交點（如果有的話）就是納什均衡。

在ui可微時，且博弈中納什均衡存在，可由下面n個方程聯(lián)立來求得納什均衡（即各參與人的反應(yīng)函數(shù)的交點）

（1）固定 x-i=(x1，…，xi-1，xi+1，…，xn)，求，使得 maxui=(x1，x2，…，xn)；

（3）判斷是否是納什均衡？

但這只是博弈論書中常見的最為簡單的情形。本文針對求解第一步做更深入的探討，即固定 x-i=(x1，…，xi-1，xi+1，…，xn)，求，使得 maxui=ui(x1，x2，…，xn)。

2 基于模糊K-Modes聚類技術(shù)的多目標(biāo)進(jìn)化算法

2．1 模糊K-Modes聚類分析改進(jìn)算法

在統(tǒng)計方法中，聚類稱為聚類分析，主要研究基于幾何距離的聚類，如歐式距離、明考斯距離，它需要考察所有的個體才能決定類的劃分，不能動態(tài)增加新的數(shù)據(jù)對象。

由于多目標(biāo)優(yōu)化屬于向量評估，故這里采用在模糊KModes聚類算法基礎(chǔ)上改進(jìn)的聚類分析算法，它是對具有分類屬性的數(shù)據(jù)進(jìn)行聚類的一種有效算法。

給定數(shù)據(jù)集 X={X1，X2，…，Xn}，即為一組數(shù)據(jù)元組。 其中每個元素包含 m 個屬性，即 Xi=[xi1，xi2，…，xim](i=1，2，…，n)表示具有m個屬性的數(shù)據(jù)對象，屬性變量j=1，2，…，m。

模糊聚類就是將X劃分為k類(2≤k≤n)，即假定聚類個數(shù)是 k，聚類變量 l=1，2，…，k，Q={Q1，Q2，…，Qk}，代表原形模型，Q1=[ql1，ql2，…，qlm]代表聚類 l的原形模型，也稱為聚類中心。

在模糊劃分中，每一個元素不能嚴(yán)格地被劃分到某一類，而是以一定的隸屬度屬于某一類，令uli表示第i個元素屬于第 l類的隸屬度，uli∈

以代價函數(shù)最小作為聚類的準(zhǔn)則，代價函數(shù)的定義如下[39]：

其中d(Ql，Xi)=||Ql-Xi||為差異測度，表示元素與聚類中心Ql之間的距離：

式中，當(dāng) x=q 時，δ(p=q)=0；否則，δ(p=q)=1，xij，qij是在第 j個分類屬性的數(shù)據(jù)，劃分矩陣的更新如下：

當(dāng) Xi=Ql時，uli=1；當(dāng) Xi=Qh，且 h≠l時，uli=0；其它情況時，有

算法的基本流程如下：

第1步 隨機產(chǎn)生c個中心；

第2步 計算聚類中心Q；

第3步 修正U；

第4步 如果有兩個中心之間的距離小于最小聚類距離d，則將這兩個中心合并；

第5步 對給定的閥值ε＞0，以一種合適的矩陣范數(shù)比較 U(t)和 U(t+1)，若

||U(t+1)-U(t))||≤ε

則算法終止，否則t=t+1，轉(zhuǎn)向第2步；

第6步 如果某個中心發(fā)生變化，轉(zhuǎn)到第3步；計算結(jié)束，返回k個中心位置。

使用改進(jìn)后的算法產(chǎn)生出來的聚類數(shù)目K可能小于預(yù)定值C，這反映了群體中實際的生境數(shù)目。

算法所得的U是一個模糊劃分矩陣，算法的基本思想是：迭代調(diào)整(U,V)，即交替更新聚類中心和劃分矩陣，直到代價函數(shù)值達(dá)到最小。聚類技術(shù)可以確保在變量空間兩個個體的競爭是局部的。

2．2 基于模糊K-Modes聚類技術(shù)的多目標(biāo)進(jìn)化算法

設(shè)多目標(biāo)優(yōu)化問題為：

下面給出采用本文所介紹的方法形成的多目標(biāo)進(jìn)化算法。

2.2.1 算法基本流程

第1步 輸入種群規(guī)模、交叉概率Pc、變異概率Pm，Pareto選優(yōu)過濾器，迭代次數(shù)；

第2步 利用隨機權(quán)數(shù)法獲得初始種群，并利用隨機模擬方法檢查可行解；

第3步 計算個體競爭適應(yīng)度，得到初始Pareto選優(yōu)過濾器；

第4步 每隔若干代，使用改進(jìn)的K-means算法對群體進(jìn)行聚類分析，劃分為個聚類；

第5步 計算每個聚類中個體的數(shù)目，計算個體的競爭適應(yīng)度；按照個體的競爭適應(yīng)度進(jìn)行常規(guī)的選擇、重組、變異操作，生成子代；

第6步 確定子代屬于哪個聚類，計算子代與子代或兩父本之間的相似性度量，按照一定概率替換最接近的父代；

第7步 利用小生境技巧迭代種群和Pareto選優(yōu)過濾器；檢查是否達(dá)到迭代次數(shù)，若是，轉(zhuǎn)第6步。若否，轉(zhuǎn)第5步，循環(huán)執(zhí)行操作第2步至第5步，直到達(dá)到預(yù)定的結(jié)束條件；

第8步 將Pareto選優(yōu)過濾器、滿意度、可行度提交決策者，讓其判別是否滿意。

算法中生境的確認(rèn)是通過聚類分析得到的，而不是由生境半徑?jīng)Q定的[3]，這就不必預(yù)先定義生境半徑，使得各種大小形狀不同的生境可以被同時發(fā)現(xiàn)。

再分析競爭適應(yīng)度的取法。生境中物種的數(shù)量取決于生境的負(fù)荷能力和每一個物種對生境能力的利用程度。在資源有限的情況下，群體規(guī)模的增長可以使用Logistic方程N=m×Nt×(1-Nt/K)來模擬，其中m是群體的名義增長率，K是環(huán)境的負(fù)荷量。生境能夠負(fù)荷的最大個體數(shù)量直接和生境的負(fù)荷能力成正比，負(fù)荷能力由生境峰值的適應(yīng)度和域內(nèi)其他極值點的適應(yīng)度來決定。

競爭適應(yīng)度的含義與共享適應(yīng)度相類似，均反映了由于生境中個體的數(shù)目而導(dǎo)致的適應(yīng)度的下降，公式如下：

fci=(1-c×xi)×fi

其中c為擁擠參數(shù)（0＜c＜1，在實際使用時一般取接近于1的數(shù)，如0.8），反映了群體的擁擠程度，公式形式上類似于自然界有限資源下種群增長的Logistic方程。

2.2.2 應(yīng)用舉例

因為再復(fù)雜的博弈模型的支付函數(shù)，都可描述為類似于下面的形式，所以這里選用一組常用的多目標(biāo)優(yōu)化的測試問題[3]中的一個，驗證文中給出的算法。

其中，X=(x1，…，xn)，n=30，xi∈[0，1]。

和文獻(xiàn)[3]中的算法進(jìn)行比較，由于非劣前沿已知，容易進(jìn)行比較。這里采用每隔10代進(jìn)行一次聚類分析，樂觀系數(shù)為0.8。采用兩點交叉，變異算子中δ=0.01，參數(shù)Pc=0.80，Pm=0.02。優(yōu)化區(qū)間取為[-10,10]，群體規(guī)模N=100。檢驗算法性能的方法是統(tǒng)計進(jìn)化到若干代后產(chǎn)生的最優(yōu)解數(shù)目，終止代數(shù)分別為50，100，200，各進(jìn)行了10次實驗。本算法求出的非劣解的數(shù)量多，且分布均勻。

進(jìn)化算法程序用Matlab語言編寫，系統(tǒng)模擬可以在一個計算環(huán)境中執(zhí)行[4]。

3 總結(jié)

由于博弈論中的不同類型的博弈模型求解都要用到反應(yīng)函數(shù)法，本文針對反應(yīng)函數(shù)法的缺陷進(jìn)行了改進(jìn)。嘗試將數(shù)學(xué)優(yōu)化領(lǐng)域的進(jìn)化計算技術(shù)引入博弈論中，針對博弈模型的求解技巧進(jìn)行探討。將收益支付函數(shù)擴展到解決有約束、多目標(biāo)的函數(shù)形式。若支付函數(shù)是有約束的單目標(biāo)優(yōu)化問題，納什均衡在最優(yōu)中進(jìn)行尋找；若支付函數(shù)是有約束、多目標(biāo)的復(fù)雜函數(shù)形式，納什均衡在非劣解中進(jìn)行尋找。進(jìn)一步的研究是應(yīng)針對有具體實際應(yīng)用背景的博弈模型進(jìn)行探討。

[1]于維生.博弈論與經(jīng)濟(jì)[M].北京：高等教育出版社，2007.

[2]吳廣謀，呂周洋.博弈論基礎(chǔ)及應(yīng)用[M].南京：華南大學(xué)出版，2009.[3]倪勤.最優(yōu)化方法與程序設(shè)計[M]北京：科學(xué)出版社，2009.

[4]龔純，王正林.精通MATLAB最優(yōu)化計算[M].北京：電子工業(yè)出版社，2009.