博弈論原理模型與教程第06章擴(kuò)展式博弈第01節(jié)

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）每個參與人在什么時候行動（決策、選擇） ；（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)參與人集合1,2,., n；(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)行建模。企業(yè)1開發(fā)(a，：投入2000元資金不開發(fā)(b)需求大需求小企業(yè)2不開發(fā)，獲

5、利潤800萬元企業(yè)2開發(fā)，獲利潤300元企業(yè)2不開發(fā)，獲利潤200萬元企業(yè)2開發(fā)，賠400萬元:不投入資金，利潤 為0。圖1-1 新產(chǎn)品開發(fā)的投入-產(chǎn)出圖解：文字描述如下：根據(jù)定義6-1 ,完全信息靜態(tài)的“新產(chǎn)品開發(fā)博弈”的擴(kuò)展式博弈包括以下要素：(1 )參與人是企業(yè)1和企業(yè)2 ;(2)兩個企業(yè)同時行動，即同時選擇產(chǎn)量；(3)每個企業(yè)行動時有兩種選擇一“開發(fā)”和“不開發(fā)”，并且每個企業(yè)行動時不知道對方的選擇1(4)兩個企業(yè)的支付如圖 1-1所示。1注意，雖然此時每個企業(yè)都不知道對方的選擇,但用擴(kuò)展式博弈進(jìn)行建模時仍然假設(shè)參與人都同時看到了圖1-1所示的投入-產(chǎn)出圖，即圖1-1對兩個企業(yè)來說為共

6、同知識。需求大企業(yè)1開發(fā)（a）:投入2000元資金企業(yè)2不開發(fā)，獲利潤800萬元企業(yè)2開發(fā)，獲利潤300元不開發(fā)（b）. 企業(yè)2不開發(fā)，狄利潤 200萬兀 需求小企業(yè)2開發(fā)，賠400萬兀:不投入資金，利潤 為0。圖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)行建模。解：文字描述如下：根據(jù)定義6-1 ,完全信息動態(tài)的“新產(chǎn)品開發(fā)博弈”的擴(kuò)展式博弈包括以下要素：（1 ）參與人是企業(yè)1和企業(yè)2 ;（2）企業(yè)1先行動，企業(yè)2后行動；（3

7、）企業(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ù)大于2 ,每個參與人可以多次行動且每次行動時可供選擇的行動方案不同等，文字描述所給出的模型就會顯得繁冗拖沓，極不直觀，因此需要尋找一種簡便易行的擴(kuò)展式博弈的描述方式。下面就以“新產(chǎn)品開發(fā)博弈”為例，介紹一種不僅簡單

8、方便，而且十分直觀的擴(kuò)展式博弈的描述方式博弈樹。所謂博弈樹，就是由結(jié)和有向枝構(gòu)成的“有向樹”。圖6-1給出的是當(dāng)市場需求為大時，完全信息動態(tài)的“新產(chǎn)品開發(fā)博弈”的博弈樹。在圖6-1所示的博弈樹中，最上端的一個點(diǎn)X1（用空心圓表示）表示博弈的開始，將“企業(yè)1”標(biāo)示在點(diǎn)X1上，表示博弈開始于企業(yè) 1的選擇。企業(yè)1的選擇有“開發(fā)”和“不開發(fā)”，分別用標(biāo)有“開發(fā)”和“不開發(fā)”的有向枝表示。若企業(yè)1選擇“開發(fā)”，則博弈從點(diǎn)X1達(dá)到X2 （用實心圓表示）；若企業(yè)1選 擇“不開發(fā)”，則博弈從點(diǎn)X1達(dá)到點(diǎn)X3 （用實心圓表示）。點(diǎn)X2 （或X3）上標(biāo)有“企業(yè) 2”，表示企業(yè)2 在博弈到達(dá)點(diǎn)x2 （或X3）時，

9、即企業(yè)1選擇“開發(fā)”（或“不開發(fā)”）后，再進(jìn)行選擇；企業(yè) 2的行動也有“開發(fā)”和“不開發(fā)”，同樣分別用標(biāo)有“開發(fā)”和“不開發(fā)”的有向枝表示。若企業(yè)2選擇“開發(fā)”，則博弈從點(diǎn)x2 （或X3）達(dá)到點(diǎn)X4 （或X6）（都用實心圓表示）；若企業(yè)2選擇“不開發(fā)”，則博弈從點(diǎn)X2（或X3）達(dá)到點(diǎn)X5 （或X7）（都用實心圓表示）。由于企業(yè)2選擇后博弈結(jié)束，因此點(diǎn)X4、X5、*6和X7都表示博弈的結(jié)束。在點(diǎn) x4、X5、X6和*7旁標(biāo)有支付向量，表示博弈達(dá)到該點(diǎn)時企業(yè)的所得。其中，支付向量中的第一個數(shù)字表示企業(yè)1的所得，第二個數(shù)字表示企業(yè) 2的所得1。(300,300)(800,0)(0, 800)(0,0

10、)圖6-1博弈樹圖6-1中，點(diǎn)X1、X2、X3、X4、X5、*6和*7稱為博弈樹的結(jié)（node）,其中標(biāo)有參與人（即企業(yè)）的結(jié)X1、*2和*3稱為決策結(jié)（decision node）,表示參與人在此選擇行動；標(biāo)有支付向量的結(jié)X4、X5、*6和X7表示博弈結(jié)束，稱為 終點(diǎn)結(jié)（terminal node ）。在決策結(jié)中，決策結(jié) X1表示博弈的開始， 亦稱為博弈樹的初始結(jié) 或根（root ）。結(jié)與結(jié)的連線稱為博弈樹的枝（branch）,表示博弈從枝的一個結(jié)達(dá)到另一個結(jié)參與人需要選擇的行動。例如，博弈從決策結(jié)x1達(dá)到X2 ,需要企業(yè)1選擇行動“開發(fā)”，所以在連接Xi和X2的枝上標(biāo)有行動“開發(fā)”。在博弈

11、樹中，枝是有向的，表示博弈只能從枝的一個結(jié)達(dá)到另一個結(jié)。例如，在連接x1和X3的枝上，標(biāo)有行動“不開發(fā)”，表示當(dāng)企業(yè)1選擇“不開發(fā)”時，博弈從 X1達(dá)到X3 ,因此連接X1到X3的枝的方向是從 X1指向X3 o1 一般情形下，支付向量中數(shù)字的順序與博弈樹中參與人的行動順序相對應(yīng)。通過以上介紹，再考察圖 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)暫時無

12、法從圖 6-1中知道以外，完全信息動態(tài)的“新產(chǎn)品開發(fā)博弈”的擴(kuò)展式描述所需要的信息(或要素)都可以從圖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ā)”還是

13、“不開發(fā)”，因此企業(yè)2 知道博弈是從 小到了 X2還是從X1到了 X3。這就意味著當(dāng)輪到企業(yè) 2決策時，他知道自己是在點(diǎn) X2上還 是在點(diǎn)X3上。對于第二種情形，企業(yè) 2不知道企業(yè)1的選擇，即不知道博弈是從 X1到了 X2還是從X1到 了 X3o因此，當(dāng)輪到企業(yè) 2決策時，他不知道自己是在點(diǎn) X2上還是在點(diǎn)X3上。所以，“企業(yè)2行動時是 否觀測到企業(yè)1的選擇”這一問題，實際上就等價于“企業(yè)2行動時是否知道自己是在博弈樹中的點(diǎn) x2± 還是在點(diǎn)X3上"。為了將“企業(yè)2行動時是否知道自己是在博弈樹中的點(diǎn)X2上還是在點(diǎn)X3上”這一點(diǎn)說清楚，需要引入“信息集"(infor

14、mation set )的概念。在博弈樹中，參與人i的一個信息集(用Ii表示)是參與人i決策結(jié)的一個集合，它 滿足以下條件：(D I i中的每個決策結(jié)都是參與人 i的決策結(jié)；(2)當(dāng)博弈到達(dá)信息集Ii (即博弈到達(dá)Ii中某個決策結(jié))時，參與人i知道自己是在信息集Ii中的決策結(jié)上，但不知道自己究竟在 Ii中哪個決策結(jié)上。因此，參與人i的信息集Ij可以用來描述當(dāng)輪到參與人 i行動時他所了解到的信息，即他知道什么(知道自己位于哪一個信息集上)、不知道什么(不知道自己位于信息集中哪一個決策結(jié)上)。例如，在“新產(chǎn)品開發(fā)博弈”中，假設(shè)企業(yè)1先行動，企業(yè)2后行動，但企業(yè)2行動時不知道企業(yè)1的行動，那么在如圖

15、6-1所示的博弈中當(dāng)企業(yè) 2行動時就只知道博弈要么到達(dá)點(diǎn) x2,要么到達(dá)點(diǎn)x3 ,但 具體在哪一點(diǎn)上，企業(yè) 2不清楚。也就是說，企業(yè) 2只知道自己位于決策結(jié)集合 x2,X3上，但不知道位 于 X2,必中哪一個決策結(jié)上。在這種情況下， X2 , X3就是企業(yè)2的一個信息集。如果假設(shè)企業(yè)2行動時知道企業(yè)1的行動，那么在如圖 6-1所示的博弈中，當(dāng)企業(yè) 2行動時就知道博弈是到達(dá)了點(diǎn) x2 ,還是 到達(dá)了點(diǎn)x3o此時，企業(yè)2的決策結(jié)集*2和*3都是企業(yè)2的信息集1。設(shè)X為一決策結(jié)集合，用L(X)表示參與人i的由決 策結(jié)集 X構(gòu)成的一個 信息集。例如，I2( x2,x3 )表示企業(yè)2的由決策結(jié)集 x2,

16、x3構(gòu)成的信息集，I2( x2 )和I 2( x2, x3 )分別表示企業(yè)2 的由決結(jié)集 x2和x3構(gòu)成的信息集。為了更好地理解信息集這個概念 ，考慮如圖6-2所表示的博弈情形中參與人 3的信息集2(順便考慮 參與人2、參與人3的信息集)。由于參與人3選擇時，參與人1和參與人2都已經(jīng)做出選擇，因此參與人 3選擇時可能面臨的決策情 形就有以下4種：(1)既知道參與人1的選擇，也知道參與人 2的選擇；(2)知道參與人1的選擇，但不知道參與人 2的選擇；(3)知道參與人2的選擇，但不知道參與人 1的選擇；(4)既不知道參與人1的選擇，也知道參與人 2的選擇。單結(jié)信息集)。但由于只有一個1注意，這是一

17、種信息退化了的情況，即信息集中只含有一個決策結(jié)(亦稱 此時，雖然信息集的定義要求參與人不知道自己在信息集哪一個決策結(jié)上， 決策結(jié)，實際上也意味著參與人知道自己在哪一個決策結(jié)上。2在圖6 2中，省略了參與人的支付，但這樣并不影響對問題的分析下面對上述4種情形分別進(jìn)行考察：首先考察第二種情形， 即參與人3知道參與人1的選擇，但不知道參與人 2的選擇。參與人3知道參與人1的選擇，就意味著當(dāng)輪到他選擇時，他知道博弈進(jìn)入了博弈的左邊（如果參與人1選擇L ）還是右邊（如果參與人 1選擇R ）；但由于參與人3不知道參與人2的選擇，因此當(dāng)輪到他選擇時，他不知道自己是在 *4上還是在X5上，或者X6上還是X7上

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

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

20、點(diǎn)上，但究竟在哪一點(diǎn)上參與人3并不清楚，所以決策結(jié)集合X4,X5,X6,X7是參與人3的一個信息集。在圖64中，用虛線將點(diǎn)X4、X5、*6和*7連起來，表示它們都屬于信息集 X4,X5,X6,X7 。圖6-4博弈樹：既不知道1的選擇；也不知道2的選擇最后考察第一種情形，即參與人3既知道參與人1的選擇也知道參與人2的選擇。由于參與人3既知道參與人1的選擇，又知道參與人2的選擇，因此當(dāng)輪到參與人 3行動時，他知道自己在點(diǎn)X4、x5、*6和X7四點(diǎn)中的哪一點(diǎn)上，所以決策集合X4、X5、X6和X7都是參與人3的信息集（參見圖65）圖6-5博弈樹：既知道1的選擇；也知道2的選擇從上面分析可以看到： 如果

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