孫　康，全宏俊

(華南理工大學(xué)物理系，廣東廣州510641)

?

多數(shù)者博弈模型演化分析

孫康，全宏俊

(華南理工大學(xué)物理系，廣東廣州510641)

摘要：為研究經(jīng)紀人行為策略對社會經(jīng)濟復(fù)雜系統(tǒng)的影響，本文在少數(shù)者博弈模型的基礎(chǔ)上提出多數(shù)方獲勝的基本多數(shù)者博弈模型以及演化多數(shù)者博弈模型。采用多主體建模方法，模型中的眾多經(jīng)紀人被賦予有限理性，他們可以選擇自己的最優(yōu)策略或者調(diào)整策略概率來競爭有限資源，演化到穩(wěn)態(tài)后也能表現(xiàn)出人類社會系統(tǒng)所獨有的現(xiàn)象。在基本少數(shù)者博弈中，當模型中的游戲規(guī)則變?yōu)槎鄶?shù)方獲勝時，得到的基本多數(shù)者博弈模型可以更快演化到穩(wěn)定狀態(tài)。并且在歷史記憶長度m較小的時候系統(tǒng)資源利用率較高，隨著m增大資源利用率逐漸降低，最終與經(jīng)紀人隨機選擇得到的結(jié)果一致。而演化多數(shù)者博弈模型的資源利用率則不受m影響，因此在m較大時，引入演化能提高資源利用率。同樣的系統(tǒng)參數(shù)，隨機初始條件不同演化多數(shù)者博弈模型經(jīng)紀人概率也有可能分布在p=0.5不同側(cè)。同時發(fā)現(xiàn)，穩(wěn)定后每時步平均獲勝方人數(shù)與經(jīng)紀人概率分布也有聯(lián)系，在經(jīng)紀人概率重置時采用不同的邊界條件，得到的經(jīng)紀人概率分布也不同。進一步分析演化多數(shù)者博弈模型系統(tǒng)資源利用率，發(fā)現(xiàn)經(jīng)紀人新舊策略概率的相關(guān)程度r越大，概率分布越平坦，系統(tǒng)資源利用率越高。增加獎懲比R，也會影響經(jīng)紀人概率分布，資源利用率也會提高。

關(guān)鍵詞：行為策略；少數(shù)者博弈模型；基本多數(shù)者博弈模型；演化多數(shù)者博弈模型；有限理性

0引言

1997年D. Challet和ZHANG Yicheng在Arthur“酒吧模型”[1]的基礎(chǔ)上提出了少數(shù)者博弈模型(MG)[2-5]。這是一個被高度重視并且廣泛研究的多經(jīng)紀人歸納博弈模型，模型的規(guī)則雖然簡單，但它是一個典型的自適應(yīng)復(fù)雜系統(tǒng)[6]，反映了許多社會與生態(tài)系統(tǒng)中多個體競爭有限資源并且少數(shù)方受益的現(xiàn)象。隨后該模型風(fēng)靡至今，得到顯著發(fā)展。從MG到演化少數(shù)者博弈模型(EMG)[7]，再到引入模仿學(xué)習(xí)的少數(shù)者博弈模型[8-9]，以及近年來探討的小世界網(wǎng)絡(luò)上模仿學(xué)習(xí)的少數(shù)者博弈模型[10-11]等等。隨著對少數(shù)者博弈模型的深入研究，該模型越來越復(fù)雜，也越來越接近現(xiàn)實。

生活中除了競爭有限資源的少數(shù)者博弈模型外，也存在主體行為策略是多數(shù)者策略(爭取使自己處于多數(shù)方)的博弈模型。比如集市模型[12]，居民去趕集，相互之間沒有任何交流與聯(lián)盟，只有在趕集人數(shù)達到一定閾值的情況下，才能達到便利交易的預(yù)期。反之，則不如待在家里。又比如客戶對社交軟件的選擇，自由市場中同一領(lǐng)域的社交軟件只有搶占到更多用戶才是勝者。因為對用戶而言，隨著使用該軟件產(chǎn)品用戶的增加，每個用戶從此產(chǎn)品中獲得的效用也會增加，才會吸引越來越多的經(jīng)紀人選擇該軟件產(chǎn)品。相反，參與人數(shù)少的社交軟件因為得不到理想的效用而使得用戶愈發(fā)減少，最終使該軟件產(chǎn)品淘汰。

1模型描述

1.1基本多數(shù)者博弈模型

將少數(shù)者博弈模型中的獲勝規(guī)則改為每一輪博弈結(jié)束時人數(shù)大于總?cè)藬?shù)一半的一方為獲勝方，其余規(guī)則保持不變，可得到基本多數(shù)者博弈模型。即，N(奇數(shù))個經(jīng)紀人，每個經(jīng)紀人有s個策略，在每一時步都獨立選擇加入“0”或“1”，其記憶容量為m，知道最近m時步的二進制取勝方記錄：u(t)={b(t-m)，…，b(t-2)，b(t-1)}，其中b(t)=“0”或“1”分別表示0方或1方取勝。每個經(jīng)紀人按照自己某個策略做出選擇后，人數(shù)多(少)的一方為獲勝(失敗)方，獲勝(失敗)方加1分(不加分)；并且給自己的s個策略評分(虛分)，如果某個策略預(yù)測了正確的獲勝方，這個策略加1分，預(yù)測失敗不加分；每一時步t，每個人根據(jù)t時步最近m次取勝方的記錄u(t)，采用得分最高策略的預(yù)測來選擇“0”或“1”，若得分最高的策略有2個以上，則隨機選取其中的一個來做預(yù)測。

1.2演化多數(shù)者博弈模型

在N. F. Johnson和P. M. Hui等人提出演化少數(shù)者博弈模型(EMG)[7]基礎(chǔ)上，改變經(jīng)紀人的主體行為策略，可得到演化多數(shù)者博弈模型。即，考慮N(奇數(shù))個經(jīng)紀人組成的系統(tǒng)，每個經(jīng)紀人事先知道最近出現(xiàn)的2m種不同歷史(每個歷史的長度為m比特)下取勝方的記錄。所有經(jīng)紀人擁有一個相同的策略，該策略在給定歷史條件下對下一次取勝方的預(yù)測與該歷史最近一次出現(xiàn)時的取勝方記錄相同。所有經(jīng)紀人隨機指定一個概率p(i)(i=1，…，N)，0≤p(i)≤1，對給定的歷史，每個經(jīng)紀人以概率p(i)按策略的預(yù)測作出決定，或者以概率1-p(i)作出與策略預(yù)測相反的決定。當每個經(jīng)紀人作出選擇后，處于多數(shù)(少數(shù))方的勝利(失敗)，勝利方獲得R分，失敗方減1分，獎懲比為R。當某個經(jīng)紀人財富小于給定的d(d<0)時，允許他在以p為中心、寬度為r的區(qū)間內(nèi)重新按均勻分布隨機挑選一個新的p(i)值，并將他的得分重新置零。采用反射邊界條件，p(i)<0時，p(i)=-p(i)，p(i)>1時，p(i)=2-p(i)，以保證概率0≤p(i)≤1。在這一進化博弈模型中的經(jīng)紀人可以不斷地從過去的錯誤中學(xué)習(xí)，總是試圖通過不斷改變自身對策略的參照來尋求與社會的最好適應(yīng)，而r則用來衡量經(jīng)紀人在修正其概率時新舊概率的關(guān)聯(lián)程度。

2結(jié)果與分析

2.1基本多數(shù)者博弈模型模擬結(jié)果

圖1給出了m=10，s=2和N=1 001時的基本多數(shù)者博弈模型在某初始條件(初始策略，初始歷史)下獲勝方人數(shù)隨時間變化的過程，通過數(shù)值計算發(fā)現(xiàn)獲勝方人數(shù)很快(102級時步)達到穩(wěn)定狀態(tài)。而同樣參數(shù)下的少數(shù)者博弈模型中獲勝方人數(shù)往往需要在104級以上時步才開始趨于動態(tài)平衡。

圖1　獲勝方人數(shù)隨時間演化Fig.1　Time evolution of the number of winners

對基本多數(shù)者博弈而言，由于經(jīng)紀人總是采用虛分最高的策略，所以在經(jīng)紀人的s條策略中，t-1時步被采用的策略(此策略虛分已經(jīng)大于或等于其他策略)在t時步繼續(xù)被采用的概率(可從t-1時步該策略加分和未加分兩種情況考慮)往往會高于t-1時步未被采用的策略，從而使經(jīng)紀人傾向于使用其s條策略中的某一條。當所有經(jīng)紀人都采用較固定的優(yōu)勢策略時，容易形成固定的結(jié)果和固定的歷史(可以從獲勝方人數(shù)隨時間的變化看出)，從而使系統(tǒng)快速達到穩(wěn)定狀態(tài)。

圖2給出了經(jīng)紀人平均成功率(所有經(jīng)紀人成功博弈次數(shù)與博弈總次數(shù)比值的平均)隨時間變化的過程，由多數(shù)者博弈規(guī)則，每一輪博弈中都有大于一半的經(jīng)紀人獲勝，經(jīng)紀人平均成功率也就大于0.5，并趨于穩(wěn)定。

圖2　經(jīng)紀人平均成功率隨時間演化Fig.2　Time evolution of the average success rate of the agents

在少數(shù)者獲勝規(guī)則下，穩(wěn)態(tài)下某一方經(jīng)紀人數(shù)的方差[13]越小則意味著系統(tǒng)資源利用率越高。然而多數(shù)者博弈模型并非零和博弈，在多數(shù)者博弈的同一回合中N個經(jīng)紀人完全有可能都是獲勝者。只是現(xiàn)實生活中，并非所有的經(jīng)紀人都可以相互約定同時選擇某一方。所以對多數(shù)者博弈模型而言，穩(wěn)態(tài)下博弈中多數(shù)方平均經(jīng)紀人數(shù)越接近N，則說明系統(tǒng)資源利用率越大。為此我們定義偏差θ：

(1)

其中T為系統(tǒng)穩(wěn)定時所需要的時步，Δt是系統(tǒng)穩(wěn)定后統(tǒng)計數(shù)據(jù)的時步。由圖3可見，偏差θ∝N，并且由圖4，對固定的m，有確定的相對偏差θ/N。所以θ/N表示一個與經(jīng)紀人數(shù)目無關(guān)的參量，相對偏差反映實際獲勝方人數(shù)與理想獲勝方人數(shù)之間偏差與理想獲勝方人數(shù)的比重，相對偏差越小說明越有效利用了市場資源。

圖3　m=3和m=8時，θ和經(jīng)紀人數(shù)目N的關(guān)系Fig.3　θ as function of N for m=3 and m=8

圖4　經(jīng)紀人數(shù)目N不同時，θ/N與m的關(guān)系Fig.4　θ/N as function of m for different values of N

圖5給出了N=1 001，s=2條件下相對偏差與m的關(guān)系，圖中每個數(shù)據(jù)點對應(yīng)128次獨立初始條件，在系統(tǒng)穩(wěn)定后，再對500時步的結(jié)果進行統(tǒng)計平均。我們發(fā)現(xiàn)基本多數(shù)者博弈模型中的平均相對偏差隨著m增大而增加，最終接近虛線所代表的經(jīng)紀人隨機作出選擇得到的相對偏差。

在少數(shù)者博弈模型中，由于周期2動力學(xué)過程[14]和經(jīng)紀人之間協(xié)作效應(yīng)的競爭關(guān)系，用來衡量系統(tǒng)資源利用率的方差與m的關(guān)系不是單調(diào)的，在某個m0處系統(tǒng)協(xié)作性最好。然而多數(shù)者博弈模型最重要的一個特點是：大多數(shù)人的預(yù)期一致時，實際情況會按照人們的預(yù)期發(fā)展，所以多數(shù)者博弈模型中不存在周期2動力學(xué)過程，并且在多數(shù)者博弈模型的歷史信息中同樣存在著有助于預(yù)測多數(shù)方的信息。當m較小時，策略池也比較小，導(dǎo)致很多經(jīng)紀人擁有相同的策略，由前文基本多數(shù)者博弈模型獲勝方人數(shù)隨時間演化過程分析，多數(shù)者博弈經(jīng)紀人也更容易采用他手中某條固定的策略。因此在多數(shù)者博弈過程中，面對同樣的歷史，經(jīng)紀人往往做出固定的決策，而這些固定的決策又形成了固定的歷史，這時候策略和歷史信息中預(yù)測勝利方的信息比較大。當m變大，策略池也變大，經(jīng)紀人的策略不盡相同，歷史也更多樣化，所以預(yù)測勝利方的信息也就隨m增大慢慢變少，最終接近隨機選擇得到的結(jié)果。

圖5　N=1 001，s=2時，θ/N與m的關(guān)系Fig.5　θ/N as function of m for N=1 001 and s=2

圖6　N=1 001，r=0.2，R=1，d=-4，θ/N與m的關(guān)系Fig.6　θ/N as function of m for N=1 001，r=0.2，R=1，d=-4

2.2演化多數(shù)者博弈模型模擬結(jié)果

圖6給出了演化多數(shù)者博弈模型的θ/N與m的關(guān)系。圖中的每個點對應(yīng)32次獨立初始條件，系統(tǒng)穩(wěn)定后再對500時步進行統(tǒng)計平均，由圖可見，演化多數(shù)者博弈模型的相對偏差與m無關(guān)。當m≥5時，演化多數(shù)者博弈模型可以比基本多數(shù)者博弈模型有著更高的資源利用率，即演化是有利的。

圖7　經(jīng)紀人概率分布Fig.7　Distribution P(p) of the p-values among the agents

圖7a、圖7b給出了演化多數(shù)者博弈模型概率分布，圖7a、圖7b有著相同的參數(shù)m=10，N=1 001，r=0.2，R=1，d=-4，但由于初始條件(初始概率、初始歷史和初始策略)會有所區(qū)別，我們得到分布于p=0.5不同側(cè)的“單峰分布”。

穩(wěn)定后每時步獲勝方人數(shù)

(2)

以圖7a為例說明經(jīng)紀人概率分布成因，在該次模擬初始概率隨機分布下，共有510位p>0.5的經(jīng)紀人，p>0.5的經(jīng)紀人有較大的概率屬于多數(shù)方，所以按公共策略決策的經(jīng)紀人更容易在每一輪博弈中獲勝，而p<0.5的經(jīng)紀人更傾向于執(zhí)行與公共策略相反的決策，從而在博弈中更容易處于少數(shù)方。對于p<0.5的某個經(jīng)紀人而言，由于每一輪博弈的失敗概率會大于獲勝概率，隨著時步t的增加，該經(jīng)紀人因得分逐漸小于d而被淘汰，然后對概率進行重置。由反射邊界條件可知，當新的p(i)<0時，p(i)=-p(i)，經(jīng)紀人的概率只能向p>0.5的方向演化。一旦p(i)>0.5，經(jīng)紀人i會因為獲勝的概率大于失敗的概率而很難被淘汰，同時也幾乎失去演化動力停留下來。于是對整個系統(tǒng)而言，p=0.5右側(cè)的經(jīng)紀人逐漸被積累，最終形成我們看到的尖峰形分布。

演化多數(shù)者博弈模型的概率分布是以p=0.5為中點，隨機分布在區(qū)間[0，0.5]或者區(qū)間[0.5，1]之間，并且演化多數(shù)者博弈模型穩(wěn)定后的概率分布形狀與經(jīng)紀人概率重置時采用的邊界條件有關(guān)。

圖8　具有不同策略p的經(jīng)紀人每時步平均得分Fig.8　Average rewards per round for the agents with different p-values

圖8a表示的是對應(yīng)圖7a模擬中(圖8b與圖7b對應(yīng)同一次模擬，初始隨機概率p>0.5的經(jīng)紀人數(shù)目為484人)演化到穩(wěn)態(tài)后得到的擁有不同策略p的經(jīng)紀人每時步平均得分，圖中每個點對應(yīng)一個經(jīng)紀人，縱坐標對應(yīng)著該經(jīng)紀人每時步的平均得分，橫坐標對應(yīng)經(jīng)紀人遵從策略的概率p。從圖8a中可以發(fā)現(xiàn)，經(jīng)紀人主要分布在p=0.5與p=0.65(與圖7a中尖峰寬度一致)之間，初始概率越接近1的經(jīng)紀人每時步的平均得分越多。而圖8b中經(jīng)紀人主要分布在p=0.5與p=0.35之間，初始概率越接近0的經(jīng)紀人每時步的平均得分越多。

由圖8a和圖8b可以發(fā)現(xiàn)一個有趣的現(xiàn)象，正如現(xiàn)實生活中收益正比于風(fēng)險，猶豫不決的經(jīng)紀人(p=0.5左右的經(jīng)紀人)只能獲取較少的財富，采取極端行為往往會帶來更大收益(收益最多的經(jīng)紀人是那些初始概率為p=1或者p=0的經(jīng)紀人)，但他們也承受著更大風(fēng)險，一旦最初的極端選擇使他們處于少數(shù)方，則必須經(jīng)歷更多次的淘汰和重置才能變成猶豫不決者存活下來。

N=1 001，m=10，R=1，d=-4時，通過模擬發(fā)現(xiàn)峰寬與經(jīng)紀人修正錯誤概率時新舊概率的關(guān)聯(lián)程度r的大小有關(guān)。隨著r增大，圖9 中尖峰的高度越低，但寬度越寬，經(jīng)紀人向極端方向分布越平坦，同時由式(2)可知，獲勝方平均經(jīng)紀人數(shù)目也會增多，圖10所示相對偏差也會減小。

圖9　不同r值的概率分布Fig.9　Distribution P(p) of the p-values for different values of r

圖10　不同r值θ/N與m的關(guān)系Fig.10　θ/N as function of m for different values of r

圖11　不同R值的P(p)Fig.11　Distribution of P(p) for different values of R

圖12　不同R值的θ/N與m的關(guān)系Fig.12　θ/N as funtion of m for different values of R

圖11給出了N=1 001，m=10，d=-4，r=0.2時，不同獎勵R下的概率分布P(p)，可以發(fā)現(xiàn)，當R<1時，由于獲勝方在每一輪博弈中的得分變小，劣勢狀態(tài)下經(jīng)紀人為避免淘汰不得不采用更極端的概率去接近p=0或p=1來提升自己的成功率，最終出現(xiàn)尖峰向兩端移動的P(p)，R越小，移動趨勢越明顯。同時由圖12可知，偏離方差θ/N也越小。

3結(jié)束語

多數(shù)者博弈除集市外還廣泛存在于電信領(lǐng)域，最典型的例子為即時通訊軟件、SNS社交網(wǎng)絡(luò)服務(wù)等。多數(shù)者博弈也促成了“美團”、“滴滴”、“去哪兒網(wǎng)”等這些在快餐、打車、旅游行業(yè)搶先占有更多客戶而興起的公司，隨著時代的發(fā)展，多數(shù)者博弈還將有更多的應(yīng)用。

本文研究了多數(shù)方獲勝的基本多數(shù)者博弈模型以及演化多數(shù)者博弈模型，分析了主體行為發(fā)生改變對系統(tǒng)演化狀態(tài)的影響。我們發(fā)現(xiàn)主體行為策略是決定系統(tǒng)演化結(jié)果的關(guān)鍵因素，分析得到的結(jié)論對于解釋現(xiàn)實生活中的一些現(xiàn)象以及控制一些實際系統(tǒng)里的合作程度有一定的參考價值。

參考文獻：

[1]ARTHUR W B. Inductive reasoning and bounded rationality[J]. Am Econ Rev， 1994， 84(2)： 406-411.

[2]CHALLET D， ZHANG Yicheng. Emergence of cooperation and organization in an evolutionary game[J]. Physica A， 1997， 246(3-4)： 407-418.

[3]CHALLET D， ZHANG Yicheng. On the minority game：Analytical numerical studies[J]. Physica A， 1998， 256(3)： 514-532.

[4]ZHANG Yicheng. Toward a theory of marginally efficient markets[J]. Physica A， 1999， 269(1)： 30-44.

[5]楊城，孫世新，曾繁華，等. 非完備策略的少數(shù)者博弈[J]. 廣西師范大學(xué)學(xué)報(自然科學(xué)版)，2006，24(4)： 235-238.

[6]HOLLAND J H. Emergence：From chaos to order[M]. Redwood City, CA： Addison-Wesley， 1998.

[7]JOHNSON N F， HUI P M， JONSON R， et al. Self-organized segregation within an evolving population[J]. Physical Review Letters, 1998, 82(16)： 3360-3363.

[8]FRANTISEK S. Harms and benefits from social imitation[J]. Physica A， 2001， 299(1-2)： 334-343.

[9]全宏俊， 汪秉宏， 羅曉曙. 模仿經(jīng)紀人演化少數(shù)者博弈模型中的合作效應(yīng)[J]. 中國科學(xué)院研究生院學(xué)報， 2003， 20： 101-104.

[10]CHEN Jiale， QUAN Hongjun. Effect of imitation in evolutionary minority game on small-word networks[J]. Physica A， 2009， 388(6)： 945-952.

[11]朱昌勇， 全宏俊. 演化少數(shù)者博弈在小世界網(wǎng)絡(luò)上的信息傳遞效應(yīng)[J]. 廣西師范大學(xué)學(xué)報(自然科學(xué)版)， 2009， 27(4)： 11-14.

[12]紀明潔， 李紅剛. 集市模型：少數(shù)者與多數(shù)者博弈演化分析[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 2012， 9(3)： 82-90.

[13]CAVAGNA A. Irrelevance of memory in the minority game[J]. Phys Rev E， 1999， 59： R3783-R3786.

[14]ZHENG Dafang， WANG Binghong. Statistical properties of the attendance time series in the minority game[J]. Physica A， 2001， 301(1)： 560-566.

(責(zé)任編輯王龍杰)

doi:10.16088/j.issn.1001-6600.2016.02.001

收稿日期：2015-12-15

基金項目：國家自然科學(xué)基金資助項目(11174083)

中圖分類號：O414.2

文獻標志碼：A

文章編號：1001-6600(2016)02-0001-07

Evolutionary Analysis of the Majority Game

SUN Kang，QUAN Hongjun

(Department of Physics， South China University of Technology， Guangzhou Guangdong 510641， China)

Abstract:In order to study the influence of agents’ action strategies on the evolution of social economic system， the basic majority game and the evolutionary majority game in which agents prefer to stay in the majority are put forward on the basis of minority game. We build agent-based models，all the agents in the model are given bounded rationality， and they use their best strategy or modify their strategy probility each round in order to compete for finite resources. When evolving to stable state， phenomena which are unique to human society also occur. In the basic minority game， if agents in the majority are ruled winners, we get the basic majority game，and the game has higher resources utilization when the dimension of the strategy space， m， is smaller. As m gets larger， the utilization becomes lower， approaching that of the random choice game finally. While the utilization of evolutionary majority game isn’t affected by m， so，when m in the game is larger，the evolution is so perferable to improve the utilization of the system. With the same parameters in the game，different random initial conditions may cause different side of distribution of P(p) at p=0.5.The average number of winners each round is also found to be related to the distribution of P(p) at the same time. If we use different boundary conditions to reset agents’ strategy probabilities， we will also get different distribution of P(p). For further analysis of evolutionary majority game’s utilization， we find that the lager the parameter r which means the relation between agents’ old and new p，the flatter distribution of P(p) is，and the utilization also gets larger.At last， if we improve R representing the value of the prize-to-fine ratio， the distribution of P(p) will also be affected，resulted to a lager utilization of the game.

Keywords:action strategies；minority game； basic majority game； evolutionary majority game； bounded rationality

通信聯(lián)系人：全宏俊(1958—)，男，湖南衡陽人，華南理工大學(xué)教授，博士。E-mail:hjquan@scut.edu.cn