混合策略課件(PPT 35頁).ppt

1、2020/9/1,張醒洲，大連,1,混合策略,找到不確定情況下的最優(yōu)反應(yīng),定義 在一個(gè)n人博弈的標(biāo)準(zhǔn)式表述中，參與人的策略 空間為 ,收益函數(shù)為 ,我們用 表示此博弈。,2020/9/1,張醒洲，大連,2,納什均衡,博弈的標(biāo)準(zhǔn)式和納什均衡,2020/9/1,張醒洲，大連,3,舉例: 猜硬幣,模型 兩個(gè)參與人 1,2 每個(gè)參與人的策略 空間為H,T 收益 零和 試著找到納什均衡,兩個(gè)男孩各自有一個(gè)硬幣并且他們必須選擇將硬幣的正面朝上還是背面朝上。如果兩個(gè)硬幣朝上的面相同（即都是正面或都是背面），則參與人2將贏得參與人1的硬幣；否則，參與人1將贏得參與人2的硬幣。,猜硬幣,如果參與人的策略一致(正

2、面，正面) 或 (反面，反 面)則參與人1會(huì)偏向于改變策略； 但是如果兩者策略不一致(正面, 反面) 或 (反面, 正 面)則參與人2偏向于改變策略。,沒有一組策略滿足 (NE),2020/9/1,張醒洲，大連,5,石頭-剪刀-布博弈,此博弈也不存在納什均衡 無論參與人1選擇哪個(gè)純策略，參與人都可以打敗他。,2020/9/1,張醒洲，大連,6,猜對(duì)方策略,猜硬幣博弈一個(gè)非常突出的特點(diǎn)是每個(gè)參與人都試圖猜中對(duì)方的策略。 任何這一類都沒有納什均衡 至少不存在1.1.C節(jié)所定義的納什均衡 因?yàn)檫@一類博弈的解包含了一個(gè)參與人對(duì)其他參與人行為的不 確定。 現(xiàn)在我們介紹混合策略,2020/9/1,張醒洲，

3、大連,7,純策略，混合策略,考慮標(biāo)準(zhǔn)式博弈G=S1, Sn; u1 , un 此后我們定義Si 中的策略為參與人 i 的純策略 在本節(jié)的完全信息同時(shí)行動(dòng)博弈中，一個(gè)參與人的純策 略就是他可以選擇的不同行動(dòng)； 例如，在猜硬幣的博弈中，Si 包含兩個(gè)純策略：正面 和背面。 參與人i的一個(gè)混合策略是在其策略空間Si中的 （一些或全部）策略的概率分布。,2020/9/1,張醒洲，大連,8,概率和信念,隨機(jī)事件 事件有明確定義.我們可以區(qū)分不同的事件. 在進(jìn)行觀察或試驗(yàn)前,我們不能肯定的說一個(gè)具體的事件會(huì)出現(xiàn).我們可以判斷哪些事件有可能出現(xiàn),并且能判斷每一個(gè)事件出現(xiàn)的可能性大小. 概率 事件的概率是對(duì)一

4、次隨機(jī)試驗(yàn)中該事件出現(xiàn)的可能性的度量 如果對(duì)可能性的度量以某種客觀規(guī)律或物質(zhì)屬性為基礎(chǔ), 我們就用“概率”一詞 如果對(duì)可能性的度量以個(gè)人經(jīng)驗(yàn)、主觀判斷為基礎(chǔ)，就用“主觀概率”、“信念”、“置信度”等術(shù)語,2020/9/1,張醒洲，大連,9,概率分布,樣本空間：=1 , 2 , , n, 試驗(yàn)中可能出現(xiàn)的所有基本結(jié)果i的集合 事件由基本結(jié)果組成，是樣本空間的子集。如果在試驗(yàn)中事件A中的一個(gè)結(jié)果出現(xiàn)了,就說事件A發(fā)生。 概率分布就是將總概率P()1分解到所有可能的樣本點(diǎn)或事件上的一種方式,2020/9/1,張醒洲，大連,10,概率的公理化定義,概率測(cè)度 樣本空間上的一個(gè)概率測(cè)度是的子集的一個(gè)函數(shù)P

5、( ) ，它 滿足三條公理： 公理(1) 0P(E) 1, 對(duì)任一事件E 公理(2) P()1 公理(3) 對(duì)任何一列互不相容的事件E1,E2,.,即EiEj=(空集), ij, 有 我們稱P(E)為事件E的概率。,2020/9/1,張醒洲，大連,11,混合粗略：猜硬幣,參與人i的一個(gè)混合策略是在其策略空間Si中的策略的概率分布 舉例: 猜硬幣 S2 包含兩個(gè)純策略即正面和反面, 因此參與人2的一個(gè)混合策略為概率分布 (q, 1 - q), 其中q 為正面朝上的概率，1 - q 是背面朝上的概率, 并且 0 q 1.,混合策略 (0,1) 是背面朝 上的純策略; 類似地, 混合 策略 (1,0

6、) 是正面朝上的 純策略。,2020/9/1,張醒洲，大連,12,混合策略: 舉例,參與人2 的一個(gè)混合策略為概率分布( q, r,1-q-r), 其中 q表示出左的概 率， r 表示出中的概率， 1 - q r 表示出右的概率。和前面一樣， 0 q 1, 并且還應(yīng)滿足 0 r 1 和 0 q + r 1。 混合策略 (1/3,1/3,1/3) 表示參與人出左、中、右的概率相同，而 (1/2,1/2,0) 表示出左、中的概率相同，但不可能出右。,參與人的一個(gè)純策略只 是其混合策略的一個(gè)特 例，例如參與人2出左的 純策略可表示為混合策 略 (1,0.0)。,2020/9/1,張醒洲，大連,13,

7、混合策略:定義,更為一般地，假定參與人 i有K個(gè)純策略：Si =si1, ,siK.參與人 i的一個(gè)混合策略是一個(gè)概率分布 ( pi1, ,piK ) ,其中 piK表示對(duì)所有k=1, ,K,參與人i選擇策略 sik的概率，由于 pik是一個(gè)概率，對(duì)所有k=1, ,K，有 0pik 1且 pi1+piK =1。我們用 pi表示基于Si 的任意一個(gè)混合策略，其中包含了選擇每一個(gè)純策略的概率，正如我們用 si表示 Si 內(nèi)任意一個(gè)純策略。,定義 對(duì)標(biāo)準(zhǔn)式博弈 ，假設(shè)S i = si1, ,siK 。 那么，參與人i的一個(gè)混合策略為概率分布 pi= ( pi1, ,piK )，其中對(duì) 所有 k=1,

8、 ,K， 0pik 1，且 pi1+piK =1。,2020/9/1,張醒洲，大連,14,參與人 j的混合策略解釋,當(dāng)參與人 i不確定參與人 j會(huì)如何行動(dòng)時(shí)，他可以把參與人 j的混合策略作為參與人 j行動(dòng)的一個(gè)解釋。,例如: 猜硬幣 假設(shè)參與人1相信參與人會(huì)以q 的概率出正面，以1 - q 的概率出背面；也就是說，1 相信2的混合策略是 ( q, 1-q )。,2020/9/1,張醒洲，大連,15,猜猜硬幣另一面的顏色,這里有三枚硬幣,每一面被貼上紅色或白色紙片(如下圖).為了方便從左向右編號(hào)1、2、3.,現(xiàn)在從中任取一枚放在桌面，結(jié)果你看到白色。請(qǐng)猜一下，這枚硬幣的背面是什么顏色? 統(tǒng)計(jì)頻數(shù)

9、 紅色 人 白色 人 共 人 計(jì)算頻率 紅色 % 白色 %,2020/9/1,張醒洲，大連,16,猜猜哪個(gè)硬幣被標(biāo)記了,這里有三枚硬幣,每一面被貼上紅色或白色紙片(如下圖).為了方便從左向右編號(hào)1、2、3號(hào)硬幣,現(xiàn)在從中任取一枚放在桌面，結(jié)果你看到白色。請(qǐng)猜一下，這是幾號(hào)硬幣?,2020/9/1,張醒洲，大連,17,猜猜哪個(gè)硬幣被標(biāo)記了,提示: 根據(jù)條件“看到一面白色”, 只考慮前兩枚硬幣(拿走兩面全是紅色的第三枚硬幣). 區(qū)分第一枚硬幣的兩個(gè)面，盡管它們同色同質(zhì)。你可以設(shè)想給第一枚的兩面分別標(biāo)記11與12。 現(xiàn)在知道，從前兩枚硬幣中任取一個(gè)并讓白色朝上，共三種可能。 由于硬幣質(zhì)地均勻，隨機(jī)抽

10、取，隨機(jī)擱置，我們認(rèn)為這三種情形等可能。,三枚硬幣，任取一枚平放在桌面上，共有32=6種等可能的情形。滿足條件“白色在上”的只有這三種。,2020/9/1,張醒洲，大連,18,期望收益,試驗(yàn)有兩種可能結(jié)果，你的信念是硬幣以2:1 的比例出現(xiàn)白色與紅色.猜對(duì)得1分,猜錯(cuò)扣1分. 請(qǐng)估計(jì)你的策略“猜白色出現(xiàn)”與“猜紅色出現(xiàn)”的預(yù)期支付各為多少？,預(yù)期支付就是概率加權(quán)支付將你在所有可能結(jié)果上的支付按這些結(jié)果出現(xiàn)的概率加權(quán)求和,2020/9/1,張醒洲，大連,19,對(duì)參與人j的混合策略，參與人i的最優(yōu)純策略,給定以下信念 如果參與人1的反應(yīng)是出正面， 則他的期望收益是 q (-1) + (1 - q)

11、 1 = 1 - 2q 如果參與人1的反應(yīng)是出正面， 則他的期望收益是 q 1 + (1 - q) (- 1) = 2q-1.,因?yàn)楫?dāng)且僅當(dāng) q 2q-1成立, 則 如果q 1/2,參與人1的最優(yōu)純策略為出背面； 如果 q = ,參與人1出正面與出背面沒有差別。,2020/9/1,張醒洲，大連,20,嚴(yán)格劣于一個(gè)混合策略的策略,針對(duì)參與人1對(duì)參與人2的可能行動(dòng)作出的任何推斷 (q, 1-q)，1的 最優(yōu)反應(yīng)是要么是T (當(dāng) q 1/2) ， 要么是M (當(dāng)q 1/2), 但不會(huì)是 B，雖然T 或 M 并不嚴(yán)格優(yōu)于 B 關(guān)鍵：存在一個(gè)混合策略嚴(yán)格優(yōu)于B 如果參與人1以1/2的概率出T，以1/2

12、的概率出 M ，則1的期望收益是3/2 無論參與人2采取哪種策略（純的 或混合的），參與人1的收益3/2 都 大于其出B時(shí)所獲得的收益。,圖 1.3.1,這個(gè)例子說明了在“尋找另外一個(gè)嚴(yán)格優(yōu)于 si 的策略”時(shí)，混合策略所起的作 用。,2020/9/1,張醒洲，大連,21,給定的純策略可以是混合策略的最優(yōu)反應(yīng),圖 1.3.2表明，一個(gè)給定的純策略可以是一個(gè)混合策略的最優(yōu)反應(yīng)，即使這一純策略并不是其他純策略的最優(yōu)反應(yīng)。,在這個(gè)博弈中，B不是參與人 1對(duì)參與人2的純策略L或R的 最優(yōu)反應(yīng)； 但B是參與人1對(duì)參與人2的 混合策略 (q, 1 - q) 的最優(yōu)反 應(yīng)，假定 1/3 q 2/3； 這個(gè)例

13、子說明了混合策略在 “參與人i可能持有的推斷”中 的作用,Figure 1.3.2,2020/9/1,張醒洲，大連,22,對(duì)參與人j的混合策略，參與人i的最優(yōu) 混合策略,給定以下信念 如果參與人1出正面, 他的期望 收益是1 - 2q ； 如果參與人1出背面，他的期望 收益是2q-1. 考慮參與人1可能的混合策略,令 (r, 1- r) 為參與人1混合策略(以概率 r 出正面,以概率1-r出背面)； 對(duì)任意 0,1 上的q，計(jì)算r的值, 用 r*(q)表示。因此， 參與人2選擇混 合策略 (q, 1 - q)時(shí)， 參與人1的最優(yōu)反應(yīng)是(r, 1 - r)。,2020/9/1,張醒洲，大連,23

14、,對(duì)參與人j的混合策略，參與人i的最優(yōu) 混合策略,參與人 2: ( q, 1-q ) 參與人 1: ( r, 1- r ) 求解 r*(q) 當(dāng)參與人2的混合策略為(q, 1 - q)時(shí)，參與人選擇 (r, 1 - r) 的期望收益如下：,rq (-1) + r(1 - q) 1 + (1 - r)q 1 + (1 - r)(l - q) (-1) = (2q-1 ) + r(2-4q) , (1.3.1) r*(q) =arg max 2(q-1/2)+4r(1/2-q),2020/9/1,張醒洲，大連,24,對(duì)參與人j的混合策略，參與人i的最優(yōu) 混合策略,參與人 2: ( q, 1-q )

15、 q0,1 參與人 1: ( r, 1- r ) r*(q) = arg max 2(q-1/2)+4r(1/2-q),圖 1.3.3,當(dāng)q=1/2時(shí)，參與人1的期望收益2(q-1/2)+4r(1/2-q)與r無關(guān)，且參與人1的所有混合策略 (r, 1-r) 都是無差異的。也就是說，當(dāng)q=1/2 時(shí)，對(duì)于0到1之間的任何r，(r, 1-r)都是 (q, 1-q)的最優(yōu)反應(yīng)。,2020/9/1,張醒洲，大連,25,最優(yōu)反應(yīng)對(duì)應(yīng),古諾模型的最優(yōu)反應(yīng)函數(shù),這里，因?yàn)榇嬖谝粋€(gè)q，使得r*(q) 有不止一個(gè)解，我們稱r*(q) 為參與人1的最優(yōu)反應(yīng)對(duì)應(yīng)。,最優(yōu)反應(yīng)對(duì)應(yīng),和我們之前討論的相關(guān)概念相比(我們

16、只考慮了參與人1的純策略)，這是一個(gè)更強(qiáng)的概念。,2020/9/1,張醒洲，大連,26,對(duì)參與人1的混合策略，參與人2的最優(yōu)反應(yīng),完全信息靜態(tài)博弈中，參與人同時(shí)行動(dòng)， 并且參與人2和參與人1會(huì)以相同的方式考 慮此博弈。 對(duì)參與人1 的策略 (r, 1-r)，參與人2的最優(yōu) 反應(yīng)是 (q*(r), 1-q*(r),其中q*(r)=arg max (1-2r)+q(4r-2),2020/9/1,張醒洲，大連,27,最優(yōu)反應(yīng)對(duì)應(yīng)的解釋,最優(yōu)反應(yīng)r*(q)和q*(r)的交點(diǎn)確定了猜硬幣博弈的納什均衡： 如果參與人i的策略是 (1/2,1/2) ，則參與人j的最 優(yōu)反應(yīng)是 (1/2,1/2)，滿足納什均

17、衡的要求。,圖 1.3.6,2020/9/1,張醒洲，大連,28,混合策略納什均衡的說明,一個(gè)混合策略納什均衡不依賴任何參與人扔硬幣、擲骰子或其他隨機(jī) 選擇策略的行為。更確切地，我們可以把參與人j 的混合策略解釋為 參與人i對(duì)參與人j選擇哪一個(gè)純策略的不確定性。 每一個(gè)參與人確定性的選擇一個(gè)純策略. 但對(duì)方不具備關(guān)于這一策略的充分信息, 這時(shí)就要作相應(yīng)的預(yù)測(cè), 將對(duì)方的行為理解為一個(gè)混合策略,并作出相應(yīng)的對(duì)策(chose a best response to a mixed strategy) 每一個(gè)參與人選擇一個(gè)純戰(zhàn)略, 正是利用了對(duì)手關(guān)于自已行為的不確定性。,2020/9/1,張醒洲，大連

18、,29,混合策略納什均衡 : 兩人博弈,定義 在兩個(gè)參與人標(biāo)準(zhǔn)式博弈 G= S1,S2; u1 ,u2 中，混合策略 (p*1,p*2) 是納什均衡的充要條件為：每一參與人的混合策略是另一個(gè)參與人混 合策略的最優(yōu)反應(yīng)，即,其中,2020/9/1,張醒洲，大連,30,納什均衡: 性別戰(zhàn)博弈,此博弈存在兩個(gè)純策略納什均衡 (Opera, Opera) 和 (Fight, Fight) 都是納什均衡,2020/9/1,張醒洲，大連,31,納什均衡: 性別戰(zhàn)博弈,找到性別戰(zhàn)博弈所有納什均衡 混合策略組 : (r,1-r)=(2/3, 1/3)和(q, 1-q)=(1/3, 2/3)是一個(gè)納什均衡,2020/9/1,張醒洲，大連,32,納什均衡的存在性,John Nash, “Equilibrium points in n-person games,” Proceedings of the National Academy of Sciences, 36 (1950), 48-49. 在一個(gè)n人標(biāo)準(zhǔn)博弈中，如果參與人的數(shù)量以及每個(gè)參與人的策略空間都是有限的，那么此博弈