博弈論原理模型與教程擴(kuò)展式博弈

1、博弈論：原理、模型與教程第二部分 完全信息動態(tài)博弈第6章 擴(kuò)展式博弈（已精細(xì)訂正！）對博弈問題的規(guī)范性描述是科學(xué)、系統(tǒng)地分析博弈問題的基礎(chǔ)。前面介紹了一種常用的博弈問題描述方式戰(zhàn)略式博弈，雖然這種博弈模型結(jié)構(gòu)簡單，只要給出博弈問題的三個基本構(gòu)成要素（即參與人、參與人的戰(zhàn)略集及參與人的支付），就可完成對博弈問題的建模。但是，由于戰(zhàn)略式博弈假設(shè)每個參與人僅選擇一次行動或行動計劃（戰(zhàn)略），并且參與人同時進(jìn)行選擇，因此從本質(zhì)上來講戰(zhàn)略式博弈是一種靜態(tài)模型，一般適用于描述不需要考慮博弈進(jìn)程的完全信息靜態(tài)博弈問題。雖然戰(zhàn)略式博弈也可以對動態(tài)博弈問題進(jìn)行建模，但是從所得到的模型中只能看到博弈的結(jié)果，而無法直

2、觀地了解到博弈問題的動態(tài)特性。本章將介紹一種新的博弈問題描述方式擴(kuò)展式博弈。從擴(kuò)展式博弈模型中，不僅可以看到博弈的結(jié)果，而且還能直觀地看到博弈的進(jìn)程。在介紹擴(kuò)展式博弈構(gòu)成的基礎(chǔ)上，還將對擴(kuò)展式博弈的戰(zhàn)略和解進(jìn)行討論。6.1 擴(kuò)展式博弈（文字描述、博弈樹描述）所謂擴(kuò)展式博弈（extensive form game），是博弈問題的一種規(guī)范性描述。與戰(zhàn)略式博弈側(cè)重博弈結(jié)果的描述相比，擴(kuò)展式博弈更注重對參與人在博弈過程中所遇到?jīng)Q策問題的序列結(jié)構(gòu)的詳細(xì)分析。一般而言，要了解一個博弈問題的具體進(jìn)程，就必須弄清楚以下兩個問題：（1）每個參與人在什么時候行動（決策、選擇）；· 第六章108（2）每個

3、參與人行動時，他所面臨決策問題的結(jié)構(gòu)，包括參與人行動時可供他選擇的行動方案及所了解的信息（集）。注：行文中頻繁出現(xiàn)的“行動”一詞，有兩義：其一，動詞的“行動”，指選擇、決策。其二，名詞的“行動”，指策略、戰(zhàn)略、謀略、行動方案、方案。上述兩個問題構(gòu)成了參與人在博弈過程中所遇到?jīng)Q策問題的序列結(jié)構(gòu)。對于一個博弈問題，如果能夠說清楚博弈過程中參與人的決策問題的序列結(jié)構(gòu)，那么就意味著知道了博弈問題的具體進(jìn)程。定義6 1 擴(kuò)展式博弈包括以下要素：（1）參與人集合；（2）參與人的行動順序，即每個參與人在何時行動；（3）每個參與人行動時面臨的決策問題，包括參與人行動時可供他選擇的行動方案及他所了解的信息（集）

4、；（4）參與人的支付函數(shù)，即博弈結(jié)束時每個參與人得到的博弈結(jié)果。從上述定義可以看到：如果要用擴(kuò)展式博弈對一個博弈問題進(jìn)行建模（或者描述），那么除了要說明博弈問題所涉及的參與人及每位參與人的支付函數(shù)以外，還必須對博弈過程中參與人所遇到的決策問題的序列結(jié)構(gòu)進(jìn)行詳細(xì)的解釋，說清楚每個參與人在何時行動，以及參與人行動時可供選擇的行動方案和所了解到的信息?！纠?-1】 考察一個“新產(chǎn)品開發(fā)博弈”。試用擴(kuò)展式博弈對兩個企業(yè)都知道市場需求且企業(yè)同時決策的博弈情形，即完全信息靜態(tài)的“新產(chǎn)品開發(fā)博弈”進(jìn)行建模。圖1-1 新產(chǎn)品開發(fā)的投入-產(chǎn)出圖解： 文字描述如下：根據(jù)定義6-1，完全信息靜態(tài)的“新產(chǎn)品開發(fā)博弈”

5、的擴(kuò)展式博弈包括以下要素：（1）參與人是企業(yè)1和企業(yè)2；（2）兩個企業(yè)同時行動，即同時選擇產(chǎn)量；（3）每個企業(yè)行動時有兩種選擇“開發(fā)”和“不開發(fā)”，并且每個企業(yè)行動時不知道對方的選擇 注意，雖然此時每個企業(yè)都不知道對方的選擇，但用擴(kuò)展式博弈進(jìn)行建模時仍然假設(shè)參與人都同時看到了圖1-1所示的投入-產(chǎn)出圖，即圖1-1對兩個企業(yè)來說為共同知識。；（4）兩個企業(yè)的支付如圖1-1所示。圖1-1 新產(chǎn)品開發(fā)的投入-產(chǎn)出圖【例6-2】 繼續(xù)考察“新產(chǎn)品開發(fā)博弈”。試用擴(kuò)展式博弈對兩個企業(yè)都知道市場需求且企業(yè)1先決策，企業(yè)2觀測到企業(yè)1的選擇后再進(jìn)行選擇的博弈情形，即完全信息動態(tài)的“新產(chǎn)品開發(fā)博弈”進(jìn)行建模。

6、解： 文字描述如下：根據(jù)定義6-1，完全信息動態(tài)的“新產(chǎn)品開發(fā)博弈”的擴(kuò)展式博弈包括以下要素：（1）參與人是企業(yè)1和企業(yè)2；（2）企業(yè)1先行動，企業(yè)2后行動；（3）企業(yè)1行動時有兩種選擇“開發(fā)”和“不開發(fā)”，企業(yè)1行動時不知道企業(yè)2的行動；企業(yè)2行動時有兩種選擇“開發(fā)”和“不開發(fā)”，但企業(yè)2行動時已經(jīng)知道企業(yè)1的行動；（4）兩個企業(yè)的支付仍然有如圖1-1所示。上述兩個例子中，用文字描述的方法給出了博弈問題的擴(kuò)展式描述。對于一些簡單的博弈問題，這種文字表述的方法也許是簡單可行的。但可以想象，如果遇到的是更為復(fù)雜的博弈問題，如參與人人數(shù)大于，每個參與人可以多次行動且每次行動時可供選擇的行動方案不同

7、等，文字描述所給出的模型就會顯得繁冗拖沓，極不直觀，因此需要尋找一種簡便易行的擴(kuò)展式博弈的描述方式。下面就以“新產(chǎn)品開發(fā)博弈”為例，介紹一種不僅簡單方便，而且十分直觀的擴(kuò)展式博弈的描述方式博弈樹。所謂博弈樹，就是由結(jié)和有向枝構(gòu)成的“有向樹”。圖6-1給出的是當(dāng)市場需求為大時，完全信息動態(tài)的“新產(chǎn)品開發(fā)博弈”的博弈樹。在圖6-1所示的博弈樹中，最上端的一個點(diǎn)(用空心圓表示)表示博弈的開始，將“企業(yè)1”標(biāo)示在點(diǎn)上，表示博弈開始于企業(yè)1的選擇。企業(yè)1的選擇有“開發(fā)”和“不開發(fā)”，分別用標(biāo)有“開發(fā)”和“不開發(fā)”的有向枝表示。若企業(yè)1選擇“開發(fā)”，則博弈從點(diǎn)達(dá)到（用實心圓表示）；若企業(yè)1選擇“不開發(fā)”，

8、則博弈從點(diǎn)達(dá)到點(diǎn)（用實心圓表示）。點(diǎn)（或）上標(biāo)有“企業(yè)2”，表示企業(yè)2在博弈到達(dá)點(diǎn)（或）時，即企業(yè)1選擇“開發(fā)”（或“不開發(fā)”）后，再進(jìn)行選擇；企業(yè)2的行動也有“開發(fā)”和“不開發(fā)”，同樣分別用標(biāo)有“開發(fā)”和“不開發(fā)”的有向枝表示。若企業(yè)2選擇“開發(fā)”，則博弈從點(diǎn)（或）達(dá)到點(diǎn)（或）（都用實心圓表示）；若企業(yè)2選擇“不開發(fā)”，則博弈從點(diǎn)（或）達(dá)到點(diǎn)（或）（都用實心圓表示）。由于企業(yè)2選擇后博弈結(jié)束，因此點(diǎn)、和都表示博弈的結(jié)束。在點(diǎn)、和旁標(biāo)有支付向量，表示博弈達(dá)到該點(diǎn)時企業(yè)的所得。其中，支付向量中的第一個數(shù)字表示企業(yè)1的所得，第二個數(shù)字表示企業(yè)2的所得 一般情形下，支付向量中數(shù)字的順序與博弈樹中參與

9、人的行動順序相對應(yīng)。 開發(fā) 不開發(fā) 企業(yè)2 企業(yè)2 開發(fā) 不開發(fā) 開發(fā) 不開發(fā) (300,300) (800,0) (0, 800) (0,0) 圖6-1 博弈樹企業(yè)1圖6-1中，點(diǎn)、和稱為博弈樹的結(jié)（node），其中標(biāo)有參與人（即企業(yè)）的結(jié)、和稱為決策結(jié)（decision node）,表示參與人在此選擇行動；標(biāo)有支付向量的結(jié)、和表示博弈結(jié)束，稱為終點(diǎn)結(jié)（terminal node）。在決策結(jié)中，決策結(jié)表示博弈的開始，亦稱為博弈樹的初始結(jié)或根（root）。結(jié)與結(jié)的連線稱為博弈樹的枝（branch），表示博弈從枝的一個結(jié)達(dá)到另一個結(jié)參與人需要選擇的行動。例如，博弈從決策結(jié)達(dá)到，需要企業(yè)1選擇行動

10、“開發(fā)”，所以在連接和的枝上標(biāo)有行動“開發(fā)”。在博弈樹中，枝是有向的，表示博弈只能從枝的一個結(jié)達(dá)到另一個結(jié)。例如，在連接和的枝上，標(biāo)有行動“不開發(fā)”，表示當(dāng)企業(yè)1選擇“不開發(fā)”時，博弈從達(dá)到，因此連接到的枝的方向是從指向。通過以上介紹，再考察圖6-1中的博弈樹，可以得到這樣的信息：（1）博弈中的參與人是企業(yè)1和企業(yè)2；（2）博弈中企業(yè)1先選擇，企業(yè)2后選擇；（3）企業(yè)1選擇時有行動“開發(fā)”和“不開發(fā)”，企業(yè)2選擇的行動有“開發(fā)”和“不開發(fā)”；（4）博弈中企業(yè)的支付。也就是說，除了“企業(yè)2行動時是否觀測到企業(yè)1的選擇”這一點(diǎn)暫時無法從圖6-1中知道以外，完全信息動態(tài)的“新產(chǎn)品開發(fā)博弈”的擴(kuò)展式描

11、述所需要的信息（或要素）都可以從圖6-1中得到。如果還能夠直接從博弈樹中知道“企業(yè)2行動時是否觀測到企業(yè)1的選擇”，那么給出博弈樹，就意味著給出了完全信息動態(tài)的“新產(chǎn)品開發(fā)博弈”的擴(kuò)展式描述。下面探討如何在博弈樹中，將“企業(yè)2行動時是否觀測到企業(yè)1的選擇”這一信息表示出來。在完全信息動態(tài)的“新產(chǎn)品開發(fā)博弈”中，企業(yè)2決策時企業(yè)1已經(jīng)做出選擇，此時企業(yè)2面臨的決策情形無非只有以下兩種：第一種：企業(yè)2知道企業(yè)1的選擇；第二種：企業(yè)2不知道企業(yè)1的選擇。對于第一種情形，企業(yè)2知道企業(yè)1的選擇，即知道企業(yè)1選擇“開發(fā)”還是“不開發(fā)”，因此企業(yè)2知道博弈是從到了還是從到了。這就意味著當(dāng)輪到企業(yè)2決策時，

12、他知道自己是在點(diǎn)上還是在點(diǎn)上。對于第二種情形，企業(yè)2不知道企業(yè)1的選擇，即不知道博弈是從到了還是從到了。因此，當(dāng)輪到企業(yè)2決策時，他不知道自己是在點(diǎn)上還是在點(diǎn)上。所以，“企業(yè)2行動時是否觀測到企業(yè)1的選擇”這一問題，實際上就等價于“企業(yè)2行動時是否知道自己是在博弈樹中的點(diǎn)上還是在點(diǎn)上”。為了將“企業(yè)2行動時是否知道自己是在博弈樹中的點(diǎn)上還是在點(diǎn)上”這一點(diǎn)說清楚，需要引入“信息集”（information set）的概念。在博弈樹中，參與人的一個信息集（用表示）是參與人決策結(jié)的一個集合，它滿足以下條件：（1）中的每個決策結(jié)都是參與人的決策結(jié)；（2）當(dāng)博弈到達(dá)信息集（即博弈到達(dá)中某個決策結(jié)）時，參

13、與人知道自己是在信息集中的決策結(jié)上，但不知道自己究竟在中哪個決策結(jié)上。因此，參與人的信息集可以用來描述當(dāng)輪到參與人行動時他所了解到的信息，即他知道什么（知道自己位于哪一個信息集上）、不知道什么（不知道自己位于信息集中哪一個決策結(jié)上）。例如，在“新產(chǎn)品開發(fā)博弈”中，假設(shè)企業(yè)1先行動，企業(yè)2后行動，但企業(yè)2行動時不知道企業(yè)1的行動，那么在如圖6-1所示的博弈中當(dāng)企業(yè)2行動時就只知道博弈要么到達(dá)點(diǎn)，要么到達(dá)點(diǎn)，但具體在哪一點(diǎn)上，企業(yè)2不清楚。也就是說，企業(yè)2只知道自己位于決策結(jié)集合上，但不知道位于中哪一個決策結(jié)上。在這種情況下，就是企業(yè)2的一個信息集。如果假設(shè)企業(yè)2行動時知道企業(yè)1的行動，那么在如圖

14、6-1所示的博弈中，當(dāng)企業(yè)2行動時就知道博弈是到達(dá)了點(diǎn)，還是到達(dá)了點(diǎn)。此時，企業(yè)2的決策結(jié)集和都是企業(yè)2 的信息集 注意，這是一種信息退化了的情況，即信息集中只含有一個決策結(jié)（亦稱單結(jié)信息集）。此時，雖然信息集的定義要求參與人不知道自己在信息集哪一個決策結(jié)上，但由于只有一個決策結(jié)，實際上也意味著參與人知道自己在哪一個決策結(jié)上。設(shè)為一決策結(jié)集合，用表示參與人的由決策結(jié)集構(gòu)成的一個信息集。例如，表示企業(yè)2的由決策結(jié)集構(gòu)成的信息集，和分別表示企業(yè)2的由決結(jié)集和構(gòu)成的信息集。為了更好地理解信息集這個概念，考慮如圖62所表示的博弈情形中參與人3的信息集 在圖62中，省略了參與人的支付，但這樣并不影響對問

15、題的分析。（順便考慮參與人2、參與人3的信息集）。由于參與人3選擇時，參與人1和參與人2都已經(jīng)做出選擇，因此參與人3選擇時可能面臨的決策情形就有以下4種：（1）既知道參與人1的選擇，也知道參與人2的選擇；（2）知道參與人1的選擇，但不知道參與人2的選擇；（3）知道參與人2的選擇，但不知道參與人1的選擇；（4）既不知道參與人1的選擇，也知道參與人2的選擇。L33 12R圖6-2 博弈樹：知道1的選擇；不知道2的選擇2 下面對上述4種情形分別進(jìn)行考察：首先考察第二種情形，即參與人3知道參與人1的選擇，但不知道參與人2的選擇。參與人3知道參與人1的選擇，就意味著當(dāng)輪到他選擇時，他知道博弈進(jìn)入了博弈的

16、左邊（如果參與人1選擇）還是右邊（如果參與人1選擇）；但由于參與人3不知道參與人2的選擇，因此當(dāng)輪到他選擇時，他不知道自己是在上還是在上，或者上還是上。但是，參與人3知道自己要么就在或者上，要么就在或者上，所以參與人3的決策結(jié)集和都為參與人3的信息集。在博弈樹中，用虛線將屬于同一信息集的決策結(jié)連起來，表示它們屬于同一信息集。例如，62中，用虛線將點(diǎn)和連起來，表示它們都屬于信息集，用虛線將點(diǎn)和連起來，表示它們都屬于與信息集 。其次考察第三種情形，即參與人3知道參與人2的選擇，但不知道參與人1的選擇。雖然參與人3知道參與人選擇了 還是 ，但由于他不知道參與人1的選擇，因此當(dāng)參與人2選擇 時，參與人

17、3知道自己是在或者上，但究竟在哪一點(diǎn)上參與人3并不清楚，所以決策集合是參與人3的一個信息集。當(dāng)參與人2選擇 時，參與人3知道自己是在或者上，但究竟在哪一個點(diǎn)上并不清楚，所以決策結(jié)集合是參與人3的另一個信息集。在圖中63中，用虛線將點(diǎn)和連起來，表示它們都屬于信息集 ，用虛線將點(diǎn)和連起來，表示它們都屬于信息集。 1L22R圖6-3 博弈樹：知道2的選擇；不知道1的選擇33考察第四種情形，即參與人3既不知道參與人1的選擇也不知道參與人2的選擇。由于參與人1和參與人2的選擇參與人3都不知道，因此當(dāng)輪到參與人3行動時，他只知道自己位于點(diǎn)、和四點(diǎn)中的某一點(diǎn)上，但究竟在哪一點(diǎn)上參與人3并不清楚，所以決策結(jié)集

18、合是參與人3的一個信息集。在圖64中，用虛線將點(diǎn)、和連起來，表示它們都屬于信息集。2R3331L2圖6-4 博弈樹：既不知道1的選擇；也不知道2的選擇最后考察第一種情形，即參與人3既知道參與人1的選擇也知道參與人2的選擇。由于參與人3既知道參與人1的選擇，又知道參與人2的選擇，因此當(dāng)輪到參與人3行動時，他知道自己在點(diǎn)、和四點(diǎn)中的哪一點(diǎn)上，所以決策集合、和都是參與人3的信息集（參見圖65）。33331L22R圖6-5 博弈樹：既知道1的選擇；也知道2的選擇從上面分析可以看到：如果有了信息集這個概念，同時又在博弈中用特定的方式將信息標(biāo)示出來 即將屬于同一信息集問題結(jié)用虛線連起來這種方式來標(biāo)示博弈中

19、的信息集。，那么給出一個博弈問題的博弈樹時，實際上就意味著給出了這個博弈問題的擴(kuò)展事描述。例如，如果讀者現(xiàn)在看到的是如圖6 2(或者圖63、圖64、圖65)所示的博弈樹，那么就應(yīng)該從圖62中得到一個博弈問題的擴(kuò)展事描述，這種描述包含了擴(kuò)展事博弈的所有要素。 當(dāng)然，當(dāng)采用“將參與人屬于同一信息集的決策結(jié)用虛線連起來”的方式表示參與人的信息集時，在圖6圖65隱含了參與人2行動時已經(jīng)觀察到參與人1的行動，因為在圖6圖65中，參與人2的信息集都是單結(jié)信息集（即值包含一個決策結(jié)的信息集） 在博弈考試時，最先行動的參與人知道自己在博弈樹起始結(jié)進(jìn)行選擇，所以行動的參與人的信息集都是單結(jié)信息集。【例63】 考察“新產(chǎn)品開發(fā)博弈”。試用博弈樹描述“兩個企業(yè)都知道市場要求，且企業(yè)1先決策，企業(yè)2觀察到企業(yè)1的選擇后在進(jìn)行選擇”的博弈情形。 開發(fā) 不開發(fā) 企業(yè)2 企業(yè)2 開發(fā) 不開發(fā) 開發(fā) 不開發(fā) (300,300) (800,0) (0, 800) (0,0) 圖6-1 博弈樹企業(yè)1圖61實際上已經(jīng)給出了當(dāng)市場需求為大時，“新產(chǎn)品開發(fā)博弈”的博弈樹。圖66給出的是當(dāng)市