博弈論(第七講)

1、第七第七講 混合策略納什均衡第第7講講 混合策略納什均衡混合策略納什均衡：引例：引例納什均衡何在？納什均衡何在？第第7講講 混合策略納什均衡混合策略納什均衡基本概念基本概念混合策略納什均衡的定義混合策略納什均衡的定義混合策略納什均衡的解法混合策略納什均衡的解法混合策略納什均衡舉例混合策略納什均衡舉例純沖突與防范行為博弈純沖突與防范行為博弈7.1 基本概念（上）在隨機(jī)試驗(yàn)中，可能出現(xiàn)也可能不出現(xiàn)，而在大量重復(fù)試驗(yàn)中具有某種規(guī)律性的事件叫做隨機(jī)事件，簡稱事件事件。 概率概率：事件的概率就是這個(gè)事件在無限次試驗(yàn)中發(fā)生的頻率。 當(dāng)兩個(gè)事件獨(dú)立時(shí)，兩個(gè)事件共同發(fā)生的概率就是事件單獨(dú)發(fā)生的概率的乘積。（舉

2、例） 隨機(jī)變量隨機(jī)變量：表示隨機(jī)現(xiàn)象（在一定條件下，并不總是出現(xiàn)相同結(jié)果的現(xiàn)象稱為隨機(jī)現(xiàn)象）各種結(jié)果的變量。 隨機(jī)變量的期望值隨機(jī)變量的期望值是隨機(jī)變量可能實(shí)現(xiàn)值的加權(quán)。（舉例） 7.1 基本概念（中）7.1 基本概念（下）120當(dāng)效用僅包含一個(gè)人如何對不同選擇進(jìn)行排列這一信息時(shí)，這種效用是有序的，但這種效用自身的數(shù)值是沒有意義的，這種效用叫做序數(shù)效用序數(shù)效用。當(dāng)面臨不確定因素時(shí)，效用等級開始起作用，而不僅僅是效用所暗含的結(jié)果排序。此時(shí)，效用不僅暗示著排序，也包含了偏好的強(qiáng)烈程度。當(dāng)效用的相應(yīng)等級包含信息時(shí)，這種效用稱為基數(shù)效用基數(shù)效用。 將“街道”和“花園”稱為兩個(gè)參與者的純策略。每個(gè)參與者

3、有使他的純策略隨機(jī)化的選擇，稱為混合策略。 在該博弈中，混合策略是0,1區(qū)間上的一個(gè)實(shí)數(shù)，這個(gè)數(shù)值就是選擇街道的概率。 用p表示警察去街道巡邏的概率，（1-p）就是警察去公園巡邏的概率。 用d表示毒販去街道交易的概率，（1-d）就是毒販去公園交易的概率。在策略組合(p,d)下，警察的支付為。 在策略組合(p,d)下，毒販的支付為：警察的純策略選擇“街道”，相當(dāng)于p=1，純策略選擇“公園”，相當(dāng)于p=0。 VPO(1,d)=60-60-50d+130d=80d VPO(0,d)=60-50d很顯然，當(dāng)d6/13時(shí)，選擇p=0優(yōu)于選擇p=1。p=0不僅優(yōu)于p=1，而且優(yōu)于p為其他任何值的選擇：當(dāng)d

4、VPO(1,d)因?yàn)閂PO(p,d)是VPO(1,d)和VPO(0,d)的加權(quán)平均數(shù)， 只要VPO(0,d)大于VPO(1,d)，VPO(0,d)就大于VPO(1,d)與VPO(0,d)的加權(quán)平均數(shù)?？傊?，當(dāng)d6/13時(shí)，p=1是警察的最佳選擇。 當(dāng)d=6/13時(shí)，對于警察而言，選擇去街道和去公園所得到的期望效用是一樣的。進(jìn)一步講，無論p為何值，期望效用都一樣。 【混合策略納什均衡的正式定義】7.3 混合策略納什均衡的解法混合策略納什均衡的解法 在毒品交易博弈的納什均衡中，毒販在街道的概率為6/13，在公園的概率為7/13。毒販的這種隨機(jī)化是比較合理，因?yàn)檫@將使警察無從下手。警察在街道的概率為

5、5/13，在公園的概率為8/13。警察的這種隨機(jī)化也是比較合理，因?yàn)檫@將使毒販無從下手。 當(dāng)警察在街道的概率為5/13時(shí)，毒販選擇街道的期望收益為(5/13)*20+(8/13)*90=820/13；毒販選擇公園的期望收益也為(5/13)*100+(8/13)*40=820/13。當(dāng)對面臨的選擇漠不關(guān)心時(shí)，隨機(jī)化一個(gè)選擇集合無疑是一個(gè)最佳選擇。 因此，毒販選擇在街道的概率為6/13，是其最佳選擇，因?yàn)樵谶@種情況下，警察選擇街道和公園的預(yù)期收益也是一樣的。 7.3 混合策略納什均衡的解法混合策略納什均衡的解法 如果使純策略隨機(jī)化是最佳選擇，那么參與者從任意純策略中獲得的期望收益相同。 如果毒販隨

6、機(jī)化其策略，那么警察必須選擇混合策略才能使毒販做出任意選擇的機(jī)會均等。 具體而言，警察的均衡策略是使毒販從其兩個(gè)純策略中獲得相等預(yù)期收益的p值： p*20+(1-p)*90=p*100+(1-p)*40推出p=5/13毒販的均衡策略是使警察從其兩個(gè)純策略中獲得相等預(yù)期收益的d值： d*80+(1-d)*0=d*10+(1-d)*60推出d=6/137.3 混合策略納什均衡的解法混合策略納什均衡的解法 這種求解方法的核心就是：找到一種策略，使得其他參與人認(rèn)為自己無論選擇哪種純策略，預(yù)期收益都一樣。 如果一個(gè)參與者有一個(gè)嚴(yán)格劣勢（純）策略，那么此策略如果一個(gè)參與者有一個(gè)嚴(yán)格劣勢（純）策略，那么此策

7、略在納什均衡混合策略中被賦予的概率值為在納什均衡混合策略中被賦予的概率值為0 0。 為了試圖解決混合策略納什均衡問題，我們需要剔除所有的嚴(yán)格劣勢策略。剔除后的博弈中的混合策略納什均衡集合與最原始的的博弈相同。如果一個(gè)純策略無法在重復(fù)剔除嚴(yán)格劣勢策略后繼續(xù)使用，混合策略納什均衡賦予其的概率為0。 7.3 混合策略納什均衡的解法混合策略納什均衡的解法 【小練習(xí)】【小練習(xí)】 求解該博弈的混合策略納什均衡。 7.4 混合策略納什均衡舉例混合策略納什均衡舉例7.4.1 混合策略納什均衡舉例阿維讓切斯防線7.4 混合策略納什均衡舉例混合策略納什均衡舉例7.4.1 混合策略納什均衡舉例阿維讓切斯防線7.4

8、混合策略納什均衡舉例混合策略納什均衡舉例7.4.1 混合策略納什均衡舉例阿維讓切斯防線 用r表示Bradley加固防線的的概率，(1-r)表示其向東進(jìn)軍的概率。用a表示Kluge攻擊的概率，(1-a)表示其撤退的概率。 如果Kluge是隨機(jī)化選擇，那么他從每個(gè)純策略中得到的預(yù)期支付是一樣的，有 r*0+(1-r)*5=r*3+(1-r)*2 解得r=1/2如果Bradley是隨機(jī)化選擇，那么他從每個(gè)純策略中得到的預(yù)期支付是一樣的，有 a*3+(1-a)*2=a*0+(1-a)*4 解得a=2/5可得，該博弈的混合策略納什均衡為(1/2,2/5)。7.4 混合策略納什均衡舉例混合策略納什均衡舉例

9、7.4.2 混合策略納什均衡舉例市場進(jìn)入 在分析其混合策略納什均衡之前，先確定這個(gè)博弈是否可以被簡化，及檢查是否存在嚴(yán)格劣勢策略。 對于公司1而言，無論有幾個(gè)公司進(jìn)入，他都會進(jìn)入，他的利潤不會低于150，其進(jìn)入成本只有100，因此，不進(jìn)入是其嚴(yán)格劣勢策略，予以剔除。 對于公司4而言，在公司1一定進(jìn)入的情況下，其利潤一定低于進(jìn)入成本，400d,bc。 該博弈有n個(gè)純策略納什均衡：任一個(gè)人提供幫助時(shí)，其他人置身事外。 在混合策略中推導(dǎo)出一個(gè)均衡，可以發(fā)現(xiàn)一個(gè)更為對策的解決方案。7.4 混合策略納什均衡舉例混合策略納什均衡舉例7.4.6 混合策略納什均衡舉例旁觀者效應(yīng)假設(shè)每個(gè)人都以p的概率去幫助，這

10、一對稱的均衡在在概率p的情況下實(shí)現(xiàn)，記為p*，即在其他(n-1)個(gè)人以概率p*去幫助時(shí)，那么對其中任意一個(gè)人而言，以概率p*提供幫助的策略最優(yōu)。換言之，如果(n-1)中的任意一個(gè)人以概率p*提供幫助，那么另一個(gè)人選擇幫助與置身事外的期望支付相同。倘若其他(n-1)個(gè)人以概率p提供幫助，一名參與者提供幫助的期望支付為： 其中，ad,bc。 這名參與者置身事外的期望支付為：7.4 混合策略納什均衡舉例混合策略納什均衡舉例7.4.6 混合策略納什均衡舉例旁觀者效應(yīng)這名參與者提供幫助與置身事外的預(yù)期支付相等，即 為了分析這個(gè)等式的性質(zhì)，假定a=4,b=3,c=2,d=1，表達(dá)式變?yōu)?.4 混合策略納什

11、均衡舉例混合策略納什均衡舉例7.4.6 混合策略納什均衡舉例旁觀者效應(yīng)有一個(gè)人提供幫助的概率隨旁觀者人有一個(gè)人提供幫助的概率隨旁觀者人數(shù)的變化情況數(shù)的變化情況至少有一個(gè)人提供幫助的概率隨旁至少有一個(gè)人提供幫助的概率隨旁觀者人數(shù)的變化情況觀者人數(shù)的變化情況7.5 純純沖突與防范行為博弈沖突與防范行為博弈 極極大極小策略即大極小策略即用來使參與者達(dá)到最用來使參與者達(dá)到最優(yōu)狀態(tài)的策略，即會優(yōu)狀態(tài)的策略，即會設(shè)想到其他參與者會設(shè)想到其他參與者會通過選擇策略來使參通過選擇策略來使參與者的支付最小。與者的支付最小。7.5 純純沖突與防范行為博弈沖突與防范行為博弈 用VH(pH,sM）表示福爾摩斯的期望支付

12、，如果他選擇混合策略pH（去多佛爾的概率）,則用sM表示莫瑞特的純策略。 福爾摩斯的極大極小策略可以解決以下問題：在已知pH的情況下，當(dāng)sM被選擇來使VH(pH,sM）最小化時(shí)，用pH來使VH(pH,sM）最大化。 如果用b(pH)表示使VH(pH,sM）最小化的sM的值，那么福爾摩斯的問題可表述為怎么確定pH的值使VH(pH, b(pH) ）最大化。7.5 純純沖突與防范行為博弈沖突與防范行為博弈 當(dāng)莫瑞特選擇去多佛爾時(shí)，福爾摩斯的期望支付為： VH(pH,多佛爾）=pH*20+(1-pH)*70=70-50pH 當(dāng)莫瑞特選擇去坎特伯雷時(shí)，福爾摩斯的期望支付為： VH(pH,坎特伯雷）=pH*90+(1-pH)*10=10+80pH7.5 純純沖突與防范行為博弈沖突與防范行為博弈 不管pH值是多少，莫瑞特總可以選擇相應(yīng)的策略使得福爾摩斯的支付最小。因此，圖中加粗的線表示福爾摩斯的支付。 很明顯，福爾摩斯的支付有一個(gè)極大值點(diǎn)，即兩條線的交點(diǎn)。 70-50pH=10+80pH pH=6/13 pH=6/13是使福爾摩斯期望支付最大化的混合策略，即他的極大極小策略。如果一名參與者知道你會做出的選擇，那么你做出隨機(jī)化選擇將更好7.5 純純沖突與防范行