博弈論 第 三 章完全信息動(dòng)態(tài)博弈講解

1、第 三 章 完全信息動(dòng)態(tài)博弈 3.1 動(dòng)態(tài)博弈的表示法和特點(diǎn) 1.定 義 與 博 弈樹(shù) 博弈的展開(kāi)式所包含的信息和內(nèi)容: 參與人的集合,記為i=1,2, n,用N代表虛擬 的參與人“自然”; 行動(dòng)的次序, 即誰(shuí)在什么時(shí)候行動(dòng); 參與人的行動(dòng)空間,即輪到某參與人行動(dòng)時(shí), 他從該時(shí)刻的純策略空間中選取什么策略; 當(dāng)參與人作出他們的行動(dòng)決策時(shí),他所他所 觀(guān)測(cè)到 或他所了解到的信息,即他在此時(shí) 獲得的信息 集合; 參與人的得益(支付或效用), 它們是已 知行動(dòng)的函數(shù); 在任何外生事件的概率分布。 例 房地產(chǎn)開(kāi)發(fā)博弈 有兩個(gè)房地產(chǎn)開(kāi)發(fā)商(分別為參與人1,記為 A和參與人2,記為B) 在某地開(kāi)發(fā)房地產(chǎn),

2、但該 地的房地產(chǎn)需求狀況是不確定的, 假定該博弈 的行動(dòng)順序如下:(1) 開(kāi)發(fā)商1先行動(dòng), 選擇開(kāi) 發(fā)或不開(kāi)發(fā);(2) 在1決策后,“ 自然”選擇需求 的大小;(3) 開(kāi)發(fā)商2在 觀(guān)測(cè)到1的決策和市場(chǎng) 的需求后, 再?zèng)Q定開(kāi)發(fā) 或不開(kāi)發(fā)。( 如 下 圖) 房 地 產(chǎn) 開(kāi) 發(fā) 博 弈 A N N B B B B 開(kāi) 發(fā) 不 開(kāi) 發(fā) 需 求 大 需 求 小 需 求 大 需 求 小 開(kāi) 發(fā) 不開(kāi)發(fā) 開(kāi)發(fā) 不開(kāi)發(fā) 開(kāi)發(fā) 不開(kāi)發(fā) 開(kāi)發(fā) 不開(kāi)發(fā) (4,4) (8,0) (-3,-3) (1,0) (0,8) (0,0) (0,1) (0,0) 單 位:百萬(wàn)元 hA(1) hN(1) hN(2) hB(1)

3、hB(2) hB(3) hB(4) h表示信息集 上述博弈樹(shù)給出了有限博弈的幾乎所有信息。 博 弈 樹(shù) 必 須 滿(mǎn) 足 下 列 規(guī) 則： (1)每一個(gè)結(jié)(node) 至多有一個(gè)其他結(jié)直接位 于 它的前面; (2)在博弈中沒(méi)有一條路徑可以使決策集與自身 相連; (3) 每一個(gè)結(jié)是唯一初始結(jié)的后續(xù)結(jié), 即博弈樹(shù) 必須有初始結(jié); (4) 每個(gè)博弈樹(shù)“正好”只有一個(gè)初始結(jié)(多于 一個(gè) 可以用“ 自 然”連接。 不允許出現(xiàn)的情況：不允許出現(xiàn)的情況： 由以上規(guī)則，對(duì)于博弈樹(shù)中的每一個(gè)終點(diǎn)結(jié)， 我們，完全可以確定從初始結(jié)到終點(diǎn) 結(jié)的路 徑，同時(shí)也展示了博弈的動(dòng)態(tài)過(guò)程。 信息集:博弈樹(shù)上的所有決策集分割成不同

4、的信 息集， 我們用hH來(lái)表示這個(gè)信息。如果 一個(gè)信息集包含 結(jié)x,我們就可以將該信息集 記為h(x), 如果一個(gè)信息 集只包含一個(gè)結(jié),這 是最簡(jiǎn)的情況。我們主要關(guān)心的 是一個(gè)信息 集包含不止一個(gè)結(jié), 假設(shè)x與xh(x), 則恰 好擁有信息h(x) 并正在選擇自己行動(dòng)的參與 人其實(shí)對(duì)自己究竟是處于x還界x是不確定的。 要 求： 如 果xh(x), 則x與x 應(yīng) 該由同 一 個(gè)參與人采取行動(dòng)，且可以選擇的策略空 間 相同：A(x)=A(x), 由此可以將信息集h上 的 行動(dòng)集記 為A(h)。 如果博弈樹(shù)的所有信息集都是單結(jié)的, 則稱(chēng)該 博弈為完美(perfect)息 博弈。(無(wú)虛線(xiàn)連接), 而完

5、全(complete)信息博弈是指得益函數(shù)和純 策略空間均為博弈各方的共同知識(shí)。完全信息 可以是完美的也可以是不完美的。 3.2 展開(kāi)型博弈的策略與均衡展開(kāi)型博弈的策略與均衡 一、 行 為 策 略 在策略型博弈中, 參與人的策略是進(jìn)行博 弈的計(jì)劃( 或打算)的詳細(xì)集合, 而在展 開(kāi)型博弈中 參與人的策略必須確定在該 參與人的每一個(gè)決 策集上 所 采 取 的 行 動(dòng),又 結(jié) 與 信 息 集 緊 密 相 連, 對(duì) 于 參 與 人i,基于信息hi的行動(dòng)的 的全體記漢A(hi),如果令Hi表示參與人i的信息 集 的集合,則Ai= A(hi)就是參與人i的所有行 動(dòng) 的集合。參與人i的一個(gè)純策略是從Hi

6、到Ai的一 個(gè)映射si:對(duì)每一個(gè)hiAi,si(h i)Ai,所有這些 si的全體記為Si,即的的純策略空間Si,由此: Si= A(hi) hi H i hi H i 例 參與人2有兩個(gè)策略集,相應(yīng)地也有兩個(gè)信息集 A(h2(1)=A(h2(2)=左,右 1 2 2 1 1 1 1 上 上 下 下 左 右 左 右 右 A B A B C D C D h2(1) h2(2) h1(1) h1(2) h1(3) 其中H2=h2(1),h2(2);參與人2的純策略空間為: S2=(A(h2(1),Ah2(2)=(左,右)(左,右) =(左,左),(左,右),(右,左),(右,右),其中純策略 (左

7、,左)表明:當(dāng)1取“上”時(shí),2取“左”;當(dāng)1取 “下”時(shí),2取“左”, 參與人1有三個(gè)信息集H1=hi(i),i=1,2,3,1的純 策略空間為:S1=A(h1(1)A(h1(2)A(h1(3) =(上,下)(A,B)(C,D),共8種純策略。 一般地,參與人I的純策略空間的純策略數(shù)目為: Si= (A(hi) hiHi 展開(kāi)型博弈中純策略是由信息集與行動(dòng)集展開(kāi)型博弈中純策略是由信息集與行動(dòng)集 定義 的的( 與靜態(tài)博弈不同,靜態(tài)博弈中采取純 策略與 采取某行動(dòng)是一個(gè)意思)。 純策略組合純策略組合(剖面剖面profile) 是由參與人各自是由參與人各自 的純策 略空間中的任一純策略構(gòu)成的組 合，

8、在任一純 策略組合s下，總可以從 初始結(jié)開(kāi)始，沿著博弈樹(shù)的某條路徑 (path), 達(dá)到s相應(yīng)的終點(diǎn)結(jié)。 有一個(gè)事 實(shí)非常重要：s中有些信息集在博弈 樹(shù) 的這條路徑上，我們稱(chēng)這些信息集是s的的 路 徑(path), 當(dāng)然也可能存在s中某些信 息集不在 此路徑上。 定義了純策略的得益函數(shù)后，我們就可以定義 展 開(kāi)型博弈的Nash 均衡； 定義 策略組合s*=(s 1*,si*,sn*)是展開(kāi)型 博弈的 一個(gè)Nash均衡，如果對(duì)每一個(gè)i,si*最大化ui(si,s-i*): 即 s i*arg max ui(si*,s-i*),對(duì)任一i 策略型博弈的混合策略實(shí)際上是純策略空間上 的 概率分布，因此

9、展開(kāi)型博弈中參與人 i的混 合策略也 可以看作是其純策略空間 Si上的任一 概率分布。 “ 參與人的每一個(gè)特定的純策略si相當(dāng)于一 本指導(dǎo)說(shuō)明書(shū)，書(shū)中每一頁(yè)表示到了一 個(gè)特定的信息集hi,在 該頁(yè)上告訴i 如何 行動(dòng)。許多的si 相當(dāng)于許多的說(shuō) 明書(shū)， Si表示這些說(shuō)明書(shū)的全體。混合策略相當(dāng) 于i 以一定的概率分布隨機(jī)地抽取一本說(shuō) 明書(shū)” (Luce F(f) 表 示攤牌;M表示對(duì)抗;P表示 放棄。 該博弈有唯一的Nash均衡(1,2)=(1/3(Rr)+2/2(Rf), 2/3(M)+1/3(P),它與信念體系一起構(gòu)成序貫均衡。 習(xí) 題 1.寫(xiě)出下列博弈的策略型表示: (1) (2) 1 2

10、 2 U D L R L R (2,1) (0,0) (-1,1) (3,2) 1 2 2 U D L R L R (2,1) (0,0) (-1,1) (3,2) (3) N 1 1 2 2 1/3 2/3 Y1 z1 x1 w1 (2,6) (5,6) a2 b2 a2 b2 (9,0) (0,3) (9,5) (0,3) 3.3 子 博 弈 與 子 博 弈 完 美 Nash 均衡在原則上適用所有的博弈,但對(duì)于預(yù) 測(cè) 參與人的行為來(lái)說(shuō),Nash均衡可能并不是 一個(gè) 合理的預(yù)測(cè), 如房地產(chǎn)博弈: A B B 開(kāi) 不 開(kāi) 不 開(kāi) 不 (-3,-3) (1,0) (0,1) (0,0) 的 策

11、略 式 表 示 為: ( 開(kāi), 開(kāi)) ( 開(kāi), 不) ( 不, 開(kāi)) ( 不, 不) 開(kāi) -3,-3 -3,-3 1,0 1,0 不 0,1 0,0 0,1 0,0 參 與 人B 參 與 人A 由 由 畫(huà)畫(huà) 線(xiàn)線(xiàn) 法法 可可 得得 三三 個(gè)個(gè) 純純 策策 略略Nash 均均 衡衡: ( 不 開(kāi) 發(fā),( 開(kāi) 發(fā), 開(kāi) 發(fā)) ( 開(kāi)開(kāi) 發(fā)發(fā),( 不不 開(kāi)開(kāi) 發(fā)發(fā), 不不 開(kāi)開(kāi) 發(fā)發(fā)) ( 開(kāi) 發(fā),( 不 開(kāi) 發(fā), 開(kāi) 發(fā)) 但中B的策略是不合理的,這個(gè)威脅是不可置 信的;中B的策略(不開(kāi)發(fā),不開(kāi)發(fā))也不合理, 因?yàn)槿鬉不開(kāi)發(fā),B顯然應(yīng)該開(kāi)發(fā); 只有是一 個(gè)合理的均衡。個(gè)合理的均衡。 2.3.1 子

12、 博 弈 定 義 一 個(gè) 展 開(kāi) 式 博 弈 的 子 博 弈G 由 一 個(gè) 決 策 結(jié)x 和 所 有 該 決 策 結(jié) 的 后繼結(jié)T(x)( 包 括終點(diǎn)結(jié)0 組 成, 它 滿(mǎn) 足 下 列 條 件:x 是 一 個(gè) 單 點(diǎn) 信 息 結(jié)即h(x)=x;對(duì)于所有的 xT(x), 如果xh(x), 則xT(x) 。 例 房 地 產(chǎn) 博 弈 A B B 開(kāi) 開(kāi) 不 不 開(kāi) 不 開(kāi) 不 有子博弈: 和子博弈: X X B B x X 開(kāi)開(kāi) 不 不 開(kāi)開(kāi) 不 不 1 2 2 U D L R L R 無(wú)(真)子博弈 1 2 2 3 3 3 3 U D L R L R C D C D C D C D 參與人2 的信

13、息集不能作為子博 弈的初始結(jié), 否則將導(dǎo)致3的信 息被分割。 3.3.2 子 博 弈 完 美 (精練)動(dòng) 態(tài) 博 弈 定義 展開(kāi)式博弈的略 組s*=(s1*,si*,sn*) 是一個(gè) 子博弈完美(精練)Nash 均衡, 如果滿(mǎn) 足:(1) 它 是原博弈的Nash 均衡;(2) 它在每一 個(gè)子博弈上 給出Nash 均衡。 混合策略的子博弈完美Nash 均衡可類(lèi)似定 義。 簡(jiǎn)單地說(shuō): 子博弈完美Nash 均衡要 求均衡策略 的行為規(guī)則在每一個(gè)信息集 上都是最優(yōu)的(包括均衡路徑和非均衡路 徑)。 定 義 展開(kāi)型博弈的一個(gè)策略組合稱(chēng)為子 博弈 完美Nash 均衡，如果對(duì)于該博弈均衡，如果對(duì)于該博弈 的

14、每一個(gè)子 博弈，該策略組合都是 Nash 均衡。 例 澤爾騰 (Selten) 1 2 (2,2) (3,1) (0,0) U D L R L R U 2,2 2,2 D 3,1 0,0 該博弈有兩個(gè)Nash 均衡： （U，R）和（D，L) 但Nash 均衡(U,R) 從動(dòng)態(tài)博弈的觀(guān)點(diǎn)來(lái)看是不合 理的,因?yàn)樗蕾?lài)于參與人2取R這一“空頭威 脅”。 3.3.3 逆向歸納法 逆向歸納法包括以幾個(gè)步驟: 從博弈樹(shù)的終點(diǎn)結(jié)出發(fā), 追蹤到緊接著它的前 面的結(jié); 在步驟的中到達(dá)的每一個(gè)基本結(jié)上,通過(guò)對(duì) 該決策結(jié)出發(fā)到達(dá)的每一個(gè)終點(diǎn)結(jié)上參與人 得到的得益求最佳行動(dòng); 在步驟中檢驗(yàn)過(guò)每一個(gè)基本決策結(jié)中 所引起

15、的所有非最優(yōu)枝刪去; ? 如達(dá)到樹(shù)根,則中止,否則回到(1) ? 對(duì)每一個(gè)參與人,將該參與人在每一個(gè)決 策 結(jié)上的最優(yōu)策略一起收集起來(lái)就構(gòu)成 了最佳 策略。 例用逆向歸納法求下列博弈的子博弈完美 Nash 均衡： 1 2 2 1 L R A B C D E F (2,0) (1,1) (0,1/2) (3,1) (2,2) h1 h1 h2 h2 解為(R,E),(B,D) 定理 在一個(gè)具有完美信息的有限博弈中,使用逆 向歸納法所選擇的策略組合總是Nash 均衡。 承諾行動(dòng)與子博弈完美均衡承諾行動(dòng)與子博弈完美均衡 例 法律的要脅訴訟(設(shè)原告為P, 被告為D) P D P (0,0) 不指控 指

16、控(提出要求) 拒絕 接受 起訴 放棄 (sc,s) (x -c-p,- x -d) (-c,0) 其中指控成本為c 如果決定指控,P 要求D支付s0 以“私了”,P 的 起訴成本為d,如 果P以概率 贏 得 x, 則xrD/2,若銀行 同意到期后再收回 ,連本帶利將得到2R(RD) 。 1 2 2 1 2 2 Y N Y N Y N Y N Y N Y N (r,r) (D,2r D) (2r D,D) (R,R) (2R D,D) (D,2R D) (R,R) Y:提取; N:不提 日期1為投資到期之前; 日期2為之后 3.4.2 討討 價(jià)價(jià) 還還 價(jià)價(jià) 博博 弈弈(Rubinstein,

17、1982) 假定兩個(gè)人分一塊蛋糕 ,參與人1先出價(jià),參與人2 可以 選擇接受或拒絕;如果1接受博弈結(jié)束,蛋糕蛋糕 按按1的方案 分配;如果1拒絕,1再出價(jià);如此直下去直 到一個(gè)參與 人的出價(jià)被另一個(gè)人接收為止。 這是一個(gè)無(wú)限期完美信息博弈，參與人 1在時(shí)期1，3， 5， ， 出價(jià),參與人2在時(shí)期2,4,6, 出價(jià)。 用x表示1的份額,1x表示2的份額,x1和(1x1) 分別 是是1出價(jià)時(shí)1和和2的份額,x2和和(1 x 2)分別表 示示2出價(jià) 時(shí)參與人1和參與人2的份額。 假定參與人1和參與人2的貼現(xiàn)因子分別為 1 和 2, 則如 果在時(shí)期t博弈結(jié)束,參與人1和參與人 2的支付貼現(xiàn)值分別是 u

18、1=1 xi 和u2=2(1xi) t-1 t-1 如果博弈是有限期的,可以使用逆向歸納法求解 子博弈完美Nash均衡(T為期限) 設(shè)T=2,參與人2出價(jià),如果他 提出x2=0,1只有接受,因?yàn)樗?巳無(wú)出價(jià)機(jī)會(huì),由于2在T=2 時(shí)得到1單位相當(dāng)于在t=1時(shí) 得到2單位,所以1在t=1時(shí) 出價(jià)1x12時(shí)2會(huì)接受, 這時(shí)子博弈完美Nash均衡的結(jié)果是(12,2), 設(shè)T=3,設(shè)1出價(jià)x=1,因?yàn)樵赥=2時(shí)的1單位等 于t=2時(shí)的1單位,如果2在t=2時(shí)出價(jià)x2=1, 1 2 1 2 x1 A R,出x2 A R,出x3 (x1,1x1) (1x2,2(1x2) 參與人1會(huì)接受,參與人2在t=2時(shí)的

19、11單位相 當(dāng)于t=1時(shí)的2(11)單位,如果參與人1在 t=1時(shí)出價(jià)1x1=2(11),參與人2會(huì)接受, 因此,子博弈完美的唯一結(jié)果為: x=12(11) 類(lèi)似地: T=4時(shí)的子博弈完美Nash均衡的結(jié)果是: x=12(11(12) T=5時(shí)的子博弈完美的結(jié)果是: x=12(11(12(11) 當(dāng) 1=2=0時(shí),x=1,當(dāng)2=0時(shí)仍為x=1, 但當(dāng)1=0,20時(shí)結(jié)果為x=12,如果 1=2=1(即雙方都有無(wú)限的耐心)那么 當(dāng)T=1,3,5,時(shí)結(jié)果為x=1; 當(dāng)T=2,4,6,時(shí)結(jié)果為x=0(后動(dòng)優(yōu)勢(shì)) 定定 理理 (Rubinstein,1982), 在無(wú)限期討價(jià)還價(jià)博弈在無(wú)限期討價(jià)還價(jià)博弈

20、 中 中, 唯一的子博弈完美唯一的子博弈完美Nash均衡的結(jié)果是均衡的結(jié)果是: x*=(1 2)/(1 12) ( 如果1=2=,x*=1/(1+) 無(wú)限期討價(jià)還價(jià)的子博弈完美Nash均衡的結(jié)果決定 于參與人的貼現(xiàn)因子(耐心程度) 證明:T=+,博弈無(wú)最后階段,但參與人1出價(jià)的任何一 個(gè)階段開(kāi)始的子博弈等價(jià)于從 t=1開(kāi)始的整個(gè)博弈,我 們可以應(yīng)用有限階段逆向歸納法尋找子博弈完美均 衡. 假定t3,1出價(jià),1能得到的最大份額是M1,對(duì)1而言t期的 M1等價(jià)于t1期的1M,故2知道在t-1期的任何 x21M的出價(jià)將被1所接受,因此2出價(jià)x2=1M,自得1 1M;又對(duì)2而言t1期的11M等價(jià)于t2

21、期的 2(11M),故1可在t2期出價(jià)x1=12(11M), 因?yàn)閺膖2期能得到的最大份額一定與從 t期開(kāi)始的 博弈完全相同,故我們有: x1=M=12(11M) 解得 M=(12)/112),且結(jié)果是唯的. 3.6 動(dòng)態(tài)博弈分析的問(wèn)題和擴(kuò)展 3.6.1 逆推歸納法的問(wèn)題 例 1 2 3 n A A A A D D D D (1,1, 1) (1/2,1/2,1/2) (1/3,1/3,1/3) (1/n,1/n,1/n) (2,2, 2) 如果參與人的數(shù)目n比較小,才能預(yù)測(cè)到最后“共同富裕” 的 結(jié) 果(2,2,2)；當(dāng)n相當(dāng)大時(shí),情況就會(huì)發(fā)生變化: 設(shè)每個(gè)參與人取A的概率為0.9,n=20

22、,則0.9 0.314,較小的 概率可能動(dòng)搖1取A的決心。 19 例 例 1 2 1 2 1 A1 A2 A3 A4 A5 D1 D2 D3 D4 D5 (1,0) (0,1) (3,0) (2,4) (6,3) (5,5) 這是一個(gè)兩人輪流行動(dòng)的博弈,如果使用后退歸納 法,則解宣布在每一個(gè)決策結(jié)上行動(dòng)的參與人應(yīng)采 取行動(dòng)Di,(i=15)。這個(gè)解是否令人信服? 例 從子博弈完美是由后退歸納法引出的這一 事實(shí)，可知子博弈完美均衡其實(shí)后退歸納 解 的推廣。由于子博弈完美的范圍更寬廣，因 此引起爭(zhēng)議的內(nèi)容更多一些。如下博弈： 1 2 3 1 1 L R L R F G F G F G （6,0,6) (8,6,8) (0,0,0) (7,10,7) (7,10,7) (0,0,0) 最后階段1與是 否能夠“協(xié)調(diào)”成 功 對(duì)2的策略有影響 逆推歸納法更大的問(wèn)題是對(duì)參與人的理性要求 太高,不僅要求所有的博弈方都有高度的理性, 不允許犯如何錯(cuò)誤,而且要求所有的博弈方相 互了解和相信其他參與人的理性,對(duì)理性有相 同的理解 。 例 犯錯(cuò)誤的可能: 1 1 L R M N S T 2 (2,0) (0,3) 該博弈的子博弈完美 Nash均衡是(L,T); N. 但如果1“ 犯錯(cuò)誤” 而選R,將會(huì)如何? 3.6.2 顫抖手均衡和順推歸納法 一 顫 抖手均衡 例 下 列