博弈樹

出自 MBA智库百科(https://wiki.mbalib.com/)

博弈樹（game tree)

　　博弈樹是指由於動態博弈參與者的行動有先後次序，因此可以依次將參與者的行動展開成一個樹狀圖形。^[1]

　　博弈樹是擴展型的一種形象化表述。它能給出有限博弈的幾乎所有信息。其基本構建材料包括結、枝和信息集。結包括決策結和終點結兩類；決策結是參與人採取行動的時點，終點結是博弈行動路徑的終點。枝是從一個決策結到它的直接後續結的連線(有時用箭頭表述)，每一個枝代表參與人的一個行動選擇。博弈樹上的所有決策結分割成不同的信息集。每一個信息集是決策集集合的一個子集，該子集包括所有滿足下列條件的決策結：(1)每一個決策結都是同一參與人的決策結；(2)該參與人知道博弈進入該集合的某個決策結，但不知道自己究竟處於哪一個決策結。^[2]

　　(1) 博弈的初始格局是初始節點。

　　(2) 在博弈樹中，"或"節點和"與"節點是逐層交替出現的。自己一方擴展的節點之間是"或"關係，對方擴展的節點之間是"與"關係。雙方輪流地擴展節點。

　　(3) 所有自己一方獲勝的終局都是本原問題，相應的節點是可解節點；所有使對方獲勝的終局都認為是不可解節點。

　　(1)軟體博弈

　　考慮下麵的策略局勢：電腦軟體商巨集軟公司正決定利用什麼樣的營銷策略推銷其新近開發的電腦游戲軟體。在經過許多研究後，該公司把它的選擇減少為兩個：(1)A計劃；(2)B計劃。巨集軟公司知道電腦游戲軟體的總銷售量不會受到選擇的廣告計劃的影響，但這些銷售量的時序會非常不同。只要巨集軟公司是游戲的唯一提供者，使用麽計劃在第一年的銷售量非常高，這是麽計劃“閃電戰”的結果，但在第二年銷售量非常小，因為市場接近飽和。B計劃第一年的銷售量相對小，但第二年的銷售量很大，因為早先的用戶告訴他們的朋友這個游戲是如何的好。在兩個廣告計劃中，第二年後沒有進一步的銷售量。

　　因為市場完全飽和。兩種計划下每年獲得的凈利潤如表1所示：

　　以表1為基礎，顯然巨集軟公司的最優決策是利用比較廉價的B計劃，並依賴於博弈在第二年銷售量的提高而產生的聲譽。但是這一結論忽略了與合法複製巨集軟游戲軟體的潛在競爭者的競爭。電腦游戲軟體的合法複製是模仿第一個游戲軟體的第二個游戲軟體，但它的複製完全不同處在於複製的所有者不能受到侵犯版權的控告。然而，對於巨集軟公司而言，中軟公司擁有生產巨集軟游戲的法定複製的技術能力，在開始博弈的那一年成本為300000美元。如果中軟公司生產複製品，則兩個企業會在第二年分割市場。這一假設不考慮其他策略問題，如兩個企業在第二年進行價格競爭。表2和表3列出了巨集軟和中軟公司在中軟公司進入市場時的利潤。顯然B計劃依然是最優的。

　　由於兩個公司的相互依賴性，巨集軟公司和中軟公司在玩一個博弈。為了分析這個博弈，我們需要知道局中人可利用的策略和他們彼此採用這些策略時的得益。構造可能的策略列表的第一步是列出兩個局中人可用的行動。巨集軟公司有兩個行動供選擇：(1)採用A計劃；(2)採用B計劃。中軟公司也有兩個行動供選擇：(1)複製游戲軟體進入市場；(2)不複製游戲軟體不進入市場。我們稱這兩個行動為進入和不進入。如果這是一個靜態博弈，每個局中人的策略集合等價於他們的行動集合。但這不是靜態博弈。在這個博弈中，巨集軟公司先行動，中軟公司在做出其進入決策前知道巨集軟公司的行動。描述這個博弈進行的時序的最簡單方法是說巨集軟公司是先行動者，中軟公司是後行動者。因為這一博弈順序，中軟公司可把其行動建立在巨集軟公司的行動之上。因此中軟公司的一個策略，是要說明如果巨集軟公司採用A計劃中軟公司將採取什麼行動；如果巨集軟公司採取B計劃，中軟公司將採取什麼行動。這兩個不必相同。

　　(2)博弈樹

　　為了決定每個企業的策略集合，我們不僅要仔細闡明局中人的行動，而且要闡明這些行動的順序和他們在做出決策時已有的信息。組織這一信息的強有力的方法是博弈樹。博弈樹是由結和枝組成的圖。博弈樹中每個結點代表局中人之一的決策點，該局中人屬於在該點行動的局中人。決策結用方框表示，框內是在該結點行動的局中人的名字。一個枝代表局中人一個可能的行動。每個枝連接的兩個結點有一個方向。該方向用箭頭表示。如果一個枝從結點屬於局中人A的結點N_1到屬於局中人B的結點N_2，則局中人A在局中人B前行動，結N₁，在終點結N₂前。在本書中，博弈樹將總是從頂到底或從左到右進行的。

　　圖1是軟體博弈的博弈樹。該博弈從圖的最左邊開始，其中巨集軟選擇為其新產品的廣告宣傳。兩個枝從左向右，每個枝代表選擇的廣告計劃。代表的行動被列入枝的上邊。每個枝點表示中軟公司的一個決策結，因為這個企業在其知道巨集軟公司已經採用的廣告類型後做出其進入決策。從決策結向代表中軟公司可能選擇的行動的兩個枝延伸。這四個箭頭的末端是圓點，叫做終點結。在終點結，博弈結束。終點結的右邊是兩個數字。第一個數字是先行動者(巨集軟公司)的得益，第二個數字是後行動者(中軟公司)的得益。博弈樹與所有終點結的得益一起，構成博弈的擴展形式。

　　為了避免模棱兩可，博弈樹必須遵循四個法則。

　　博弈樹法則1 每個結點前至多有一個其他結點直接相聯繫。

　　圖2左邊是違背法則1的博弈樹。局中人B有兩個決策結，從他們的枝到達相同的終點結。如果局中人A的行動對得益沒有影響，則該局中人的決策結會因前後不一致而被剔除。而且，如果局中人B的行動對得益有影響，則在博弈樹上需要加上兩個終點結，對應著A的每個行動。

　　當法則1被滿足時，講一個決策結“跟在另一個決策結後”才有意義。如果從A開始，局中人可能做出後續的行動，使得博弈到結點B，結點B是結點A的後續結。正式地，結點B是結點彳的後續結，當且僅當存在某些後續結N_l,N₂，…，N_K，使得A=N₁，B=N_K，且每個結點直接位於後面的另一個結點之前。這一結點順序稱之為從A到B的路徑。法則l意味著在任意兩個結點之間至多有一條路徑。我們將說結點A是結點B的前列結，當且僅當結點B是A的後續結。終點結沒有後續結，初始結沒有前列結。稱沒有終點結的結點為決策結。

　　圖3左邊是滿足博弈樹法則1的一個博弈樹，但其中有一個“環”：如果局中人A選擇“下”，則局中人B開始行動；而且如果局中人B選擇“左”，則局中人A開始行動。因此，誰先行動呢?為了剔除此種任意性，我們將避免有環狀的決策樹。圖3右邊的博弈樹是正確的：局中人A行動兩次，一次在局中人B之前，一次在局中人B之後。

　　博弈樹法則2 在一個博弈樹中不能有路徑把一個決策結與其自身相聯結。

　　圖4是滿足博弈樹法則1和2的博弈樹，但沒有初始結。然而，“無頭”的決策結有可能產生某些策略組合後果的任意性。由於這個原因，我們需要決策樹滿足法則3。

　　博弈樹法則3 每個結是一個唯一初始結的後續結

　　博弈樹法則1、2和3意味著每個結點在其前列結中只有一個初始結。但是，整個博弈樹可能有一個以上的初始結。不過，不管這在何時發生，結點都可根據他們在哪個初始結之後被分成不連續的集合。我們要求這些不連續的結點子集(和聯結他們的枝)的每個可被看成是滿足博弈樹法則1、2、3的分離的博弈樹。而且這每一個“子樹”，根據構造只有一個初始結(如圖5所示)。在圖5中，博弈樹有一個以上初始結的任何博弈都可以分成彼此獨立的博弈，每個獨立的博弈只有一個初始結。我們稱這個唯一的初始結是博弈樹的根。因此，不失一般性，最後要求滿足博弈樹法則4。

　　博弈樹法則4 每個博弈樹只有一個初始結

　　(3)策略

　　策略是局中人進行博弈的詳細計劃集合。局中人的一個策略必須說明在該局中人的每一個決策結所採取的行動。因為巨集軟公司只有一個決策結，所以巨集軟公司的策略就只包括其選擇兩個行動之一。中軟公司有兩個決策結。中軟公司的一個策略是基於巨集軟公司先前的廣告選擇，在進入或不進入市場間決策。中軟公司的一個可能的策略是：如果巨集軟公司採用A計劃，中軟公司就進入，如果巨集軟公司採用B計劃，中軟公司就不進入。我們把這一策略寫成：(進入，不進入)。第一部分即進入，描述瞭如果巨集軟公司採用A計劃，中軟公司將採取的策略；第二部分不進入描述的是，如果巨集軟公司採用的是B計劃，中軟公司所採取的策略。這是四個可能的策略之一。其他三個策略，請讀者寫出。策略和行動容易混淆。關鍵是要理解策略不同於行動。策略所刻畫的是在所有可能的事件下的計劃。不同的策略可產生相同的行動順序，例如，中軟公司和巨集軟公司博弈中的下麵兩個策略組合：{B計劃，(不進入，進入))，{A計劃，(進入，不進入))。

　　(4)信息

　　如果一個局中人知道在他開始行動時博弈進行到哪裡，則就說該局中人有完美信息。如果博弈的每個局中人都有完美信息，該博弈就是完美信息動態博弈。多數博弈，如下象棋或者下跳棋，是完美信息博弈。軟體博弈1是一個完美信息博弈。此外，一個局中人在不知道另一個局中人先前的行動時必須行動，此局中人就有不完美信息。如果至少有一個局中人有不完美信息，該搏弈就是不完美信息博弈。靜態博弈是不完美信息博弈，如多數紙牌游戲。

　　(5)結果和得益

　　軟體博弈中巨集軟公司和中軟公司的得益如表4所示。巨集軟公司的行動和策略是一致的，而中軟公司的行動與策略不一致。表4列出了中軟公司的行動而不是其策略。表4告訴我們，如果巨集軟公司選擇爿計劃，中軟公司就選擇進入，則巨集軟公司將獲得380000美元的利潤，中軟公司將承受250000美元的虧損。