第三講混合策略納什均衡ppt課件

1、第三講 混合戰(zhàn)略納什平衡 主講人：李美娟 引言有些博弈不存在納什平衡，或者納什平衡不獨(dú)一，如猜硬幣博弈，前述納什平衡分析就無(wú)法對(duì)博弈方的選擇和博弈結(jié)果作明確的預(yù)測(cè)。這部分對(duì)不存在納什平衡和存在多個(gè)納什平衡的博弈作一些討論?；旌蠎?zhàn)略的引進(jìn)一、撲克牌對(duì)色游戲-1， 11， -11， -1-1， 1紅黑乙甲紅黑不存在前面定義的納什平衡戰(zhàn)略組合。這類(lèi)博弈很多，引出混合戰(zhàn)略納什平衡概念?；旌蠎?zhàn)略的相關(guān)概念混合戰(zhàn)略是一種按照什么概率選擇這個(gè)純戰(zhàn)略、按照什么概率選擇那種純戰(zhàn)略的戰(zhàn)略選擇指示?；旌蠎?zhàn)略闡明：參與人可以按照一定的概率，隨機(jī)地從純戰(zhàn)略集合中選擇一種純戰(zhàn)略的實(shí)踐行動(dòng)。期望值：假定存在 個(gè)能夠的取值

2、，并且這些取值發(fā)生的概率分別為： ，那么期望值為： 小孩玩的游戲“石頭，剪子，布，也是一種博弈。但是，這個(gè)博弈有一種有趣的特征，即給定一方的任何選擇，另一方都有制勝對(duì)方的戰(zhàn)略，因此這個(gè)戰(zhàn)略不是最優(yōu)的。任何“純戰(zhàn)略都不是最優(yōu)的，純戰(zhàn)略是“石頭，剪子，布中的任何一個(gè)?；旌蠎?zhàn)略博弈石頭、剪刀、布0， 01， -1-1， 1-1， 11， -10， 01， -1-1， 10， 0石 頭剪 子布博弈方2石 頭剪 子布博弈方1 但是，我們知道，玩這個(gè)游戲總是以對(duì)方不易猜出的隨機(jī)方式出招。現(xiàn)實(shí)上，可以經(jīng)過(guò)數(shù)學(xué)證明，當(dāng)雙方都以每個(gè)戰(zhàn)略按1/3的概率出招時(shí)，達(dá)成一種雙方都不愿改動(dòng)這種概率分布的局面。這被稱(chēng)為“混

3、合戰(zhàn)略納什平衡，而這種以隨機(jī)方式選擇純戰(zhàn)略的博弈被稱(chēng)為“混合戰(zhàn)略博弈。 以混合戰(zhàn)略博弈我們來(lái)看下面幾個(gè)例子。 例子1 為什么普通人總是小錯(cuò)不斷，大錯(cuò)不犯；偷稅漏稅的普通是中小企業(yè)，大企業(yè)會(huì)老老實(shí)實(shí)地交稅？ 稅務(wù)部門(mén)不會(huì)對(duì)一切企業(yè)的交稅情況每一次都去檢查，由于這樣做的本錢(qián)太高，得不償失。所以，稅務(wù)部門(mén)總是隨機(jī)地對(duì)企業(yè)的交稅情況進(jìn)展檢查。 企業(yè)也是隨機(jī)地在交稅與偷漏稅之間進(jìn)展選擇。稅收部門(mén)與企業(yè)間進(jìn)展的是混合戰(zhàn)略博弈。由于假設(shè)企業(yè)總是交稅，稅務(wù)部門(mén)就最好不檢查；但給定不檢查，企業(yè)就會(huì)偷漏稅。所以，兩者只需在隨機(jī)地檢查與不檢查，企業(yè)隨機(jī)地在偷漏稅與交稅之間選擇，才會(huì)達(dá)成平衡。 對(duì)于大企業(yè)，因一旦偷稅

4、數(shù)額就宏大，所以，稅務(wù)部門(mén)在隨機(jī)檢查時(shí)放在大企業(yè)上的能夠性就大一些；而給定稅務(wù)部門(mén)檢查大企業(yè)的能夠性較大，大企業(yè)偷漏稅的行為就較少，否那么就容易被逮個(gè)正著。所以，偷漏稅較多的就是一些中小企業(yè)，大企業(yè)納稅的積極性較高。同樣的道理，在犯罪或?qū)﹀e(cuò)誤的監(jiān)視懲罰博弈中，也是混合博弈，人們能夠總是大錯(cuò)不犯小錯(cuò)不斷。 例子2 田忌賽馬新編 春秋戰(zhàn)國(guó)時(shí)期，齊威王常與旗下大將田忌賽馬。規(guī)那么是：每次賽三局，每一局齊威王與田忌各出一匹馬競(jìng)賽奔跑速度。每一局中的勝者贏(yíng)敗方一千斤銅。田忌有上、中、下三匹馬，而齊威王也有上、中、下三匹馬。每次競(jìng)賽，第一局田忌出上馬，齊威王也出上馬；第二局田忌出中馬，齊威王也出中馬；第三

5、局，田忌出下馬，齊威王也出下馬。齊威王的上馬比田忌的上馬好，齊威王的中馬也比田忌的中馬好，齊威王的下馬還是比田忌的下馬好。于是，每次競(jìng)賽的結(jié)果都是田忌連輸三局。 田忌的謀士孫臏了解了田忌的姿態(tài)后，就探聽(tīng)到這樣一個(gè)音訊：雖然齊威王的上、中、下三匹馬都要比田忌的對(duì)應(yīng)上、中、下三匹馬好，但碰巧的是田忌的上馬可勝齊威王的中馬，田忌的中馬可勝齊威王的下馬。于是，孫臏為田忌獻(xiàn)計(jì)：下一次競(jìng)賽中第一局時(shí)田忌出下馬對(duì)齊威王的上馬輸一局，第二局田忌出上馬對(duì)齊威王的中馬，第三局田忌出中馬對(duì)齊威王的下馬，這樣可連贏(yíng)兩局，最后凈勝一千斤銅。田忌依計(jì)而行，果真贏(yíng)回一千斤銅。 這個(gè)故事曾經(jīng)被很多人當(dāng)作博弈論的例子來(lái)演繹，但

6、實(shí)踐上這個(gè)故事與博弈論無(wú)關(guān)。博弈論會(huì)假定一切局中人都是理性的，不能假定一些局中人聰明而另一些局中人卻是傻子。當(dāng)田忌出下馬時(shí)，齊威王最好的選擇是出下馬而不是上馬。孫臏的計(jì)謀中假定齊威王是傻子，當(dāng)田忌出下、上、中馬時(shí)，他依然按上、中、下馬出，當(dāng)然要輸了?，F(xiàn)實(shí)上，當(dāng)田忌出下馬時(shí)，齊威王應(yīng)出下馬，但齊威王出下馬時(shí)，田忌不應(yīng)出下馬而是出中馬，但此時(shí)齊威王又應(yīng)出中馬而不是下馬了，。這樣，博弈不會(huì)有純戰(zhàn)略的平衡。 兩人只能玩混合戰(zhàn)略博弈，齊威王分別以1/6隨機(jī)的概率選擇出上、中、下馬的任一陳列，田忌也如此。由于齊威王存在絕對(duì)優(yōu)勢(shì)，他平均看來(lái)依然會(huì)贏(yíng)田忌一千斤銅。 混合戰(zhàn)略平衡純戰(zhàn)略與純戰(zhàn)略納什平衡純戰(zhàn)略：一

7、定會(huì)被選擇以100%的概率被選擇的戰(zhàn)略?；旌蠎?zhàn)略混合戰(zhàn)略：以一定的概率分布選擇某幾個(gè)行動(dòng)的戰(zhàn)略?；旌蠎?zhàn)略定義：在n人博弈的戰(zhàn)略式表述 中，假定參與人 有K個(gè)純戰(zhàn)略： ，那么，概率分布 稱(chēng)為 的一個(gè)混合戰(zhàn)略，這里 是 選擇 的概率，對(duì)于一切的 。 顯然，純戰(zhàn)略可以了解為混合戰(zhàn)略的特例，比如說(shuō)，純戰(zhàn)略 等價(jià)于混合戰(zhàn)略 ，即選擇純戰(zhàn)略 的概率為1，選擇任何其他純戰(zhàn)略的概率為0?；旌蠎?zhàn)略納什平衡：包含混合戰(zhàn)略的戰(zhàn)略組合，構(gòu)成納什平衡?；旌蠎?zhàn)略混合戰(zhàn)略平衡設(shè) 是n人戰(zhàn)略式博弈的一個(gè)混合戰(zhàn)略組合。假設(shè)對(duì)于一切的 ， 對(duì)于每一個(gè) 都成立，那么稱(chēng)混合戰(zhàn)略組合 是這個(gè)博弈的一個(gè)納什平衡。 期望支付 例：參與人1

8、的混合戰(zhàn)略：p,1-p) 參與人2的混合戰(zhàn)略：(q,1-q)參與人1的期望支付：假設(shè)參與人1選擇S11：假設(shè)參與人1選擇S12：EV1p,q)=參與人2的期望支付：EV2p,q)=u1，u2u3，u4u5，u6u7，u8參與人2S11 pS12 1-pS21S22參與人2q1-q混合戰(zhàn)略平衡 例：監(jiān)視博弈給定工人偷懶，老板的最優(yōu)選擇是監(jiān)視；給定老板監(jiān)視，工人的最優(yōu)選擇是不偷懶；給定工人不偷懶，老板的最優(yōu)選擇是不監(jiān)視；給定老板不監(jiān)視，工人的最優(yōu)選擇是偷懶；如此循環(huán)。1，-1-1，2-2，32，2老板監(jiān)視不監(jiān)視偷懶不偷懶工人混合戰(zhàn)略平衡監(jiān)視不監(jiān)視偷懶不偷懶工人老板 假定老板選擇混合戰(zhàn)略0.5，0.

9、5) 工人選擇“偷懶期望支付為 (-1)0.5+30.5=1 工人選擇“不偷懶期望支付為20.5+20.5=2 工人應(yīng)選擇“不偷懶 老板選擇“不監(jiān)視 工人選擇“偷懶0.50.5 假定老板選擇混合戰(zhàn)略0.2，0.8) 工人選擇“偷懶期望支付為(-1)0.2+30.8=2.2 工人選擇“不偷懶期望支付為20.2+20.8=2 工人應(yīng)選擇“偷懶 老板選擇“監(jiān)視 工人選擇“不偷懶1，-1-1，2-2，32，2混合戰(zhàn)略平衡 什么情況下到達(dá)納什平衡形狀？假定存在一個(gè)概率q，老板選擇混合戰(zhàn)略q，1-q工人選擇“偷懶期望收益為(-1)q+3(1-q)=3-4q工人選擇“不偷懶收益為2假設(shè)老板真的以概率q選擇監(jiān)

10、視，1-q選擇不監(jiān)視，那么意味著他不會(huì)一直反復(fù)地選擇某個(gè)純戰(zhàn)略，而他不反復(fù)選擇的條件必需是工人也不會(huì)反復(fù)地選擇純戰(zhàn)略。 因此，老板以概率q選擇監(jiān)視必然意味著在這種情況下工人沒(méi)有適宜的純戰(zhàn)略選擇。=老板的選擇必需使工人在兩個(gè)純戰(zhàn)略之間隨機(jī)選擇。工人什么情況下隨機(jī)選擇？混合戰(zhàn)略平衡當(dāng)工人選擇任何一個(gè)戰(zhàn)略的期望支付相等時(shí)，只能隨機(jī)選擇。于是，3-4q=2 ，即q*=1/4,1- q*=3/4。這樣，當(dāng)老板選擇1/4，3/4的混合戰(zhàn)略時(shí)，可以使工人在兩個(gè)純戰(zhàn)略之間無(wú)差別。 同理，假設(shè)工人選擇(p,1-p)，(p,1-p)成為其最優(yōu)混合戰(zhàn)略的條件是老板在選擇監(jiān)視與選擇不監(jiān)視之間無(wú)差別，即1p+(-1)(

11、1-p)=(-2)p+2(1-p)，即p*=1/2,1- p*=1/2。當(dāng)老板選擇1/4，3/4，工人選擇1/2，1/2時(shí)，剛好互為彼此的最優(yōu)反響，到達(dá)納什平衡形狀,稱(chēng)為混合戰(zhàn)略納什平衡?；旌蠎?zhàn)略平衡參與人1和參與人2的混合戰(zhàn)略組合 構(gòu)成平衡的必要條件：混合戰(zhàn)略平衡的求解方法方法1：支付最大化法 給定其他參與人的混合戰(zhàn)略，本人選擇行動(dòng)的概率分布要使本人期望支付最大化。q1-q1-pp工人的期望支付函數(shù)為(-1)pq+2(1-p)q+3p(1-q)+2(1-p)(1-q)=-4pq+p-2q+2最優(yōu)化一階條件為：-4q+1=0 q*=1/4給定工人的混合戰(zhàn)略為(p,1-p)，老板的混合戰(zhàn)略為(q

12、,1-q)支付最大化法求混合戰(zhàn)略納什平衡1，-1-1，2-2，32，2老板監(jiān)視不監(jiān)視偷懶不偷懶工人混合戰(zhàn)略平衡的求解方法方法2：支付等值法 本人選擇戰(zhàn)略概率分布使對(duì)方不會(huì)偏好于任何行動(dòng)，即選擇每一個(gè)戰(zhàn)略都會(huì)得到一樣的收益。例子例：博弈方1的混合戰(zhàn)略p,1-p) 博弈方2的混合戰(zhàn)略q,1-q博弈方1：由 可得 ：q=0.8博弈方2：由 可得 ：p=0.8 2， 35， 23， 11， 5CDAB博弈方2博弈方1得雙方的戰(zhàn)略及相應(yīng)得益：其中，博弈方1的期望得益為：博弈方2的期望得益為：策略期望得益博弈方1（0.8，0.2）2.6博弈方2（0.8，0.2）2.6多重平衡博弈和混合戰(zhàn)略一、夫妻之爭(zhēng)的混

13、合戰(zhàn)略納什平衡首先，該博弈有兩個(gè)納什平衡，本博弈的兩個(gè)博弈方不會(huì)害怕對(duì)方猜到本人的選擇，他們客觀(guān)上并不想隱藏本人的選擇。因此，該博弈中兩博弈方的決策思緒和原那么應(yīng)該與沒(méi)有納什平衡的嚴(yán)厲競(jìng)爭(zhēng)博弈有所不同。2， 10， 00， 01， 3時(shí) 裝足 球時(shí)裝足球丈 夫妻子夫妻之爭(zhēng)但顯然，雙方的偏好不同，妻子喜歡前一個(gè)，丈夫喜歡后一個(gè)。故在純戰(zhàn)略的范圍內(nèi)，該博弈也是無(wú)法對(duì)兩博弈方的選擇提出確定性建議，因此也需求思索博弈方采用混合戰(zhàn)略的能夠性。設(shè)p和1-p分別為妻子選擇時(shí)裝扮演和足球的概率；假設(shè)妻子不想讓丈夫利用本人的選擇傾向占上風(fēng)，那么本人的概率選擇應(yīng)使丈夫選擇兩種戰(zhàn)略的期望得益一樣：得：p=3/4設(shè)q

14、和1-q分別為丈夫選擇時(shí)裝扮演和足球的概率。同樣，假設(shè)丈夫不想讓妻子利用本人的選擇傾向占上風(fēng)，那么本人的概率選擇應(yīng)使妻子選擇兩種戰(zhàn)略的期望得益一樣：得：q=1/3夫妻之爭(zhēng)博弈的混合戰(zhàn)略納什平衡 戰(zhàn)略 得益妻子 0.75，0.25 0.67丈夫 1/3，2/3 0.75可見(jiàn)，這個(gè)結(jié)果明顯不如夫妻雙方能交流協(xié)商時(shí)，任何一方遷就另一方的得益好。這是由于缺乏溝通時(shí)能夠出現(xiàn)最差的結(jié)果呵斥的。也就是說(shuō)，假設(shè)不強(qiáng)行設(shè)定雙方不能交流串通的博弈規(guī)那么，雙方?jīng)Q策時(shí)沒(méi)有被客觀(guān)或人為的緣由隔分開(kāi)來(lái)，也沒(méi)有由于賭氣而采取不理性的態(tài)度，那么這種夫妻之間的決策問(wèn)題普通不應(yīng)該用上述博弈方式處理。二、制式問(wèn)題電器和電子設(shè)備往往

15、有不同的原理或相關(guān)技術(shù)規(guī)范，稱(chēng)之為不同的制式。假設(shè)消費(fèi)相關(guān)電器或電子設(shè)備的廠(chǎng)商采用一樣的制式，那么產(chǎn)品之間就能相互匹配，零配件也能夠相互通用，這對(duì)于推行各自的產(chǎn)品和在消費(fèi)運(yùn)營(yíng)中進(jìn)展協(xié)作很有協(xié)助。設(shè)有兩個(gè)廠(chǎng)商同時(shí)方案引進(jìn)彩電消費(fèi)線(xiàn)，而彩電有A、B兩種不同的制式，那么這時(shí)候兩個(gè)廠(chǎng)商之間就有一個(gè)選擇制式的博弈問(wèn)題。二、制式問(wèn)題1， 30， 00， 02， 2ABAB廠(chǎng)商2廠(chǎng)商1制式問(wèn)題 制式問(wèn)題混合戰(zhàn)略納什平衡 A B 得益廠(chǎng)商1： 0.4 0.6 0.664廠(chǎng)商2： 0.67 0.33 1.296假定兩廠(chǎng)商采用不同的制式所能獲取的各自益處如以下圖所示：三、市場(chǎng)時(shí)機(jī)博弈-50, -50100, 00

16、, 1000, 0進(jìn)不 進(jìn)進(jìn)不進(jìn)廠(chǎng)商2廠(chǎng)商1市場(chǎng)時(shí)機(jī) 進(jìn) 不進(jìn) 得益廠(chǎng)商1： 2/3 1/3 0廠(chǎng)商2： 2/3 1/3 0兩廠(chǎng)商同時(shí)發(fā)現(xiàn)一個(gè)市場(chǎng)時(shí)機(jī)，但這個(gè)市場(chǎng)的容量并不大，兩個(gè)廠(chǎng)商該如何選擇呢？廠(chǎng)商1的混合戰(zhàn)略必需使廠(chǎng)商2選擇進(jìn)與不進(jìn)的期望得益一樣，廠(chǎng)商2 的情形類(lèi)似?；旌蠎?zhàn)略反響函數(shù)反響函數(shù)：一博弈方對(duì)另一博弈方每種能夠的決策內(nèi)容的最正確反響決策構(gòu)成的函數(shù)。在純戰(zhàn)略的范疇內(nèi)，反響函數(shù)是各博弈方選擇的純戰(zhàn)略對(duì)其他博弈方純戰(zhàn)略的反響；在混合戰(zhàn)略的范疇內(nèi)，博弈方的決策內(nèi)容為選擇概率分布，反響函數(shù)就是一方對(duì)另一方的概率分布的反響，也是一定的概率分布。由于純戰(zhàn)略可了解為混合戰(zhàn)略，因此實(shí)踐上反響函數(shù)

17、的概念，可以在混合戰(zhàn)略概率分布之間反響的意義上一致同來(lái)。法三：混合戰(zhàn)略反響函數(shù)猜硬幣博弈-1， 11， -11， -1-1， 1正 面反 面猜硬幣方正面反面猜硬幣博弈蓋硬幣方rq111/21/2(r,1-r)：蓋硬幣方選擇正反面的混合戰(zhàn)略概率分布(q,1-q)：猜硬幣方選擇正反面的混合戰(zhàn)略概率分布當(dāng)q0.5時(shí)，取r為0當(dāng)r0.5時(shí)，取q為1夫妻之爭(zhēng)博弈2， 10， 00， 01， 3時(shí)裝足球丈夫時(shí)裝足球妻子夫妻之爭(zhēng)rq111/33/4(r,1-r)：妻子的混合戰(zhàn)略概率分布(q,1-q)：丈夫的混合戰(zhàn)略概率分布當(dāng)q1/3時(shí)，取r為1當(dāng)r3/4時(shí)，取q為1混合戰(zhàn)略平衡 混合戰(zhàn)略要求人們以隨機(jī)的方式

18、選擇本人的行動(dòng)，由于隨機(jī)性行為無(wú)法準(zhǔn)確預(yù)期，因此很多人以為混合戰(zhàn)略并非一個(gè)令人稱(chēng)心的平衡概念?，F(xiàn)實(shí)生活中人們真會(huì)這樣采取行動(dòng)嗎？如何解釋混合戰(zhàn)略？參與人試圖經(jīng)過(guò)選擇混合戰(zhàn)略給對(duì)手呵斥一種不確定性，使對(duì)手不能預(yù)測(cè)本人的行動(dòng)。如，猜硬幣、劃拳?；旌蠎?zhàn)略平衡對(duì)參與人類(lèi)型的一種推斷。如監(jiān)視博弈，老板不知道工人的類(lèi)型，只知道“勤勞、“懶惰型工人各占50%。老板在選擇本人 戰(zhàn)略時(shí)仿佛面臨的是一個(gè)選擇混合戰(zhàn)略的 工人。納什定理：在一個(gè)由n個(gè)博弈方的博弈 中，假設(shè)n是有限的，且 Si 都是有限集(對(duì) i=1,n)，那么該博弈至少存在一個(gè)納什平衡，但能夠包含混合戰(zhàn)略。奇數(shù)定理Wilson,1971：幾乎一切有限

19、博弈都有有限奇數(shù)個(gè)納什平衡。納什平衡的存在性納什平衡的存在性 占優(yōu)平衡 反復(fù)剔除的占優(yōu)平衡 純戰(zhàn)略NE 混合戰(zhàn)略NE前一個(gè)平衡是后一個(gè)平衡的特例，后一個(gè)平衡是前一個(gè)的擴(kuò)展。上述四個(gè)平衡概念統(tǒng)稱(chēng)為納什平衡。占優(yōu)平衡反復(fù)剔除占優(yōu)平衡純戰(zhàn)略納什平衡混合戰(zhàn)略納什平衡多重平衡與協(xié)調(diào) 多重平衡的概念很多博弈具有多個(gè)納什平衡，比如以上講到的麥琪的禮物、性別戰(zhàn)等，稱(chēng)為多重平衡。多重平衡降低博弈的解釋力一方面無(wú)法知道哪個(gè)平衡會(huì)出現(xiàn)，另一方面會(huì)發(fā)生真正出現(xiàn)的結(jié)果與平衡結(jié)果不一致在某些具有多重平衡的博弈中，各個(gè)博弈方偏好于不同的平衡結(jié)果，如麥琪的禮物和性別博弈。那么，博弈方如何使本人偏好的平衡成為實(shí)踐的平衡結(jié)果呢？

20、這就是多重平衡的協(xié)調(diào)問(wèn)題。多重平衡與協(xié)調(diào) 帕累托上策平衡風(fēng)險(xiǎn)上策平衡聚點(diǎn)平衡相關(guān)平衡一、帕累托上策平衡有些博弈，雖然存在多個(gè)納什平衡，但這些納什平衡能夠有明顯的優(yōu)劣差別，一切博弈方都偏好其中同一個(gè)納什平衡。換句話(huà)說(shuō)，能夠有這些納什平衡中的某一個(gè)，給一切博弈方帶來(lái)的利益，都大于其他一切納什平衡會(huì)帶來(lái)的利益，此時(shí)，博弈方的選擇傾向性就會(huì)是一致的，各個(gè)博弈方不僅本人會(huì)選擇該納什平衡的戰(zhàn)略，而且可以預(yù)料其他博弈方也會(huì)選擇該納什平衡的戰(zhàn)略，因此不會(huì)有選擇困難。用這種方法選擇出來(lái)的納什平衡，也稱(chēng)為“帕累托上策平衡。一、帕累托上策平衡這個(gè)博弈中有兩個(gè)純戰(zhàn)略納什平衡，戰(zhàn)爭(zhēng)，戰(zhàn)爭(zhēng)和和平，和平，顯然后者帕累托優(yōu)于前者，所以，和平，和平是本博弈的一個(gè)帕累托上策平衡。-5， -5-10， 88， -1010， 10戰(zhàn)爭(zhēng)和平國(guó)家2戰(zhàn)爭(zhēng)和平國(guó)家1戰(zhàn)爭(zhēng)與和平為什么理性的國(guó)家之間不會(huì)選擇戰(zhàn)爭(zhēng)，但歷史上會(huì)有那么多戰(zhàn)爭(zhēng)呢？決策者思索短期利益、個(gè)人或小集團(tuán)利益；決策者確實(shí)缺乏理性和明智；部分地域或特定時(shí)期的利益比上述博弈中所假設(shè)的要大等；二、風(fēng)險(xiǎn)上策平衡帕累托上策平衡并