基于決策概率逼近的矩陣對策近似求解方法

何煉堅 冷國俊 蒲春霞

【摘要】本文提出一種面向大規模矩陣對策問題，基于決策概率逼近的可快速收斂到近似最優策略的求解方法.

【關鍵詞】矩陣對策;局中人;策略

【基金項目】本論文由國家自然科學青年基金（51605452）資助.

一、引?言

對一般性的矩陣對策問題，通常使用線性規劃法，將原問題轉化為等價的線性規劃問題，利用單純形或對偶單純形法求解.該方法的缺點在于，對大規模的矩陣對策問題，求解線性規劃的開銷太大.

本文提出一種基于決策概率逼近的矩陣對策策略確定方法.該方法依賴于以下準則：一是矩陣對策雙方都會根據期望收益最大（或期望損失最小）原則進行分析，即根據每個決策方案的期望收益（或期望損失）來對方案進行比較，從中選擇期望收益最大（或期望損失最小）的方案;二是決策方案選擇的概率分布是關于其期望收益的單調上升函數（或關于其期望損失的單調下降函數）.

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

矩陣對策問題模型包括以下基本要素：

（1）局中人

以I表示局中人的集合;矩陣對策包括兩個局中人，因此，I中元素的個數為2.

（2）策略

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

（3）收益函數

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

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

（1）局中人1

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

使用最新計算出的局中人2所有策略的期望收益，計算局中人2的策略選擇概率分布（計算函數要求是局中人2的期望收益的嚴格單調上升函數）.

（2）局中人2

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

使用最新計算出的局中人1所有策略的期望收益，計算局中人1的策略選擇概率分布（計算函數要求是局中人1的期望收益的嚴格單調上升函數）.

只要為局中人1（或局中人2）的策略選擇概率分布給出一個初始值（從而可以計算局中人2或局中人1的所有策略的期望收益），就可以驅動上述迭代計算，以（1）或（2）為開始.迭代計算應該在判斷局中人1和局中人2的策略選擇概率分布都收斂的時候終止.

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

（1）設置初值

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

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

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

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

如下計算m維向量f和h：

f=Rg，

h=h（0），∑mi=1F（fi）=0時，[F（f1），…，F（fm）]T∑mi=1F（fi），其他情況，

其中

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

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

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

∑mi=1hi=1.

函數F滿足：

F（0）=0，且F（x）關于x嚴格單調上升.

特別的，對函數F（x）=x，有：

h=h（0），∑mi=1fi=0時，

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

f，h的計算反映了局中人1的策略選擇概率是關于其策略期望收益的嚴格單調上升函數.

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

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

如下計算n維向量e，q和g：

e=-RTh，

q=0，…，1C，…，0T，滿足G（ej）=0的下標共有C（0

其分量值為1C，其中j為分量下標;

滿足G（ej）<0的下標共有n-C（0

其分量值為0，其中j為分量下標

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

g=g（0），∑nj=1G（qj）=0時，

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

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

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

∑nj=1gj=1，

q為計算g用到的中間向量.

函數G滿足：

G（0）=0，且G（x）關于x嚴格單調上升.

特別的，對函數G（x）=x，有：

g=g（0），∑nj=1ej=0時，

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

e，q，g的計算反映了局中人2的策略選擇概率是關于其策略期望收益的嚴格單調上升函數.

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

完成上述計算后轉（2）.（2）執行完后又會轉（3）.

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

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

deviation_g=max1≤j≤n（deviation_gj），

deviation_h=max1≤i≤m（deviation_hi），

其中：

deviation_gj=|gj-gprevj|，gprevj=0時，

|（gj-gprevj）/gprevj|，gprevj≠0時，

deviation_hi=|hi-hprevi|，hprevi=0時，

|（hi-hprevi）/hprevi|，hprevi≠0時.

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

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

L=L+1，當deviation_g

deviation_h

0，其他.

這里MINEPS為預設精度.

如果L值達到預設門限Lmax（Lmax≥1），那么判斷g，h均收斂，迭代結束，否則繼續迭代.

說明：不同場景中，g，h的收斂速度是不一樣的，為了確保計算在可接受的迭代次數內結束，可以設置迭代次數門限，當迭代次數達到該門限時，無論g，h是否滿足收斂條件，都結束迭代計算，并以結束迭代時的g和h分別作為局中人1和2的近似最優策略.

三、數值實驗

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

上述計算實驗可以持續進行多輪（每次只有收益矩陣不同）.實驗的結果如下：

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

四、結束語

本文提出的基于決策概率逼近的矩陣對策近似求解方法，能夠快速收斂到大規模矩陣對策問題的近似最優策略，對博弈決策的實際應用具有重要的意義.

【參考文獻】

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