北京大學博弈論課件第3章-完全信息動態(tài)博弈

第三章

完全信息動態(tài)博弈第三章

完全信息動態(tài)博弈在完全信息動態(tài)博弈中，博弈參與者的行動存在先后順序。可以用博弈樹表示完全信息動態(tài)博弈?？梢酝ㄟ^逆向歸納法求解完全信息動態(tài)博弈的子博弈精煉納什均衡，剔除不可置信的威脅。在完全信息動態(tài)博弈中，博弈參與者的行動存在先后順序。第一節(jié)完全信息動態(tài)博弈概述一、完全信息動態(tài)博弈的定義在完全信息靜態(tài)博弈中，博弈參與者同時采取行動。但在完全信息動態(tài)博弈中，博弈參與者的行動存在先后順序。從信息角度上，完全信息動態(tài)博弈與完全信息靜態(tài)博弈類似，博弈參與者對博弈結構、博弈順序、雙方收益等信息都具備完全了解。第一節(jié)完全信息動態(tài)博弈概述一、完全信息動態(tài)博弈的定義二、博弈樹在動態(tài)博弈中，由于博弈參與者的行動存在先后順序，因此可以用更形象的方法來表示動態(tài)博弈：博弈樹（GameTree）。通過支付矩陣的形式表示的博弈通常被稱為策略型或正則型博弈（NormalFormGame）。通過博弈樹表示的博弈通常被稱為擴展型博弈（ExtensiveFormGame）。二、博弈樹在動態(tài)博弈中，由于博弈參與者的行動存在先后順序，因動態(tài)市場爭奪戰(zhàn)博弈的擴展型表達方式如圖所示“市場爭奪戰(zhàn)”博弈的擴展型表達形式動態(tài)市場爭奪戰(zhàn)博弈的擴展型表達方式如圖所示“市場爭奪戰(zhàn)”博弈1．博弈樹的構成要素（1）博弈參與者（2）行動順序：在動態(tài)博弈中，博弈參與者的行動存在先后次序。（3）行動策略空間（ActionSet）：指博弈參與者可以采取的所有可能策略。（4）信息集（InformationSet）：指博弈參與者在博弈過程中所知道的信息。（5）支付函數(shù)指博弈參與者采用特定策略與所能得到的收益之間的關系。1．博弈樹的構成要素（1）博弈參與者2．博弈樹的結構（1）博弈樹的構造方法首先行動的一方位于博弈樹的最上端，根據(jù)動態(tài)博弈過程中各方的行動順序，博弈數(shù)自上至下延展。也有學者習慣自左至右構造博弈樹。橫向博弈樹2．博弈樹的結構（1）博弈樹的構造方法橫向博弈樹博弈樹中包含若干“節(jié)點”，節(jié)點用小圓圈表示。位于博弈樹最上端的節(jié)點稱為“初始節(jié)點”。初始節(jié)點用空心小圓圈表示，其他節(jié)點均用實心小圓圈表示。在每個節(jié)點處均對應某個博弈參與者，將節(jié)點對應的博弈參與者標識在節(jié)點旁邊。例如：在“市場爭奪戰(zhàn)”博弈中，因為潛在進入者先行動，因此初始節(jié)點處對應的博弈參與者為潛在進入者。將潛在進入者標識在博弈樹初始節(jié)點旁邊。當潛在進入者決策之后，輪到在位者進行決策。在位者所在的節(jié)點稱為“后續(xù)節(jié)點”。在位者位于兩個后續(xù)節(jié)點上。在位者都有兩種策略選擇：“斗爭”和“默許”。博弈樹中包含若干“節(jié)點”，節(jié)點用小圓圈表示。如果初始節(jié)點處的博弈參與者存在N種策略，那么就從初始節(jié)點處分出N條路徑。路徑用線段表示。在線段旁注明相應的策略。在“市場爭奪戰(zhàn)”博弈中，首先行動的潛在進入者可以采取兩種策略：“不進入”和“進入”。因此，從初始節(jié)點處引出兩條線段，在兩條線段旁分別標識“不進入”和“進入”。當潛在進入者選擇結束后，達到在位者的節(jié)點。在位者有兩個選擇：“斗爭”和“默許”。因此，從在位者的節(jié)點處引出兩條線段，在兩條線段旁分別標識“斗爭”和“默許”。如果初始節(jié)點處的博弈參與者存在N種策略，那么就從初始節(jié)點當博弈不再有后續(xù)節(jié)點時，需要將博弈的收益標識在博弈樹末端。將博弈參與者的收益放在括號里。需要注意的是：各博弈參與者的收益需要按照各參與者行動順序進行排列。先行動的博弈參與者的收益寫在左邊，依次類推，從左到右，最后行動的博弈參與者的收益寫在最右邊。各個博弈參與者的收益之間用逗號分割。當博弈不再有后續(xù)節(jié)點時，需要將博弈的收益標識在博弈樹末端。（2）博弈樹與博弈順序博弈樹各節(jié)點之間存在順序關系，博弈樹由上至下的節(jié)點順序表示各博弈參與者進行決策的順序。（2）博弈樹與博弈順序從博弈樹的節(jié)點可以引出多條線段，但不能從博弈樹多個節(jié)點共同到達博弈樹下方同一個后續(xù)節(jié)點。錯誤的博弈樹構造方法從博弈樹的節(jié)點可以引出多條線段，但不能從博弈樹多個節(jié)點共同到正確的博弈樹構造方法正確的博弈樹構造方法正確的博弈樹構造方法正確的博弈樹構造方法構造博弈樹時只能按照由上至下的路徑，而不能存在由下向上的路徑，也不能形成循環(huán)路徑?；厮萋窂轿ㄒ恍栽谇蠼馔耆畔討B(tài)博弈時非常重要。因為在求解動態(tài)博弈均衡時，一個很重要的方法是“逆向歸納法（BackwardInduction）”。只有首先確保從博弈樹任何最終節(jié)點向上回溯時路徑唯一，才能確保逆向歸納法的可操作性。構造博弈樹時只能按照由上至下的路徑，而不能存在由下向上的路徑正確的博弈樹構造方法正確的博弈樹構造方法正確的博弈樹構造方法正確的博弈樹構造方法錯誤的博弈樹構造方法錯誤的博弈樹構造方法錯誤的博弈樹構造方法錯誤的博弈樹構造方法三、信息集與三人罷工博弈在完全信息動態(tài)博弈中，如果將博弈樹的多個節(jié)點用虛線連接起來，表明這多個節(jié)點位于同一個博弈信息集中。也就是說：博弈參與者不知道自己位于同一個信息中的哪個博弈節(jié)點上?？梢酝ㄟ^“三人罷工博弈”來說明信息集的含義以及信息集在動態(tài)博弈中的重要性。三、信息集與三人罷工博弈在完全信息動態(tài)博弈中，如果將博弈樹的1．三人罷工博弈的定義三人罷工博弈的博弈樹1．三人罷工博弈的定義三人罷工博弈的博弈樹2．三人罷工博弈的策略選擇與信息員工2只有一個信息集的博弈樹2．三人罷工博弈的策略選擇與信息員工2只有一個信息集的博員工3不能觀察到員工2的決策策略員工3不能觀察到員工2的決策策略員工3不知道員工1的決策策略員工3不知道員工1的決策策略員工3不知道員工1和員工2的決策策略員工3不知道員工1和員工2的決策策略三名員工都只有一個信息集的博弈三名員工都只有一個信息集的博弈四、博弈樹與靜態(tài)博弈博弈樹的方法不僅能表示動態(tài)博弈，還能表示靜態(tài)博弈。所謂的“博弈先后順序”，它主要是一個信息的概念，而不是一個純時間先后的概念。用博弈樹表示囚徒困境四、博弈樹與靜態(tài)博弈博弈樹的方法不僅能表示動態(tài)博弈，還能表示下面三種博弈表達方式所表達的博弈內涵相同嫌疑人乙坦白不坦白嫌疑人甲坦白（5，5）（1，10）不坦白（10，1）（2，2）下面三種博弈表達方式所表達的博弈內涵相同嫌疑人乙坦白不坦白嫌第二節(jié)完全且完美信息動態(tài)博弈概述在完全且完美信息動態(tài)博弈（DynamicGamewithPerfectandCompleteInformation）中，每個博弈參與者均知道在自己之前進行決策的參與者選擇的策略和博弈結構。博弈樹中每個節(jié)點都獨立構成一個信息集，沒有虛線連接兩個或多個博弈樹節(jié)點。求解完全且完美信息動態(tài)博弈的重要方法之一是：逆向歸納法。可以通過“海盜分寶博弈”這個生動有趣的故事對“逆向歸納法”進行一個直觀介紹。第二節(jié)完全且完美信息動態(tài)博弈概述在完全且完美信息動態(tài)博弈一、海盜分寶博弈1．海盜分寶博弈的規(guī)則五個海盜首先進行抽簽，確定決策順序。五個海盜按照決策順序依次提出對100個金幣的分配方案。第一個海盜提出一個分配方案，如超過半數(shù)的海盜（包括提出分配方案的海盜）同意第一個海盜的分配方案，即大于等于3名海盜同意第一個海盜的分配方案時，那么該方案被通過，博弈結束。如果第一個海盜提出的分配方案沒有得到超過半數(shù)海盜的同意，那么第一個海盜將被扔到海里喂鯊魚。接下來由第二個海盜提出分配方案，如果超過半數(shù)的海盜同意第二個海盜的分配方案時，那么該方案被通過，博弈結束。一、海盜分寶博弈1．海盜分寶博弈的規(guī)則如果第二個海盜提出的分配方案沒有得到超過半數(shù)海盜的同意，那么第二個海盜也將被扔到海里喂鯊魚。接下來由第三個海盜提出分配方案，如果超過半數(shù)的海盜，即大于等于2名海盜，同意第三個海盜的分配方案時，那么該方案被通過，博弈結束。如果第三個海盜提出的分配方案沒有得到超過半數(shù)海盜的同意，那么第三個海盜也將被扔到海里喂鯊魚。接下來由第四個海盜提出分配方案。如果超過半數(shù)的海盜同意第四個海盜的分配方案時，那么該方案被通過，博弈結束。如果第二個海盜提出的分配方案沒有得到超過半數(shù)海盜的同意，那么如果第四個海盜提出的分配方案沒有得到超過半數(shù)海盜的同意，那么第四個海盜也將被扔到海里喂鯊魚。這時就只剩下第五個海盜了，第五個海盜將獨吞搶劫來的100個金幣，博弈結束。在這種分配規(guī)則下，第一個海盜將提出怎樣的分配方案？第一個海盜提出的分配方案需要滿足兩個條件。第一，保證超過半數(shù)的海盜同意第一個海盜的分配方案。第二：第一個海盜最大化自己能分到的金幣。如果直接從第一個海盜的決策策略入手，此問題相對復雜。不妨從第五個海盜入手，然后按照從后向前的順序依次逆向考察海盜的策略選擇。如果第四個海盜提出的分配方案沒有得到超過半數(shù)海盜的同意，那么2．求解海盜分寶博弈的均衡第一個海盜將提出怎樣的分配方案？此分配方案在保證能得到超過半數(shù)海盜同意的前提下應最大化第一個海盜的利益。輪次分配方案提出者分配方案最后一輪海盜5自己獨吞全部100個金幣倒數(shù)第二輪海盜4任何分配方案都得不到通過倒數(shù)第三輪海盜3分配給第三個海盜100個金幣，第四個海盜0個金幣，第五個海盜0個金幣。倒數(shù)第四輪海盜2分配給自己98個金幣，第三個海盜0個金幣，第四個海盜1個金幣、第5個海盜1個金幣。通過逆向歸納法推導出的財寶分配方案2．求解海盜分寶博弈的均衡第一個海盜將提出怎樣的分配方案？此3．海盜分寶博弈的均衡第一個海盜的分配方案可以有兩種。分配方案1：分配給自己97個金幣，給第二個海盜0個金幣，給第三個海盜1個金幣，給第四個海盜2個金幣，給第五個海盜0個金幣。分配方案2：分配給自己97個金幣，給第二個海盜0個金幣，給第三個海盜1個金幣，給第四個海盜0個金幣，給第五個海盜2個金幣。如果第一個海盜提出分配方案1，那么第二個海盜和第五個海盜將反對，而第一個、第三個和第四個海盜將同意，因此第一個海盜的提議將獲得通過。如果第一個海盜提出分配方案2，那么第二個海盜和第四個海盜將反對，而第一個、第三個和第五個海盜將同意，因此第一個海盜的提議將獲得通過。3．海盜分寶博弈的均衡第一個海盜的分配方案可以有兩種。二、擴展形式博弈的策略表達方式1．將擴展形式的博弈改寫為策略形式動態(tài)博弈的擴展表達形式二、擴展形式博弈的策略表達方式1．將擴展形式的博弈改寫為策略參與者2UV參與者1L（a1，b1）（a2，b2）R（a3，b3）（a4，b4

）錯誤的動態(tài)博弈策略表達形式參與者2UV參與者1L（a1，b1）（a2，b2）R（a參與者2（U，U）（U，V）（V，U）（V，V）參與者1L（a1，b1）（a1，b1）（a2，b2）（a2，b2）R（a3，b3）（a4，b4）（a3，b3）（a4，b4）動態(tài)博弈的策略表達形式參與者2（U，U）（U，V）（V，U）（V，V）參與者1L（參與者2(U,U,U)(U,U,V)(U,V,U)(U,V,V)(V,U,U)(V,U,V)(V,V,U)(V,V,V)參與者1L（a1,b1）（a1,b1）（a1,b1）（a1,b1）（a2,b2）（a2,b2）（a2,b2）（a2,b2）M（a3,b3）（a3,b3）（a4,b4）（a4,b4）（a3,b3）（a3,b3）（a4,b4）（a4,b4）R（a5,b5）（a6,b6）（a5,b5）（a6,b6）（a5,b5）（a6,b6）（a5,b5）（a6,b6）動態(tài)博弈的擴展表達形式動態(tài)博弈的策略表達形式參與者2(U,U,U)(U,U,V)(U,V,U)(U,V,2．擴展形式轉化為策略形式時的規(guī)律參與者1的純策略空間為：參與者2的純策略空間為：參與者3的純策略空間為：2．擴展形式轉化為策略形式時的規(guī)律參與者1的純策略空間為參與者2的純策略空間為：參與者1的純策略空間為：參與者2的純策略空間為：第三節(jié)子博弈與逆向歸納法在圖中，用虛線框起來的部分稱作一個子博弈（Sub-Game）。第三節(jié)子博弈與逆向歸納法在圖中，用虛線框起來的部分稱作一一、子博弈子博弈是原始動態(tài)博弈的一部分。子博弈包含博弈所需的各種信息，能獨立構成一個博弈。一個博弈的子博弈需要滿足四個條件。1．子博弈的起始節(jié)點不能是原來博弈的起始節(jié)點2．子博弈不能分割信息集3．有些博弈包含多個子博弈4．有些博弈沒有子博弈一、子博弈子博弈是原始動態(tài)博弈的一部分。子博弈包含博弈所需的二、逆向歸納法1．逆向歸納法的定義和求解方法逆向歸納法指：在求解動態(tài)博弈時，首先找到博弈順序在最后的子博弈，找到子博弈中博弈參與者的策略選擇，然后按博弈順序由后向前逆向歸納，直至博弈樹的初始節(jié)點，從而找到博弈的均衡。二、逆向歸納法1．逆向歸納法的定義和求解方法1．逆向歸納法的定義和求解方法逆向歸納法指：在求解動態(tài)博弈時，首先找到博弈順序在最后的子博弈，找到子博弈中博弈參與者的策略選擇，然后按博弈順序由后向前逆向歸納，直至博弈樹的初始節(jié)點，從而找到博弈的均衡。1．逆向歸納法的定義和求解方法北京大學博弈論ppt課件第3章-完全信息動態(tài)博弈2．通過逆向歸納法求解博弈均衡實例2．通過逆向歸納法求解博弈均衡實例三、斯塔貝爾伯格寡頭博弈斯塔貝爾伯格博弈（StackelbergDuopolyGame）是寡頭博弈的一種常見形式，是一種完全信息動態(tài)博弈。1．斯塔貝爾伯格寡頭博弈的定義斯塔貝爾伯格寡頭博弈：市場中有兩個廠商。廠商1先行動，選擇自身產量。廠商2觀察到廠商1選擇的產量后，再決策自己的產量。廠商1通常被稱為領先者，廠商2通常被稱為跟隨者。三、斯塔貝爾伯格寡頭博弈斯塔貝爾伯格博弈（Stackelbe2．求解斯塔貝爾伯格寡頭博弈根據(jù)逆向歸納法，首先考慮廠商2如何選擇自己的產量.作為領先者，廠商1在決定自己的產量時會考慮自己的決策產量對廠商2的影響。求解得到：作為領先者的廠商1的產量為：作為跟隨者的廠商2的產量為：2．求解斯塔貝爾伯格寡頭博弈根據(jù)逆向歸納法，首先考慮廠商23．古諾寡頭博弈與斯塔貝爾伯格寡頭博弈在古諾寡頭博弈中，市場需求函數(shù)和廠商成本函數(shù)與斯塔貝爾伯格博弈均相同。二者的主要區(qū)別是：在古諾寡頭博弈中，兩家廠商同時進行決策，是一個完全信息靜態(tài)博弈。在斯塔貝爾伯格寡頭博弈中，廠商1先行動，廠商2后行動，是一個完全信息動態(tài)博弈。古諾寡頭博弈的均衡是：斯坦貝爾伯格寡頭博弈的均衡是：3．古諾寡頭博弈與斯塔貝爾伯格寡頭博弈在古諾寡頭博弈中，市場斯塔貝爾博弈寡頭博弈均衡示意圖斯塔貝爾博弈寡頭博弈均衡示意圖第四節(jié)子博弈精煉納什均衡澤爾滕（Selten）在1965年提出了“子博弈精煉納什均衡（SubgamePerfectNashEquilibrium）”的概念。子博弈精煉納什均衡也被稱為子博弈完美納什均衡。子博弈精煉納什均衡與納什均衡不同。納什均衡要求：給定其他參與者在均衡處的策略，任何一方博弈參與者在均衡處選擇的策略都是自己所能選擇的最優(yōu)策略，沒有博弈參與者有動機改變自己在均衡時的策略。子博弈精煉納什均衡不僅要求均衡解是納什均衡，而且要求均衡解在每一個信息集上都是最優(yōu)解。第四節(jié)子博弈精煉納什均衡澤爾滕（Selten）在196一、子博弈精煉納什均衡的含義通過逆向歸納法求解博弈樹得到的均衡是子博弈精煉納什均衡。納什均衡僅需要在均衡處，每個博弈參與者沒有動機改變自己的策略。子博弈納什均衡不僅要求均衡滿足納什均衡要求的條件，還要求在動態(tài)博弈中，此均衡是每個子博弈的最優(yōu)解。也就是說：納什均衡只對均衡處的策略有要求。子博弈精煉納什均衡不僅對均衡處的策略有要求，而且對到達均衡的路徑有要求。要求從博弈初始節(jié)點開始，博弈參與者到達均衡處所經(jīng)過的路徑也必須是最優(yōu)的。一、子博弈精煉納什均衡的含義通過逆向歸納法求解博弈樹得到的均在“市場爭奪戰(zhàn)”博弈中，如果在位者選擇“斗爭”，那么潛在進入者會選擇“不進入”。如果在位者選擇“默許”，那么潛在進入者會選擇“進入”。對潛在進入者來說，在位者的“斗爭”策略是一種不可置信的威脅（NoncredibleThreat）或空洞的威脅（EmptyThreat）。子博弈精煉納什均衡就是把包含不可置信威脅的納什均衡從可能的均衡中剔除出去。顧名思義，“子博弈精練納什均衡”是對納什均衡的“精練”。通過剔除包含不可置信威脅的納什均衡，減少納什均衡的數(shù)目。在“市場爭奪戰(zhàn)”博弈中，如果在位者選擇“斗爭”，那么潛在進入二、不可置信的威脅在很多完全信息動態(tài)博弈中，都存在不可置信的威脅。1．“市場爭奪戰(zhàn)”博弈在“市場爭奪戰(zhàn)”博弈中，（潛在進入者不進入，在位者斗爭）這個納什均衡包含不可置信的威脅，因此不是一個子博弈精練納什均衡。如果在位者把“斗爭”變成一個可置信的威脅（CredibleThreat），那么博弈的均衡就會不同。二、不可置信的威脅在很多完全信息動態(tài)博弈中，都存在不可置信的2．斯塔貝爾伯格寡頭博弈如果后行動的跟隨者做出一個“威脅”：不管先行動的領先者選擇何種產量，自己都會將產量定在對于領先者廠商來說，這是一個可置信的威脅如果跟隨者在具有法律約束力的公證機構簽署一項承諾：不管領先者選取何種產量水平，自己都會將產量定在，如果自己違反承諾，那么將自動捐出的收益。跟隨者廠商的承諾變?yōu)橐粋€可置信的承諾。跟隨者廠商不可置信的威脅不會影響到先行動的領先者廠商的產量決策。然而跟隨者可置信的威脅的確會影響到先行動的領先者廠商的產量決策，進而影響博弈均衡。2．斯塔貝爾伯格寡頭博弈如果后行動的跟隨者做出一個“威脅”：三、逆向歸納法的擴展應用逆向歸納法不僅在求解完全且完美信息動態(tài)博弈時非常有用，在某些完全但不完美信息動態(tài)博弈中，逆向歸納法也有一定用武之地。三、逆向歸納法的擴展應用逆向歸納法不僅在求解完全且完美信息動完全且完美信息動態(tài)博弈博弈的均衡路徑是：參與者1選擇策略R，然后參與者2進行決策參與者2選擇策略T，博弈結束。參與者1得到收益3、參與者2得到收益1。完全且完美信息動態(tài)博弈博弈的均衡路徑是：四、逆向歸納法的局限和“蜈蚣博弈”雖然逆向歸納法是求解動態(tài)博弈子博弈精煉納什均衡的有力工具，但根據(jù)逆向歸納法求解出的均衡有時卻是和常理相悖的?；蛘哒f：通過逆向歸納法有時也會求解出“不合理”的均衡。經(jīng)濟學家羅森賽爾（Rosenthsal）提出的“蜈蚣博弈（CentipedeGame）”就是這樣一個典型例證。雖然通過逆向歸納法可以求出蜈蚣博弈的均衡解，但此均衡解的合理性受到了普遍挑戰(zhàn)。因此，蜈蚣博弈有時也被稱為“蜈蚣博弈悖論”，簡稱“蜈蚣悖論（CentipedeParadox）”。四、逆向歸納法的局限和“蜈蚣博弈”雖然逆向歸納法是求解動態(tài)博1．蜈蚣博弈的定義假設有兩名博弈參與者：參與者1和參與者2。兩名參與者輪流進行決策：首先由參與者1進行決策，然后是參與者2，再次是博弈參與者1，然后是博弈參與者2，依次類推。在博弈的初始節(jié)點處，參與者1有兩個策略可以選擇：T和C。策略T表示結束博弈（Terminate），策略C表示繼續(xù)（Continue）博弈。當參與者1選擇策略T時，博弈結束。參與者1得到收益1，參與者2得到收益1。當參與者1選擇策略C時，輪到博弈參與者2進行決策。參與者2同樣面臨兩個策略選擇：策略T