重復(fù)博弈完全且非完美信息動(dòng)態(tài)博弈

1、2009-03-16張醒洲，大連1重復(fù)博弈完全且非完美信息動(dòng)態(tài)博弈2009-03-16張醒洲，大連2第3章和第4章要點(diǎn)博弈類型舉例解的概念簡(jiǎn)單的完全且完美信息動(dòng)態(tài)博弈Stackelberg (1934) 雙寡頭壟斷模型魯賓斯坦 (1982) 討價(jià)還價(jià)模型Backwards Induction Outcome (BIO)后向歸納結(jié)果2人兩階段重復(fù)博弈 (“同時(shí)行動(dòng)” 意味著 “不完美信息”)Lazear&Rosen Tournaments (1981 ) 工作競(jìng)賽模型Subgame Perfect Outcome (SPO)子博弈完美結(jié)果動(dòng)態(tài)博弈主題: 可信威脅與承諾會(huì)影響現(xiàn)在的行為下一次博弈開(kāi)

2、始前的所有博弈的結(jié)果都能被觀察到的重復(fù)博弈Subgame-perfect Nash equilibrium子博弈完美NE2009-03-16張醒洲，大連3完全信息動(dòng)態(tài)博弈表述Normal-form / Strategic-form 標(biāo)準(zhǔn)式/策略式Extensive-form 擴(kuò)展式解的概念Nash Equilibrium (NE)Nash均衡Subgame-perfect Nash equilibrium (SPNE)子博弈完美Nash均衡Central Issue中心問(wèn)題 credibility threats or promise (self-enforcement)可信性威脅或承諾The

3、me 主題思想一個(gè)完全信息動(dòng)態(tài)博弈可能會(huì)有很多個(gè)納什均衡，但是有些均衡包含了不可置信的威脅和承諾。子博弈完美納什均衡就是通過(guò)了可信任檢測(cè)的均衡。第3章和第4章要點(diǎn)2009-03-16張醒洲，大連4重復(fù)博弈要點(diǎn)當(dāng)參與人重復(fù)進(jìn)行策略互動(dòng)時(shí)，某個(gè)參與人對(duì)于未來(lái)行動(dòng)的威脅或承諾是否影響其他參與人當(dāng)前的行動(dòng)？直觀 大部分直觀的結(jié)論是由兩階段的例子給出的 一些觀點(diǎn)需要討論無(wú)限次的情況概念：子博弈完美納什均衡我們還將定義重復(fù)博弈中子博弈完美納什均衡的概念 這一定義在重復(fù)博弈的條件下表述比較容易理解，而在2.4.B. 節(jié)分析一般完全信息動(dòng)態(tài)博弈中則要復(fù)雜一些；我們?cè)诒竟?jié)先作簡(jiǎn)要介紹，以便后面的展開(kāi)。2009-

4、03-16張醒洲，大連5兩階段重復(fù)博弈兩階段囚徒困境兩階段博弈的階段博弈有多個(gè)納什均衡預(yù)測(cè)第二階段的行動(dòng)重復(fù)博弈的子博弈完美結(jié)果2009-03-16張醒洲，大連6兩階段囚徒困境考慮囚徒困境給定如圖2.3.1的標(biāo)準(zhǔn)式 納什均衡為(L1 , L2) 同時(shí)行動(dòng)博弈 參與人 2 參與人 1L2R2L11, 1 5, 0R10, 5 4, 4圖 2.3.1讓兩個(gè)參與人進(jìn)行兩次囚徒困境博弈，第二次博弈開(kāi)始之前可以觀察到第一次博弈的結(jié)果，并假設(shè)整個(gè)過(guò)程博弈的總收益等于兩階段博弈收益的簡(jiǎn)單相加 (即不考慮貼現(xiàn)因素) 。2009-03-16張醒洲，大連7“2 2 2” 博弈和子博弈完美結(jié)果兩階段囚徒困境博弈是“

5、22 兩人同時(shí)行動(dòng)”博弈的一個(gè)特殊例子。在這個(gè)博弈中，我們?cè)谏弦还?jié)利用后向歸納法的思路分析了“子博弈完美結(jié)果”，具體見(jiàn)2.2.1。子博弈完美結(jié)果 如果參與人1和2預(yù)測(cè)到參與人3和4在第二階段的行動(dòng)將由(a3*(a1,a2)，a4*(a1,a2)給出，則參與人1和2在第一階段的問(wèn)題就可以用以下的同時(shí)行動(dòng)博弈表示： 1. 參與人1和2同時(shí)從各自的可行集A1和A2中選擇a1和a2； 2. 收益情況為ui(a1,a2,a3*(a1,a2),a4*(a1,a2)，i=1,2； 假定（a1*,a2*）為以上同時(shí)行動(dòng)博弈唯一的納什均衡，我們稱 (a1*,a2*,a3*(a1*,a2*),a4*(a1*,a2

6、*)為這一兩階段博弈的子博弈完美結(jié)果。2009-03-16張醒洲，大連8兩階段囚徒困境得到 a3*(a1,a2)，a4*(a1,a2)根據(jù)第一階段的行動(dòng)a1和 a2 ，預(yù)測(cè)第二階段參與人的反應(yīng)；請(qǐng)注意，在囚徒困境博弈中存在唯一的納什均衡，因此參與人的反應(yīng)獨(dú)立于其在第一階段的行動(dòng)。計(jì)算 ui(a1,a2,a3*(a1,a2),a4*(a1,a2)，i=1,2支付等于兩個(gè)階段博弈支付的簡(jiǎn)單和. 2009-03-16張醒洲，大連9兩階段囚徒困境第二階段博弈的結(jié)果為納什均衡 (L1 , L2) ，兩人收益為(1, 1)；參與 人在兩階段囚徒困境博弈中第一階 段的交互行動(dòng)如圖2.3.2所示；這個(gè)一次性博

7、弈有唯一的納什均衡 (L1 ,L2) 。 參與人 2 參與人 1L2R2L12, 2 6, 1R11, 6 5, 5圖 2.3.2兩階段囚徒困境唯一的子博弈完美結(jié)果就是第一階段的 (L1,L2) 和第二階段的 (L1,L2)。在子博弈完美結(jié)果中，任意階段都不能達(dá)成相互合作 (R1,R2)。2009-03-16張醒洲，大連10有限重復(fù)博弈:重復(fù)獨(dú)立 令 G = A1, .,An; u1, ., un 表示一個(gè)完全信息博弈，其中參與人1 到n同時(shí)從各自的行動(dòng)空間A1到An中分別選擇行動(dòng)a1到an ，得到的 收益分別為u1(a1, ., an) , ., un(a1, ., an),我們稱博弈G為重

8、復(fù)博弈 中的階段博弈。定義1 對(duì)給定的階段博弈G，令 G(T)表示G重復(fù)進(jìn)行T次的有限博弈，并且在下一次博弈開(kāi)始前，所有以前博弈的進(jìn)行都可以被觀察到。G(T)的收益為T(mén)次階段博弈收益的簡(jiǎn)單相加。定理1 如果階段博弈G有唯一的納什均衡，則對(duì)任意有限的T，重復(fù)博弈G(T)有唯一的子博弈完美結(jié)果：即G的納什均衡結(jié)果在每一階段重復(fù)進(jìn)行。2009-03-16張醒洲，大連11兩階段重復(fù)博弈:階段博弈有多個(gè)納什均衡設(shè)圖2.2.3表示的階段博弈重復(fù)進(jìn)行兩次，并在第二階段開(kāi)始前可以觀察到第一階段的結(jié)果。我們可以證明在這一重復(fù)博弈中存在一個(gè)子博弈完美結(jié)果，其中第一階段的策略組合為 (M1,M2)。 參與人 2參與

9、人 1L2M2R2L11, 15, 0 0, 0M10, 54, 4 0, 0R10, 00, 03, 3圖 2.3.3圖2.2.3中表示的博弈有兩個(gè)納什均衡 (L1,L2),(R1,R2)2009-03-16張醒洲，大連12兩階段重復(fù)博弈:階段博弈有多個(gè)納什均衡由于這個(gè)階段博弈有不止一個(gè)納什均衡，因此參與人可能會(huì)預(yù)測(cè)： 根據(jù)第一階段的不同結(jié)果，在第二階段的博弈中將會(huì)出現(xiàn)不同的納什均衡。關(guān)鍵問(wèn)題是：預(yù)測(cè)對(duì)第一階段的行動(dòng)a1 和a2 的反應(yīng)。 參與人 2 參與人 1L2M2R2L11, 15, 0 0, 0M10, 54, 4 0, 0R10, 00, 03, 3第一階段第二階段收益(L1, L

10、2)(1,1)+(?,?)(R1, R2)(3,3)+(?,?)(M1, M2)(4,4)+(?,?)(M1, L2)(0,5)+(?,?)(L1, M2)(5,0)+(?,?)others(0,0)+(?,?)圖 2.3.3第二階段的結(jié)果 ?2009-03-16張醒洲，大連13信 號(hào)假設(shè)：如果參與人預(yù)測(cè)到第一階段的結(jié)果是(M1,M2)，第二階段的結(jié)果將會(huì)是 (R1,R2) ；如果第一階段出現(xiàn)其他8個(gè)結(jié)果中任何一個(gè)，第二階段的結(jié)果就會(huì)是 (L1,L2)。那么，這個(gè)兩階段博弈就如同圖2.3.4的一次性博弈。 參與人2 參與人 1L2M2R2L12, 26, 1 1, 1M11, 67, 7 1,

11、 1R11, 11, 14, 4圖 2.3.4在圖2.3.4所示的博弈中有3個(gè)純策略納什均衡: (L1,L2), (M1,M2) 和(R1,R2)。和圖2.3.2中一樣,這個(gè)一次性博弈中的納什均衡對(duì)應(yīng)著重復(fù)博弈的子博弈完美結(jié)果。2009-03-16張醒洲，大連14兩階段重復(fù)博弈的子博弈完美結(jié)果標(biāo)記令 (w, x), (y, z)表示重復(fù)博弈的一個(gè)結(jié)果第一階段和第二階段 的行動(dòng)分別為 (w, x) 和(y, z) 。圖2.3.4中的納什均衡 (L1,L2) 對(duì)應(yīng)著重復(fù)博弈的子博弈完美結(jié)果 (L1,L2), (L1,L2) ，因?yàn)槌谝浑A段的結(jié)果是(M1,M2) 外，其他任何情 況發(fā)生時(shí)，第二階段

12、的結(jié)果都是 (L1,L2)。類似地，圖2.3.4 中的納什均衡 (R1,R2) 對(duì)應(yīng)了重復(fù)博弈的子博弈完美 結(jié)果 (R1,R2), (L1,L2) 。重復(fù)博弈的這兩個(gè)子博弈完美結(jié)果都簡(jiǎn)單地 由兩個(gè)階段博弈的納什均衡解相串而成。第一階段的非合作傾向在第二階段遭到報(bào)復(fù)或懲罰!2009-03-16張醒洲，大連15兩階段重復(fù)博弈的子博弈完美結(jié)果圖2.3.4 里的第三個(gè)納什均衡結(jié)果與前兩者存在質(zhì)的差別： 圖2.3.4中的 (M1,M2)對(duì)應(yīng)的重復(fù)博弈子博弈完美結(jié)果為 (M1,M2),(R1,R2)，因?yàn)閷?duì)(M1,M2)之后第二階段結(jié)果預(yù)期是(R1,R2) , 亦即正如我們前面講過(guò)的，在重復(fù)博弈的子博弈完

13、美結(jié)果中，合作 可以在第一階段達(dá)成。下面是更為一般的情況如果 G = A1, .,An; u1, ., un 是一個(gè)有多個(gè)納什均衡的完全信息靜態(tài) 博弈，則重復(fù)博弈G(T)可以存在子博弈完美結(jié)果，其中對(duì)每一 t 0, 企業(yè)的收益是 y-w, 工人的收益是 w-e。2009-03-16張醒洲，大連24工資效率: 一階段偷懶模型工人的努力程度企業(yè)無(wú)法觀測(cè)，但是 企業(yè)和工人都可以觀測(cè)到工人的產(chǎn)出 水平。 產(chǎn)出可能高也可能低，為簡(jiǎn)單起見(jiàn)， 我們認(rèn)為低水平的產(chǎn)出為0，高水平 的產(chǎn)出為y 0假設(shè)如果工人努力工作則肯定可 以得到高產(chǎn)出；但是如果工人偷懶則以p 的概率 得到高產(chǎn)出，1 - p 的概率的到低產(chǎn)出；

14、從而，在這個(gè)模型中，低產(chǎn)出是偷懶 無(wú)可辯駁的證據(jù)。顯然地，企業(yè)不能強(qiáng) 制工人努力工作- 偷懶總是存在的。為了聘請(qǐng)工人，企業(yè) 只需要支付工人w0-支付更多的工資是沒(méi)有意義的，因?yàn)橥祽锌偸谴嬖凇?009-03-16張醒洲，大連25工資效率: 社會(huì)效率如果企業(yè)以工資 w 雇傭工人 ，則參與人的收益為如果工人努力工作并帶來(lái)高產(chǎn)出，則 企業(yè)收益為：y - w ，工人收益為：w e；如果工人偷懶，則e = 0 ； 如果出現(xiàn)低產(chǎn)出，則y = 0；我們假定y - e w0 py 這就使得 工人付出努力工作是有社會(huì)效率的工人自我雇傭要優(yōu)于受雇于企業(yè)并偷懶 同樣意味著 企業(yè)不會(huì)事先預(yù)付工資，因?yàn)樽畹凸べY將超出期望

15、產(chǎn)出! 2009-03-16張醒洲，大連26工資效率: 階段博弈這一階段的子博弈完美結(jié)果是使人失望的：因?yàn)槠髽I(yè)先付給工人工資w，工人沒(méi)有動(dòng)機(jī)去努力工作，于是企業(yè)將會(huì)開(kāi)出w w0 ，且工人會(huì)選擇自我雇傭。在無(wú)限重復(fù)博弈中，企業(yè)給工人高于wc 的工資水平w， 并且威脅一旦出現(xiàn)低產(chǎn)出，就將工人開(kāi)除。下面我們將證明在某些取值范圍內(nèi)，企業(yè)給出較高的工資并借此激勵(lì)工人努力工作是值得的。2009-03-16張醒洲，大連27 考慮無(wú)限重復(fù)博弈中下面的戰(zhàn)略，其中包含了將在以后決定的 。如果所有前面的工資開(kāi)價(jià)都是 ，所有的開(kāi)價(jià)都被接受了，并且所有前期的產(chǎn)出都是高的，我們就稱博弈的過(guò)程是“高工資、高產(chǎn)出”。 企業(yè)的

16、策略為第一階段開(kāi)出工資水平 ，并且在其后的每一階段，如果博弈的過(guò)程是高工資、高產(chǎn)出，則繼續(xù)開(kāi)出工資水平 ；但其他情況下開(kāi)出 。 工人的策略為如果 ，則接受企業(yè)的工資（否則，選擇自我雇傭），并且如果博弈的過(guò)程（包括本階段的工資）是高工資、高產(chǎn)出，則努力工作（否則偷懶）。請(qǐng)注意，如果 ，但 ，則工人將接受企業(yè)的工資但選擇偷懶。效率工資: 無(wú)限重復(fù)博弈2009-03-16張醒洲，大連28子博弈一個(gè)子博弈是全部博弈的一部分，當(dāng)全部博弈進(jìn)行到任何 一個(gè)階段，到此為止的進(jìn)行過(guò)程已成為參與各方的共同知 識(shí)，而其后尚未開(kāi)始進(jìn)行的部分就是一個(gè)子博弈。定義 在有限重復(fù)博弈G(T) 中,由第t + 1階段開(kāi)始的一個(gè)

17、子博弈為G 進(jìn)行T t次的重復(fù)博弈，表示為G(T- t)。由第t + 1階段開(kāi)始有許多子博弈；到第 t 階段為止的每一可能的進(jìn) 行過(guò)程之后都是不同的子博弈。 在無(wú)限重復(fù)博弈G(,)中,由第t + 1階段開(kāi)始的每個(gè)子博弈都等同于初始博弈G(,)與在有限情況下相似，博弈G(,) 到第 t 階段為止有多少不同 的可能進(jìn)行過(guò)程，就有多少?gòu)膖 + 1階段開(kāi)始的子博弈。2009-03-16張醒洲，大連29子博弈請(qǐng)注意，重復(fù)博弈的第 t 階段本身（在有限情況下假 定 t 0 (2.3.7)2009-03-16張醒洲，大連36效率工資:子博弈完美納什均衡 前面我們已假定y- e wo (即對(duì)工人而言，選擇受雇于企業(yè)并努