何煉堅(jiān) 冷國(guó)俊 蒲春霞

【摘要】本文提出一種面向大規(guī)模矩陣對(duì)策問(wèn)題，基于決策概率逼近的可快速收斂到近似最優(yōu)策略的求解方法.

【關(guān)鍵詞】矩陣對(duì)策;局中人;策略

【基金項(xiàng)目】本論文由國(guó)家自然科學(xué)青年基金（51605452）資助.

一、引?言

對(duì)一般性的矩陣對(duì)策問(wèn)題，通常使用線性規(guī)劃法，將原問(wèn)題轉(zhuǎn)化為等價(jià)的線性規(guī)劃問(wèn)題，利用單純形或?qū)ε紗渭冃畏ㄇ蠼?該方法的缺點(diǎn)在于，對(duì)大規(guī)模的矩陣對(duì)策問(wèn)題，求解線性規(guī)劃的開(kāi)銷太大.

本文提出一種基于決策概率逼近的矩陣對(duì)策策略確定方法.該方法依賴于以下準(zhǔn)則：一是矩陣對(duì)策雙方都會(huì)根據(jù)期望收益最大（或期望損失最小）原則進(jìn)行分析，即根據(jù)每個(gè)決策方案的期望收益（或期望損失）來(lái)對(duì)方案進(jìn)行比較，從中選擇期望收益最大（或期望損失最?。┑姆桨?二是決策方案選擇的概率分布是關(guān)于其期望收益的單調(diào)上升函數(shù)（或關(guān)于其期望損失的單調(diào)下降函數(shù)）.

二、基于決策概率逼近的矩陣對(duì)策近似求解方法

矩陣對(duì)策問(wèn)題模型包括以下基本要素：

（1）局中人

以I表示局中人的集合;矩陣對(duì)策包括兩個(gè)局中人，因此，I中元素的個(gè)數(shù)為2.

（2）策略

可供局中人選擇的策略集記為Sz（z=1，2），其元素個(gè)數(shù)分別記為m和n;矩陣對(duì)策的m，n均為有限值.

（3）收益函數(shù)

局中人1的任一策略和局中人2的任一策略一起形成的策略組稱為一個(gè)局勢(shì)，該局勢(shì)下兩個(gè)局中人的收益由收益函數(shù)確定.所有局勢(shì)下局中人2的收益構(gòu)成一個(gè)m×n矩陣R，局中人1的收益構(gòu)成另一個(gè)m×n矩陣-R.不失一般性約定矩陣R滿足0≤Rij≤1（i=1，…，m，j=1，…，n）.

考慮某一局中人的任一策略，該策略的期望收益是與對(duì)方采取的策略有關(guān)的.如果能夠有效估計(jì)對(duì)方可能采取的策略，對(duì)提升期望收益是有利的.一種合理的想法是，認(rèn)為對(duì)方從其策略集中選擇某一策略的概率是關(guān)于該策略的期望收益的單調(diào)上升函數(shù)，即期望收益越大的策略的選擇概率越大，期望收益越小的策略的選擇概率越小.另一方面，對(duì)方計(jì)算其某一策略的期望收益時(shí)，必須由我方策略選擇的概率分布輸入，其同樣會(huì)認(rèn)為，我方從策略集中選擇某一策略的概率是關(guān)于該策略的期望收益的單調(diào)上升函數(shù).這樣就形成了如下迭代計(jì)算：

（1）局中人1

針對(duì)局中人1的策略選擇概率分布，計(jì)算局中人2所有策略的期望收益.

使用最新計(jì)算出的局中人2所有策略的期望收益，計(jì)算局中人2的策略選擇概率分布（計(jì)算函數(shù)要求是局中人2的期望收益的嚴(yán)格單調(diào)上升函數(shù)）.

（2）局中人2

針對(duì)局中人2的策略選擇概率分布，計(jì)算局中人1所有策略的期望收益.

使用最新計(jì)算出的局中人1所有策略的期望收益，計(jì)算局中人1的策略選擇概率分布（計(jì)算函數(shù)要求是局中人1的期望收益的嚴(yán)格單調(diào)上升函數(shù)）.

只要為局中人1（或局中人2）的策略選擇概率分布給出一個(gè)初始值（從而可以計(jì)算局中人2或局中人1的所有策略的期望收益），就可以驅(qū)動(dòng)上述迭代計(jì)算，以（1）或（2）為開(kāi)始.迭代計(jì)算應(yīng)該在判斷局中人1和局中人2的策略選擇概率分布都收斂的時(shí)候終止.

不失一般性，站在局中人1的立場(chǎng)，為局中人2的策略選擇概率分布給出初始值，則迭代計(jì)算的具體步驟如下：

（1）設(shè)置初值

記局中人2關(guān)于其策略集中策略的選擇概率向量為n維向量g，設(shè)定其初值如下：

g（0）=1n，…，1nT.

上面設(shè)置選擇概率向量初值時(shí)，認(rèn)為各策略的選擇概率均等;如果有更多的信息用于判斷各策略的選擇概率，也可以設(shè)置為其他向量值.不同初值的影響在于收斂的速度可能不同.

（2）計(jì)算局中人1的策略選擇概率向量

如下計(jì)算m維向量f和h：

f=Rg，

h=h（0），∑mi=1F（fi）=0時(shí)，[F（f1），…，F(xiàn)（fm）]T∑mi=1F（fi），其他情況，

其中

h（0）=[1m，…，1m]T.

這里R是局中人2的收益矩陣;f表示當(dāng)局中人2的策略選擇概率向量為g時(shí)，局中人1各策略的期望收益;h為局中人1的策略選擇概率向量，滿足：

0≤hi≤1，i=1，…，m，

∑mi=1hi=1.

函數(shù)F滿足：

F（0）=0，且F（x）關(guān)于x嚴(yán)格單調(diào)上升.

特別的，對(duì)函數(shù)F（x）=x，有：

h=h（0），∑mi=1fi=0時(shí)，

[f1，…，fm]T∑mi=1fi，其他情況，

f，h的計(jì)算反映了局中人1的策略選擇概率是關(guān)于其策略期望收益的嚴(yán)格單調(diào)上升函數(shù).

計(jì)算h時(shí)，當(dāng)∑mi=1F（fi）=0時(shí)h=h（0），實(shí)際上這時(shí)只要h滿足所有分量值屬于[0，1]，且其總和為1就可以（由F的定義，∑mi=1F（fi）=0等價(jià)于F（fi）=0（i=1，…，m），即局中人1的任意策略的期望收益效用都為最小值0，這種情況下局中人1無(wú)論如何選擇策略都無(wú)法改善處境，一般簡(jiǎn)單以均等概率選擇，即h=h（0））.

（3）計(jì)算局中人2的策略選擇概率向量

如下計(jì)算n維向量e，q和g：

e=-RTh，

q=0，…，1C，…，0T，滿足G（ej）=0的下標(biāo)共有C（0

其分量值為1C，其中j為分量下標(biāo);

滿足G（ej）<0的下標(biāo)共有n-C（0

其分量值為0，其中j為分量下標(biāo)

1G（e1），…，1G（en）T，其他情況，

g=g（0），∑nj=1G（qj）=0時(shí)，

G（q1），…，G（qn）∑nj=1G（qj），其他情況.

這里-R為局中人1的收益矩陣;e表示當(dāng)局中人1的策略選擇概率向量為h時(shí)，局中人2各策略的期望收益;g為局中人2的策略選擇概率向量，滿足：

0≤gj≤1，j=1，…，n，

∑nj=1gj=1，

q為計(jì)算g用到的中間向量.

函數(shù)G滿足：

G（0）=0，且G（x）關(guān)于x嚴(yán)格單調(diào)上升.

特別的，對(duì)函數(shù)G（x）=x，有：

g=g（0），∑nj=1ej=0時(shí)，

[e1，…，en]T∑nj=1ej，其他情況.

e，q，g的計(jì)算反映了局中人2的策略選擇概率是關(guān)于其策略期望收益的嚴(yán)格單調(diào)上升函數(shù).

計(jì)算g時(shí)，當(dāng)∑nj=1G（qj）=0時(shí)g=g（0），實(shí)際上這時(shí)只要g滿足所有分量值屬于區(qū)間[0，1]，且其總和為1就可以（由G的定義，∑nj=1G（ej）=0等價(jià)于G（ej）=0（j=1，…，n），即局中人2的任意策略的期望收益效用都為0，由于局中人2策略的期望收益屬于區(qū)間[-1，0]，這表明局中人2無(wú)論如何選擇策略都能取得最高的期望收益0，一般簡(jiǎn)單以均等概率選擇，即g=g（0））.

完成上述計(jì)算后轉(zhuǎn)（2）.（2）執(zhí)行完后又會(huì)轉(zhuǎn)（3）.

上述（2）（3）之間的往復(fù)迭代計(jì)算到g，h都收斂后結(jié)束.此時(shí)g和h分別是局中人1和2的近似最優(yōu)策略.g和h可能是純策略，也可能是混合策略.對(duì)混合策略不能接受（要求完全確定的策略）的情況，可以在可選的所有純策略中根據(jù)期望收益最大原則（或期望損失最小原則）選擇一個(gè)（假定對(duì)方采用混合策略）.

g，h的收斂判斷采用如下方法，記錄最近2次計(jì)算出的g，h值，并如下計(jì)算前后相繼的g之間的距離，以及前后相繼的h之間的距離：

deviation_g=max1≤j≤n（deviation_gj），

deviation_h=max1≤i≤m（deviation_hi），

其中：

deviation_gj=|gj-gprevj|，gprevj=0時(shí)，

|（gj-gprevj）/gprevj|，gprevj≠0時(shí)，

deviation_hi=|hi-hprevi|，hprevi=0時(shí)，

|（hi-hprevi）/hprevi|，hprevi≠0時(shí).

這里gj為當(dāng)前g的第j個(gè)分量值（j=1，…，n），gprevj為上輪迭代得到的g的第j個(gè)分量值（j=1，…，n），hi為當(dāng)前h的第i個(gè)分量值（i=1，…，m），hprevi為上輪迭代得到的h的第i個(gè)分量值（i=1，…，m）.

設(shè)置整數(shù)變量L的初值為0，如下在每次迭代中更新L：

L=L+1，當(dāng)deviation_g

deviation_h

0，其他.

這里MINEPS為預(yù)設(shè)精度.

如果L值達(dá)到預(yù)設(shè)門限Lmax（Lmax≥1），那么判斷g，h均收斂，迭代結(jié)束，否則繼續(xù)迭代.

說(shuō)明：不同場(chǎng)景中，g，h的收斂速度是不一樣的，為了確保計(jì)算在可接受的迭代次數(shù)內(nèi)結(jié)束，可以設(shè)置迭代次數(shù)門限，當(dāng)?shù)螖?shù)達(dá)到該門限時(shí)，無(wú)論g，h是否滿足收斂條件，都結(jié)束迭代計(jì)算，并以結(jié)束迭代時(shí)的g和h分別作為局中人1和2的近似最優(yōu)策略.

三、數(shù)值實(shí)驗(yàn)

在一輪計(jì)算實(shí)驗(yàn)中，設(shè)置局中人1和2的策略集合的元素個(gè)數(shù)范圍均為[128，1024]，預(yù)設(shè)精度為MINEPS=10-3.L值預(yù)設(shè)門限Lmax=5.判斷策略選擇概率向量g，h的收斂性.遍歷局中人1和2的策略集合元素個(gè)數(shù)組合（共有（1024-128+1）×（1024-128+1）=804609個(gè)），同時(shí)在[0，1]范圍內(nèi)隨機(jī)設(shè)置收益矩陣的元素，構(gòu)建矩陣對(duì)策問(wèn)題.按照前邊描述的方法迭代計(jì)算矩陣對(duì)策問(wèn)題的近似最優(yōu)策略（其中函數(shù)F，G分別設(shè)置為F（x）=x，G（x）=x），記錄收斂時(shí)的迭代次數(shù).

上述計(jì)算實(shí)驗(yàn)可以持續(xù)進(jìn)行多輪（每次只有收益矩陣不同）.實(shí)驗(yàn)的結(jié)果如下：

由上表可以看出，針對(duì)較大規(guī)模的矩陣對(duì)策問(wèn)題，本文提出的基于決策概率逼近的矩陣對(duì)策近似求解方法能夠在很少的幾次迭代（就我們的實(shí)驗(yàn)而言是6或7次）后收斂.

四、結(jié)束語(yǔ)

本文提出的基于決策概率逼近的矩陣對(duì)策近似求解方法，能夠快速收斂到大規(guī)模矩陣對(duì)策問(wèn)題的近似最優(yōu)策略，對(duì)博弈決策的實(shí)際應(yīng)用具有重要的意義.

【參考文獻(xiàn)】

[1]羅杰，B·邁爾森.博弈論：矛盾沖突分析[M].北京：中國(guó)經(jīng)濟(jì)出版社，2001.