網格資源分配博弈的隨機動態分析
2009-01-01 00:00:00李志潔
計算機應用研究 2009年3期
(大連民族學院 計算機科學與工程學院， 遼寧 大連 116600)
摘 要：針對網格資源分配的優化問題，提出利用隨機動態來研究有限網格群體博弈的分析方法。通過建立網格使用者策略選擇的隨機模型來分析有限網格群體的博弈，并利用期望效用生成選擇過程的量化指標來判斷使用者在反復博弈中策略選擇的變化方向及其穩定性。最后通過仿真實例的研究結果表明，在效用矩陣不變的情況下，群體規模是影響網格使用者策略選擇方案的一個重要因素。
關鍵詞：網格； 資源分配； 博弈； 隨機動態
中圖分類號：TP393 文獻標志碼：A
文章編號：10013695(2009)03085203
Stochastic dynamics analysis of resource allocation game in grid environment
LI Zhijie
(School of Computer Science Engineering， Dalian Nationalities University， Dalian Liaoning 116600， China)
Abstract:To address the problem of optimal allocation of grid resource， this paper proposed an analysis method for studying the game with finite population using stochastic dynamics. Established stochastic model for user strategy selections to study the game with finite population. According to the expectation utilities of user， produced invasion and fixation rates to quantify selection pressure during the repeated games. Finally， detailed the effects of population size on selection scenario under fixed utility matrix through example. The results show that the grid population size is a vital factor to effect the strategy selection of user that aims to maximize its own utility in grid resource allocation.
Key words：grid; resource allocation; game; stochastic dynamics
網格技術[1，2]研究的核心問題是資源共享。與其他環境下的資源相比，網格中的資源具有數量龐大、異構性強、變化頻繁、傳輸快速、共享程度高等特點。因此，資源管理是一個復雜的過程。要改善網格分散管理所帶來的不足，需要采用分布的、協作的和智能化的方式。由于不同個體之間存在著價值差異，且同時具有競爭和共享的關系，由競爭個體構成的網格資源管理系統[3]可以看成是一個博弈系統。目前有許多研究試圖利用博弈論[4~6]的成果來優化網格資源的配置以及分析個體的競爭行為。這些研究大致可分為兩類：a)在完全理性條件下研究網格個體之間的利益之爭。這類方法[7~10]的不足在于采用的是一種完全理性假設，即要求博弈方始終以自身最大利益為目標并具有完美的判斷和預測能力。事實上，這種完全理性的要求無法滿足，個體在策略選擇上經常會犯錯誤。b)有限理性條件下網格個體之間的博弈研究。這些方法[11~13]雖然考慮了個體理性的局限性，并通過反復博弈達到策略均衡，但大多假設個體數量是無限的，這樣博弈的結果仍處于一定程度的理想狀態。目前，網格環境中的個體數量有限，分析能力和預見能力差別較大，其策略均衡問題有待進一步解決。
本文針對網格中的資源分配問題，以及不同網格個體之間的利益競爭和相互影響的特點，利用隨機動態方法研究有限網格群體的博弈過程，并與無限網格群體的博弈結果進行了比較，討論了無限網格群體博弈的穩定均衡與有限網格群體博弈的選擇動態之間的關系，并以實例分析了效用矩陣固定時，網格個體為了效用最大化，其選擇方案隨群體規模的變化過程。
1 網格資源分配博弈的理論建模
1.1 網格博弈的問題描述
假設網格系統中有N個使用者競爭同一個有限的網格資源，而且使用者出價相對越高，使用的資源比例相對越多。每個使用者需向資源提交一個出價bi∈R，則b=[b1，…，bN]表示所有競爭者的出價。假定資源分配遵循基于權重的比例共享原則，而且每個網格使用者對于得到的分配mi都有一個評估vi(mi)，這個評估可以是資源份額函數的性能測量。比如計算市場中完成作業的時間，或者是在給定的網絡帶寬份額下傳送數據的時間。每種性能測量都被轉換為一個等價值，且能與費用相比較。若網格使用者的評估函數是連續可微的，則其效用定義為評估值與支付費用之差：
Ui(bi)=vi(mi(bi))-bi=vi(bi/∑Nj=1bj)-bi(1)
本文將博弈系統中進行出價博弈的網格使用者群體抽象為兩個個體的群體。在出價博弈過程中，假定每個網格使用者都面臨兩種出價策略選擇，即主導策略或變異策略，網格使用者選擇不同的出價策略所獲得的效用水平由式(1)計算，由此構造一個隨機配對的博弈框架，可用表1所示的2×2矩陣來表示。網格使用者的策略以預算E為基礎，一種出價對應一種策略。
若網格群體中采用主導策略E/k的使用者比例為x(0≤x≤1)，則采用變異策略E的使用者比例為1-x。由效用矩陣可算出選擇兩種策略網格使用者的期望效用分別為
f(E/k，x)=x×[v(1/2)-E/k]+(1-x)×{v[1/(k+1)]-E/k}(2)
f(E，1-x)=x×{v[k/(k+1)]-E}+(1-x)×[v(1/2)-E](3)
根據式(2)(3)，可得到群體的平均期望效用：
f(x，x)=x×f(E/k，x)+(1-x)×f(E，1-x)(4)
1.2 無限網格群體博弈的穩定點分析
按照生物進化復制動態的思想，采用策略所得效用低于群體平均效用的博弈方會改變自己的策略，轉向另一個策略，群體中采用不同策略成員的比例就會發生變化，特定策略比例的變化速度與其期望效用超過平均期望效用的幅度成正比。因此，在上述問題中采用主導策略E/k的博弈方，其比例x的變化速度可用復制動態機制[14]表示為
dx/dt=x[f(E/k，x)-f(x，x)]=x(1-x)[x(v(1/2)-v(1/(k+1)))+(1-x)(v(k/(k+1))-v(1/2))](5)
將式(5)簡記為dx/dt=F(x)。令F(x)=0就可解出復制動態方程的穩定點x*。上述復制動態最多可能有三個穩定點，分別是0、1、[y(1/2)-v(k/(k+1))]/[v(1/2)-v(k/(k+1))+v(1/2)-v(1/(k+1))]。但是具有真正穩定性的穩定狀態還必須對微小的擾動具有穩定性，這要求在穩定點處F(x)的導數F′(x*)＜0。由式(5)可得
F′(x)=x(2-3x)(v(1/2)-v(1/(k+1)))+(1-x)(1-3x)(v(k/(k+1))-v(1/2))(6)
再根據網格主體的效用矩陣求解式(6)，滿足F′(x*)＜0的點即是該博弈的進化穩定點。有如下四種情況：a)如果v(1/(k+1))＜v(1/2)＜[v(1/(k+1))+v(k/(k+1))]/2，則x*=1是進化穩定點；b)如果v(k/(k+1))＜v(1/2)＜[v(1/(k+1))+v(k/(k+1))]/2，則x*=0是進化穩定點；c)如果v(1/2)＜v(1/(k+1))且v(1/2)＜v(k/(k+1))，則x*=[y(1/2)-v(k/(k+1))]/[2v(1/2)-v(k/(k+1))-v(1/(k+1))]是進化穩定點；d)如果v(1/2)＞v(1/(k+1))且v(1/2)＞v(k/(k+1))，則有兩個點x*=0和x*=1是進化穩定點。
1.3 有限網格群體博弈的隨機動態過程
本節對于使用者數量有限的群體博弈，研究其反復博弈的隨機過程。已知網格模型中有N個競爭資源的使用者，假設選擇主導策略E/k的使用者數量為n，由于每個使用者要與其他所有的使用者博弈，選擇該策略的使用者比例為(n-1)/N，根據式(2)可知選擇該策略的使用者期望效用為
f(E/k，n/N)=(n-1)/N×(v(1/2)-E/k)+(N-n)/N×(v(k/(k+1))-E)(7)
而選擇變異策略E的使用者數量為N-n，同樣的原理，其比例為(N-n-1)/N。所以根據式(3)選擇該策略的使用者期望效用表示為
f(E，(N-n)/N)=n/N×(v(1/(k+1))-E/k)+(N-n-1)/N×(v(1/2)-E)(8)
根據隨機動態機制[15]在每次階段博弈中，網格使用者要按照正比例原則，根據其期望效用來復制后代，這個復制的后代會將一個隨機選擇的使用者替換掉，所以網格群體的數量仍然保持為N。令f＾n=f(E/k，n/N)，f~n=f(E，(N-n)/N)，那么一個選擇主導策略E/k的使用者復制其后代的概率為n×f＾/[n×f＾n+(N-n)f~n]。選擇主導策略的使用者數量每次博弈后的變化情況有三種，即增加一個、保持不變和減少一個。本文用Pn表示保持不變的概率，Pn+表示增加一個的概率，Pn-表示減少一個的概率。其表達式如下所示：
Pn+=n×f＾n/[n×f＾n+(N-n)f~n]×(N-n)/N(9)
Pn-=(N-n)f~n/[n×f＾n+(N-n)f~n]×n/N(10)
Pn=1-Pn+-Pn-(11)
由于同一類型的使用者不可能增加或減少兩個以上，網格群體狀態變化的概率矩陣只有三條對角線，其他概率均為零。
P1P1+0000P2-P2P2+00
00P3-P3P3+0000OOO0000PN-3PN-2PN-10000PN-2PN-1
(12)
這個概率矩陣中，n的取值為1~(N-1)。還有兩個關鍵的邊界狀態，即n=0和n=N。如果網格群體達到這兩個狀態，就會穩定不再變化；否則，仍有變化的可能。下面計算網格群體達到這種邊界狀態的概率。用pn表示選擇主導策略E/k的使用者數量從n變化到N的概率，則pn滿足一個遞歸方程：
pn=Pn+×pn+1+Pn×pn+Pn-1×pn-1(13)
因為網格群體達到邊界狀態時就會穩定不再變化，式(13)具有兩個邊界條件p0=0和pN=1。p0=0表示群體中沒有使用者選擇主導策略時，該類型使用者數量變為N的可能性為0；pN=1表示群體中所有使用者都選擇主導策略時，該群體狀態不再變化。換句話說，使用者選擇變異策略的可能性為0。將式(12)代入(13)， 解此方程得
pn=Pn+×pn+1+(1-Pn+-Pn-)×pn+Pn-×pn-1=Pn+×(pn+1-pn)-Pn-×(pn-pn-1)+pn(14)
令tn=pn+1-pn，則式(14)可改寫為
tn=Pn-/Pn+×tn-1(15)
合并式(10)(11)(15)得
tn=f~k/f＾k×tn-1(16)
先代入邊界條件p0=0，得
tn=∏nk=1f~k/f＾k×p1pn=(1+∑n-1j=1∏jk=1f~k/f＾k)×p1(17)
再代入邊界條件pN=1，得
p1=1/（1+∑N-1j=1∏jk=1f~k/f＾k）
(18)
合并式(17)(18)，最終得到概率pn的函數解：
pn=[1+∑n-1j=1∏jk=1f~k/f＾k]/[1+∑N-1j=1∏jk=1f~k/f＾k](19)
式(19)的含義為選擇主導策略的網格使用者數量從n變化到N的概率。根據式(19)還可以導出兩個重要的概率，分別是網格群體中只有一個選擇主導策略的使用者時，其數量從1變化到N的概率：
δ＾=p1=1/(1+∑N-1j=1∏jk=1f~k/f＾k)(20)
以及網格群體中只有一個選擇變異策略的使用者時，其數量從1變化到N的概率：
δ=1-pN-1=∏N-1k=1f~k/f＾k/(1+∑N-1j=1∏jk=1f~k/f＾k)(21)
利用概率δ＾與δ，可以判斷當前網格群體的策略選擇穩定性，稱之為穩定指標。也就是說，當概率δ＾較大時，選擇主導策略的使用者全面替代群體的可能性很大；而當概率δ較大時，選擇主導策略的使用者將被消滅的可能性也較大，取而代之的是選擇變異策略的使用者。另一個判斷群體變化方向的指標是
gn=f＾n/f~n;n=1，…，N-1(22)
gn稱為侵蝕指標。其中g1和gN-1的值是否大于1說明在只有一個使用者選擇主導策略(變異策略)的群體中，該使用者的期望效用是否大于群體的期望效用。侵蝕指標g與穩定指標δ的區別在于：g的形式簡單，是效用矩陣和變量N的函數，主要用于判斷有n個使用者選擇主導策略時，下一步該類型使用者是增加還是減少；而δ的表達式比較復雜，是用于衡量博弈趨于穩定狀態的概率，若兩種策略具有相同的效用，那么δ＾=δ=1/N，可以此1/N為基準來研究一種策略全面替代另一種策略的傾向性。當使用者的效用矩陣固定時，指標g和δ會隨著N的變化呈現不同的結果，在N變化時，可以用g和δ判斷使用者的選擇方案。下面以一個仿真例子來具體描述這種策略選擇的隨機過程。
2 網格策略選擇博弈的仿真算例及分析
本文以2×2的效用矩陣為例，博弈方有兩種策略可供隨機選擇，即主導策略E/k和變異策略E。令k=2，E=2
G$(G$表示網格貨幣單位)，則出價策略分別為1和2G$。按照正比例資源共享的原則，若網格使用者都選擇主導策略(變異策略)時，博弈雙方所獲得的資源份額均為1/2；若選擇主導策略的使用者遇到選擇變異策略的使用者時，所獲得的資源份額為1/3；若選擇變異策略的使用者遇到選擇主導策略的使用者時，所獲得的資源份額為2/3。將評估函數設為vi(mi)=8 ln(1+mi)。其中mi為第i個網格使用者分得的資源份額。根據式(1)的定義可知使用者得到的效用等于評估與出價之差。表2是賦值后的效用矩陣。
由1.3節無限群體博弈的穩定點分析可知，當k=2時，不等式v(1/(k+1))＜v(1/2)＜[v(1/(k+1))+v(k/(k+1))]/2成立，因此，x*=1是進化穩定點。經過多次反復博弈，網格使用者都會選擇主導策略，即出價1 G$，博弈結果是一個純策略納什均衡。從另一個角度分析，由于v(1/2)-E/k+v(1/(k+1))-E/k＞v(k/(k+1))-E+v(1/2)-E′，即2.24+1.30＞2.08+1.24，對于大規模的網格群體來說，使用者不會選擇效用較低的變異策略。
由第1.3節有限群體博弈的隨機過程可知，當效用矩陣固定時，侵蝕指標g(式(22))與穩定指標δ(式(20)(21))都是群體規模N的函數，如圖1~4所示。由于效用矩陣不變，圖1中使用者的期望效用在群體規模增大時只有微小的變化。圖2中穩定指標δ隨著群體規模N的增加而急劇下降，特別是在N較大時，δ的值已經非常小。這是因為在小的群體中，使用者之間的相互影響使得一種策略很容易就占據了上峰；但是在大規模群體中，使用者間達成一致的可能性就比較小。
圖3和4顯示了g與δ隨著N的變化而改變，從而導致群體規模N不同時，網格使用者的選擇方案不同。主要有如下五種情況：
a)當群體規模N∈[2，7)時，穩定指標滿足條件δ＾＜1/N＜δ，侵蝕指標滿足條件g1，gN-1＜1，此時，網格使用者傾向于選擇變異策略，即出價2G$。
b)當群體規模N∈[7，8]時，穩定指標滿足條件δ＾＜1/N＜δ，侵蝕指標滿足條件g1＜1＜gN-1，此時，網格使用者雖然傾向于選擇變異策略，但是選擇主導策略的使用者不會被完全消滅。
c)當群體規模N∈(8，11)時，穩定指標滿足條件δ＾，δ＜1/N，侵蝕指標滿足條件g1＜1＜gN-1，此時，網格群體處于穩定狀態，也就是說網格使用者基本保持原來的策略不變。
d)當群體規模N∈[11，15]時，穩定指標滿足條件δ＜1/N＜δ＾，侵蝕指標滿足條件g1＜1＜gN-1，此時，網格使用者雖然傾向于選擇主導策略，但是選擇變異策略的使用者不會被完全消滅。
e)當群體規模N∈(15，100]時，穩定指標滿足條件δ＜1/N＜δ＾，侵蝕指標滿足條件g1，gN-1＞1，此時，網格使用者傾向于選擇主導策略，即出價1 G$，而選擇變異策略的使用者將最終被消滅。
3 結束語
網格系統的特殊性質使得網格使用者間的關系十分復雜，為了優化網格資源的配置，同時兼顧網格使用者的自身利益，本文結合博弈論中隨機動態的相關理論對網格使用者的競爭機制展開研究。
1)針對網格中資源配置的優化問題，提出了利用隨機動態來研究有限網格群體博弈的分析方法。根據這種分析方法，可以得到在效用矩陣不變的情況下，群體規模對個體選擇方案的影響，進而為網格使用者的協調管理提供借鑒。
2)該方法有兩個關鍵的量化分析指標：a)利用網格使用者期望效用生成的侵蝕指標，用于判斷使用者在反復博弈中策略選擇的變化方向；b)通過使用者策略選擇隨機模型導出的穩定指標，用于判斷使用者在博弈的隨機過程中策略選擇的其穩定性。
3)以仿真實例評估了這種有限網格群體博弈的分析方法，同時與無限網格群體博弈的結果進行了比較。在效用矩陣固定，且使用者以最大化個人效用為目標時，大規模有限網格群體博弈與無限網格群體博弈的結果一致，而小規模有限網格群體博弈中使用者的選擇方案依賴于群體規模。
參考文獻：
［1］FOSTER I， KESSELMAN C， TUECKE S. The anatomy of the grid: enabling scalable virtual organizations[J]. International Journal of High Performance Computing Applications， 2001，15(3):200222
