第三章擴展式博弈與完全信息動態(tài)博弈課件

第三章擴展式博弈與完全信息動態(tài)博弈主要內(nèi)容：一、擴展式博弈二、擴展式博弈的戰(zhàn)略及其Nash均衡三、兩種博弈描述形式的比較第三章擴展式博弈與完全信息動態(tài)博弈主要內(nèi)容：1一、擴展式博弈所謂擴展式博弈(extensiveformgame)是博弈問題的一種規(guī)范性描述。與戰(zhàn)略式博弈側重博弈結果的描述相比，擴展式博弈更注重對參與人在博弈過程中所遇到?jīng)Q策問題的序列結構的詳細分析。一、擴展式博弈所謂擴展式博弈(extensiveform研究博弈問題的具體進程必須弄清楚的兩個問題

每個參與人在什么時候行動(決策)；每個參與人行動時，他所面臨決策問題的結構。這包括參與人行動時可供他選擇的行動方案，以及參與人行動時所了解的信息。研究博弈問題的具體進程必須弄清楚的兩個問題每個參與人在什么擴展式博弈的定義：

擴展式博弈包括以下要素：參與人集合；參與人的行動順序，即每個參與人在何時行動；每個參與人行動時面臨的決策問題，包括參與人行動時可供他選擇的行動方案以及他所了解的信息；參與人的支付函數(shù)，即博弈結束時每個參與人得到的博弈結果。擴展式博弈的定義：擴展式博弈包括以下要素：例子：“新產(chǎn)品開發(fā)博弈”試用擴展式博弈對兩個企業(yè)都知道市場需求，且企業(yè)1先決策，企業(yè)2觀測到企業(yè)1的選擇后再進行選擇的博弈情形即完全信息動態(tài)的“新產(chǎn)品開發(fā)博弈”進行建模。例子：“新產(chǎn)品開發(fā)博弈”試用擴展式博弈對兩個企業(yè)都知道市場完全信息動態(tài)的“新產(chǎn)品開發(fā)博弈”的擴展式博弈包括以下要素：參與人是企業(yè)1和2；企業(yè)1先行動，企業(yè)2后行動；企業(yè)1行動時有兩種選擇——“開發(fā)”和“不開發(fā)”，企業(yè)1行動時不知道企業(yè)2的行動；企業(yè)2行動時有兩種選擇——“開發(fā)”和“不開發(fā)”，但企業(yè)2行動時已經(jīng)知道企業(yè)1的行動；完全信息動態(tài)的“新產(chǎn)品開發(fā)博弈”的擴展式博弈包括以下要素：參(4)兩個企業(yè)的支付如下：(4)兩個企業(yè)的支付如下：例子中，用文字描述的方法給出了博弈問題的擴展式描述。但可以想象，如果我們遇到的是更為復雜的博弈問題，文字描述可以？例子中，用文字描述的方法給出了博弈問題的擴展式描述。十分直觀的擴展式博弈的描述方式——博弈樹。第三章擴展式博弈與完全信息動態(tài)博弈ppt課件所謂博弈樹就是由結和有向枝構成的“有向樹”。所謂博弈樹就是由結和有向枝構成的“有向樹”。最上端的一個點(用空心圓表示)，表示博弈的開始。將“企業(yè)1”標示在點x1上，表示博弈開始于企業(yè)1的選擇。

企業(yè)1的選擇有“開發(fā)”和“不開發(fā)”，分別用標有“開發(fā)”和“不開發(fā)”的有向枝表示。

表示博弈達到該點時企業(yè)的所得，其中，支付向量中的第一個數(shù)字表示企業(yè)1的所得，第二個數(shù)字表示企業(yè)2的所得。最上端的一個點(用空心圓表示)，表示博弈的開始。將“企業(yè)1稱為博弈樹的結(node)決策結稱為博弈樹的結(node)決策結回過來再考察上圖中的博弈樹，可以得到這樣的信息：博弈中的參與人是企業(yè)1和企業(yè)2；博弈中企業(yè)1先選擇，企業(yè)2后選擇；企業(yè)1選擇時有行動“開發(fā)”和“不開發(fā)”，企業(yè)2選擇的行動有“開發(fā)”和“不開發(fā)”；博弈中企業(yè)的支付?；剡^來再考察上圖中的博弈樹，可以得到這樣的信息：博弈中的參也就是說，除了“企業(yè)2行動時是否觀測到企業(yè)1的選擇”這一點，暫時無法從上圖中知道以外，完全信息動態(tài)的“新產(chǎn)品開發(fā)博弈”的擴展式描述所需要的信息(或要素)，都可以從上圖中得到。也就是說，除了“企業(yè)2行動時是否觀測到企業(yè)1的選擇”這一點，如果還能夠直接從博弈樹中知道“企業(yè)2行動時是否觀測到企業(yè)1的選擇”，那么給出博弈樹，就意味著給出了完全信息動態(tài)的“新產(chǎn)品開發(fā)博弈”的擴展式描述。如果還能夠直接從博弈樹中知道“企業(yè)2行動時是否觀測到企業(yè)1的問題：如何在博弈樹中，將“企業(yè)2行動時是否觀測到企業(yè)1的選擇”這一信息表示出來？問題：如何在博弈樹中，將“企業(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的選擇。在完全信息動態(tài)的“新產(chǎn)品開發(fā)博弈”中，企業(yè)2決策時，企業(yè)1已對于第一種情形，企業(yè)2知道企業(yè)1的選擇，即知道企業(yè)1選擇了“開發(fā)”還是“不開發(fā)”，因此，企業(yè)2知道博弈是從x1到了x2還是從x1到了x3。這就意味著當輪到企業(yè)2決策時，他知道自己是在點x2上還是在點x3上；對于第一種情形，企業(yè)2知道企業(yè)1的選擇，即知道企業(yè)1選擇了“對于第二種情形，企業(yè)2不知道企業(yè)1的選擇，即不知道博弈是從x1到了x2還是從x1到了x3。因此，當輪到企業(yè)2決策時，他不知道自己是在點x2上還是在點x3上。所以，“企業(yè)2行動時是否觀測到企業(yè)1的選擇”這一問題，實際上就等價于“企業(yè)2行動時是否知道自己是在博弈樹中的點x2上還是在點x3上”。對于第二種情形，企業(yè)2不知道企業(yè)1的選擇，即不知道博弈是從x為了將“企業(yè)2行動時是否知道自己是在博弈樹中的點x2上還是在點x3上”這一點說清楚，需要引入“信息集”(informationset)的概念。為了將“企業(yè)2行動時是否知道自己是在博弈樹中的點x2上還是在在博弈樹中，參與人i的一個信息集(用Ii表示)是參與人i決策結的一個集合，它滿足以下兩個條件：

Ii中的每個決策結都是參與人i的決策結；當博弈到達信息集Ii(即博弈到達Ii中某個決策結)時，參與人i知道自己是在信息集Ii中的決策結上，但不知道自己究竟在Ii中哪個決策結上。在博弈樹中，參與人i的一個信息集(用Ii表示)是參與人i決策因此，參與人i的信息集Ii可以用來描述：當輪到參與人i行動時，他所了解到的信息，即他知道什么(知道自己位于哪一個信息集上)、不知道什么(不知道自己位于信息集中哪一個決策結上)。因此，參與人i的信息集Ii可以用來描述：當輪到參與人i行動時例如在“新產(chǎn)品開發(fā)博弈”中，假設企業(yè)1先行動，企業(yè)2后行動，但企業(yè)2行動時不知道企業(yè)1的行動。企業(yè)2行動時，只知道博弈要么到達點x2，要么達到點x3

，但具體在哪一點上，企業(yè)2不清楚。也就是說，企業(yè)2只知道自己位于決策結集合{x2,x3}上，但不知道位于{x2,x3}中哪一個決策結上。

例如在“新產(chǎn)品開發(fā)博弈”中，假設企業(yè)1先行動，企業(yè)2后行動設X為一決策結集合，用Ii(X)表示參與人的由決策結集X構成的一個信息集。例如，I2({x2,x3})表示企業(yè)2的由決策結集{x2,x3}構成的信息集，I2({x2})和I2({x3})分別表示企業(yè)2的由決策結集{x2}和{x3}構成的信息集。可以在博弈樹中將同一信息集中的決策結用虛線連接起來。設X為一決策結集合，用Ii(X)表示參與人的由決策結集X構成下圖表示參與人3選擇時，知道參與人1的選擇，但不知道參與人2的選擇的博弈情形。下圖表示參與人3選擇時，知道參與人1的選擇，但不知道參與人2下圖表示參與人3選擇時，知道參與人2的選擇，但不知道參與人1的選擇的博弈情形。下圖表示參與人3選擇時，知道參與人2的選擇，但不知道參與人1下圖表示參與人3選擇時，即不知道參與人2的選擇，也不知道參與人1的選擇的博弈情形。下圖表示參與人3選擇時，即不知道參與人2的選擇，也不知道參與下圖表示參與人3選擇時，即知道參與人2的選擇，也知道參與人1的選擇的博弈情形。下圖表示參與人3選擇時，即知道參與人2的選擇，也知道參與人1

在以后的討論中，我們假設博弈樹中的博弈都是從上往下進行的，因此，在不引起歧義的情況下，我們都不標示出博弈樹中枝的方向。在以后的討論中，我們假設博弈樹中的博弈例子：考察“新產(chǎn)品開發(fā)博弈”。試用博弈樹描述“兩個企業(yè)都知道市場需求，且企業(yè)1先決策，企業(yè)2觀測到企業(yè)1的選擇后再進行選擇”的博弈情形。例子：考察“新產(chǎn)品開發(fā)博弈”。試用博弈樹描述“兩個企業(yè)都知道當市場需求大時，“新產(chǎn)品開發(fā)博弈”的博弈樹當市場需求大時，“新產(chǎn)品開發(fā)博弈”的博弈樹當市場需求小時，“新產(chǎn)品開發(fā)博弈”的博弈樹當市場需求小時，“新產(chǎn)品開發(fā)博弈”的博弈樹由于在博弈分析中，假設博弈的結構(或描述方式)為共同知識，因此，在以后的討論中，如果給出博弈樹，就意味著所有的參與人都同時一起看到了博弈樹。由于在博弈分析中，假設博弈的結構(或描述方式)為共同知識，因除了前面一再提到的博弈結構和參與人完全理性為共同知識外，對于多階段的動態(tài)博弈問題，一般還假設參與人滿足“完美記憶”(perfectrecall)要求，即假設參與人不會忘記以前知道或者做過的事情。除了前面一再提到的博弈結構和參與人完全理性為共同知識外，對于但在現(xiàn)實生活中，不滿足“完美記憶”要求的情形比比皆是。例如，人們在玩撲克時，往往會忘記自己曾經(jīng)出過什么牌或者對手曾經(jīng)出過什么牌；在棋類比賽中，也會出現(xiàn)這種情況。但在現(xiàn)實生活中，不滿足“完美記憶”要求的情形比比皆是。例如，但是，在博弈分析中，如果沒有“完美記憶”假設，各種博弈結果都有可能出現(xiàn)，那么我們也就無法對博弈進行預測。但是，在博弈分析中，如果沒有“完美記憶”假設，各種博弈結果都不滿足“完美記憶”要求的博弈情形參與人1第二次行動時忘了他第一次行動時的選擇。不滿足“完美記憶”要求的博弈情形參與人1第二次行動時忘了他第二、擴展式博弈的戰(zhàn)略及其Nash均衡提出一個問題：給定一個博弈問題的擴展式，該如何來求解博弈問題的解？已知對于戰(zhàn)略式博弈，可以用Nash均衡來描述博弈問題的解，對于博弈樹所描述的擴展式博弈，是否同樣可以用Nash均衡來描述博弈問題的解？二、擴展式博弈的戰(zhàn)略及其Nash均衡提出一個問題：給定一個博對于一個博弈問題，要給出其戰(zhàn)略式描述，就必須定義清楚該博弈問題的三個要素：參與人、參與人的戰(zhàn)略以及參與人在相應戰(zhàn)略組合下的支付。對于一個博弈問題，要給出其戰(zhàn)略式描述，就必須定義清楚該博弈問一個擴展式博弈實際上已定義了博弈的參與人及參與人的支付，因此，如果能定義一個擴展式博弈的戰(zhàn)略，那么就意味著給出了一個擴展式博弈的戰(zhàn)略式描述，同時也就意味著可以用Nash均衡來描述博弈的解。一個擴展式博弈實際上已定義了博弈的參與人及參與人的支付，因此所謂參與人的戰(zhàn)略就是參與人在博弈中的行動規(guī)則，它規(guī)定了參與人在博弈中每一種輪到自己行動的情形下，應該采取的行動。所謂參與人的戰(zhàn)略就是參與人在博弈中的行動規(guī)則，它規(guī)定了參與人而在博弈樹中，參與人在博弈中每一種輪到自己行動的情形又可以用一個信息集來表示，因此，參與人在擴展式博弈中的戰(zhàn)略實際上就是參與人在每個信息集上的行動規(guī)則。而在博弈樹中，參與人在博弈中每一種輪到自己行動的情形又可以用用Hi表示博弈樹中參與人i的信息集的集合，即Hi=(Ii)；用Ai(Ii)表示參與人i在信息集Ii上的行動集，Ai(Hi)表示參與人在所有信息集上的行動集合，即用Hi表示博弈樹中參與人i的信息集的集合，即Hi=(Ii參與人i的一個純戰(zhàn)略si就是從信息集集合Hi到行動集合Ai(Hi)的一個映射關系，即其中，對參與人i的一個純戰(zhàn)略si就是從信息集集合Hi到行動集合Ai(根據(jù)上述定義，參與人i的一個純戰(zhàn)略可以解釋為參與人i在各個信息集上的行動組合。因此，在以后的討論中，可以用參與人i在每個信息集上的行動集Ai(Ii)的笛卡爾積來表示參與人i的戰(zhàn)略集Si，即根據(jù)上述定義，參與人i的一個純戰(zhàn)略可以解釋為參與人i在各個信例如：例如：參與人2的信息集為I2

({x2})，參與人2在I2

({x2})上的行動集為{C,D}。所以，參與人2的戰(zhàn)略集為{C,D}

；

參與人1的信息集為I1

({x1})和I1

({x3})，其中參與人1在I1

({x1})上的行動集為{A,B}，在I1

({x3})上的行動集為{E,F}。所以，參與人1的戰(zhàn)略集為{A,B}×{E,F}，即{A,E}、{A,F}、{B,E}和{B,F}。參與人2的信息集為I2({x2})，參與人2在I2({x給定一個博弈問題的擴展式描述，可以得到參與人的戰(zhàn)略以及參與人在各戰(zhàn)略組合下的支付，所以，由一個博弈問題的擴展式描述可以得到該博弈問題的戰(zhàn)略式描述。給定一個博弈問題的擴展式描述，可以得到參與人的戰(zhàn)略以及參與人例如擴展式描述戰(zhàn)略式描述例如擴展式描述戰(zhàn)略式描述由左圖可得前面所示的擴展式博弈的Nash均衡——((B,E),D)和((B,F),D)。由左圖可得前面所示的擴展式博弈的Nash均衡——((B,E)三、兩種博弈描述形式的比較戰(zhàn)略式博弈從本質上來講是一種靜態(tài)模型。擴展式博弈從本質上來講是一種動態(tài)模型。三、兩種博弈描述形式的比較戰(zhàn)略式博弈從本質上來講是一種靜態(tài)模1.戰(zhàn)略式博弈從本質上來講是一種靜態(tài)模型戰(zhàn)略式博弈從本質上來講是一種靜態(tài)模型，它假設所有的參與人同時選擇戰(zhàn)略并得到博弈的結果，至于博弈中參與人何時行動、行動時又如何行動等等，戰(zhàn)略式博弈并不考慮。1.戰(zhàn)略式