混合策略課件

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

2、都是背面），則參與人2將贏得參與人1的硬幣；否則，參與人1將贏得參與人2的硬幣。猜硬幣 如果參與人的策略一致(正面，正面) 或 (反面，反 面)則參與人1會(huì)偏向于改變策略； 但是如果兩者策略不一致(正面, 反面) 或 (反面, 正 面)則參與人2偏向于改變策略。 參與人 2正面背面正面 -1, 1 1, -1參與人 1背面 1, -1 -1, 1 沒(méi)有一組策略滿足 (NE)2022-2-15張醒洲，大連5石頭-剪刀-布博弈 此博弈也不存在納什均衡 無(wú)論參與人1選擇哪個(gè)純策略，參與人都可以打敗他。 參與人 2石頭剪刀布石頭0, 01, 00, 1參與人 1剪刀0, 10, 01, 0布1, 00

3、, 10, 02022-2-15張醒洲，大連6猜對(duì)方策略 猜硬幣博弈一個(gè)非常突出的特點(diǎn)是每個(gè)參與人都試圖猜中對(duì)方的策略。 任何這一類都沒(méi)有納什均衡 至少不存在1.1.C節(jié)所定義的納什均衡 因?yàn)檫@一類博弈的解包含了一個(gè)參與人對(duì)其他參與人行為的不 確定。 現(xiàn)在我們介紹混合策略2022-2-15張醒洲，大連7純策略，混合策略 考慮標(biāo)準(zhǔn)式博弈G=S1, Sn; u1 , un 此后我們定義Si 中的策略為參與人 i 的純策略 在本節(jié)的完全信息同時(shí)行動(dòng)博弈中，一個(gè)參與人的純策 略就是他可以選擇的不同行動(dòng)； 例如，在猜硬幣的博弈中，Si 包含兩個(gè)純策略：正面 和背面。 參與人i的一個(gè)混合策略是在其策略空間

4、Si中的 （一些或全部）策略的概率分布。2022-2-15張醒洲，大連8概率和信念 隨機(jī)事件 事件有明確定義事件有明確定義. .我們可以區(qū)分不同的事件我們可以區(qū)分不同的事件. . 在進(jìn)行觀察或試驗(yàn)前在進(jìn)行觀察或試驗(yàn)前, ,我們不能肯定的說(shuō)一個(gè)具體的事我們不能肯定的說(shuō)一個(gè)具體的事件會(huì)出現(xiàn)件會(huì)出現(xiàn). .我們可以判斷哪些事件有可能出現(xiàn)我們可以判斷哪些事件有可能出現(xiàn), ,并且能并且能判斷每一個(gè)事件出現(xiàn)的可能性大小判斷每一個(gè)事件出現(xiàn)的可能性大小. . 概率 事件的概率是對(duì)一次隨機(jī)試驗(yàn)中該事件出現(xiàn)的可能性事件的概率是對(duì)一次隨機(jī)試驗(yàn)中該事件出現(xiàn)的可能性的度量的度量 如果對(duì)可能性的度量以某種客觀規(guī)律或物質(zhì)屬性

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

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

7、與人 2參與人 1正面 q背面 1-q正面 -1, 1 1, -1背面 1, -1 -1, 1混合策略 (0,1) 是背面朝上的純策略; 類似地, 混合策略 (1,0) 是正面朝上的純策略。2022-2-15張醒洲，大連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) 表示出左、中的概率相同，但不可能出

8、右。 參與人 2左中中右 上1, 01, 20, 1參與人 1 下0, 30, 12, 0 圖 1.1.1 at Pager 6參與人的一個(gè)純策略只 是其混合策略的一個(gè)特 例，例如參與人2出左的 純策略可表示為混合策 略 (1,0.0)。2022-2-15張醒洲，大連13混合混合策略策略:定義定義 更為一般地，假定參與人 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。我們

9、用 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, ,K， 0pik 1，且 pi1+piK =1。nnuuS,;,SG112022-2-15張醒洲，大連14參與人 j的混合策略解釋 當(dāng)參與人 i不確定參與人 j會(huì)如何行動(dòng)時(shí)，他可以把參與人 j的混合策略作為參與人 j行動(dòng)的一個(gè)解釋。 參與人 2參與人 1正面 q背面 1-q正面 -1, 1 1, -1背面 1, -1

10、-1, 1例如: 猜硬幣 假設(shè)參與人1相信參與人會(huì)以q 的概率出正面，以1 - q 的概率出背面；也就是說(shuō)，1 相信2的混合策略是 ( q, 1-q )。2022-2-15張醒洲，大連15猜猜硬幣另一面的顏色 這里有三枚硬幣,每一面被貼上紅色或白色紙片(如下圖).為了方便從左向右編號(hào)1、2、3.123 現(xiàn)在從中任取一枚放在桌面，結(jié)果你看到白色。請(qǐng)猜一下，這枚硬幣的背面是什么顏色? 統(tǒng)計(jì)頻數(shù) 紅色 人 白色 人 共 人 計(jì)算頻率 紅色 % 白色 %2022-2-15張醒洲，大連16猜猜哪個(gè)硬幣被標(biāo)記了1/21/31/31/21/21/21/21/21/3NC2C1C3 這里有三枚硬幣,每一面被貼

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

12、21112上上下2022-2-15張醒洲，大連18期望收益Student = 白紅 2/31-1 1/3-11試驗(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)求和2022-2-15張醒洲，大連19對(duì)參與人j的混合策略，參與人i的最優(yōu)純策略給定以下信念 如果參與人1的反應(yīng)是出正面， 則他的期望收益是 q (-1) + (1 - q) 1 = 1 - 2q 如果參與人1的反應(yīng)是出正面， 則他的期望收益是 q 1 + (1

13、 - q) (- 1) = 2q-1. 參與人 2參與人 1正面 q背面1-q正面 -1, 1 1, -1背面 1, -1 -1, 1 因?yàn)楫?dāng)且僅當(dāng)當(dāng)且僅當(dāng) q 2q-1成立, 則 如果q 1/2,參與人1的最優(yōu)純策略為出背面； 如果 q = ,參與人1出正面與出背面沒(méi)有差別。2022-2-15張醒洲，大連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

14、/2 的概率出 M ，則1的期望收益是3/2 無(wú)論參與人2采取哪種策略（純的 或混合的），參與人1的收益3/2 都 大于其出B時(shí)所獲得的收益。參與人 2L qR 1-qT3, 0, 參與人 1M 0, 3, B1, 1, 圖 1.3.1這個(gè)例子說(shuō)明了在“尋找另外一個(gè)嚴(yán)格優(yōu)于 si 的策略”時(shí)，混合策略所起的作 用。2022-2-15張醒洲，大連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的 混合策略

15、(q, 1 - q) 的最優(yōu)反 應(yīng)，假定 1/3 q 2/3；這個(gè)例子說(shuō)明了混合策略在 “參與人i可能持有的推斷”中 的作用參與人 2L qR 1-qT3, 0, 參與人 1M0, 3, B2, 2, Figure 1.3.22022-2-15張醒洲，大連22對(duì)參與人j的混合策略，參與人i的最優(yōu)混合策略給定以下信念 如果參與人1出正面, 他的期望 收益是1 - 2q ； 如果參與人1出背面，他的期望 收益是2q-1.考慮參與人1可能的混合策略 參與人2參與人 1正面 q背面1-q正面 r -1, 1 1, -1背面 1-r 1, -1 -1, 1 令 (r, 1- r) 為參與人1混合策略(以

16、概率 r 出正面,以概率1-r出背面)； 對(duì)任意 0,1 上的q，計(jì)算r的值, 用 r*(q)表示。因此， 參與人2選擇混 合策略 (q, 1 - q)時(shí)， 參與人1的最優(yōu)反應(yīng)是(r, 1 - r)。2022-2-15張醒洲，大連23對(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) 的期望收益如下： 參與人 2參與人 1正面 q背面1-q正面 r -1, 1 1, -1背面 1-r 1, -1 -1, 1 rq (-1) + r(1

17、- 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)2022-2-15張醒洲，大連24對(duì)參與人j的混合策略，參與人i的最優(yōu)混合策略 參與人 2: ( q, 1-q ) q0,10,1 參與人 1: ( r, 1- r ) r*(q) = arg max 2(q-1/2)+4r(1/2-q)圖 1.3.3*1 1/20,1 1/2qr qqq 當(dāng)q=1/2時(shí)，參與人1的期望收益2(q-1/2)+4r(1/2-q)與r無(wú)關(guān)，且參與人1的所有混

18、合策略 (r, 1-r) 都是無(wú)差異的。也就是說(shuō)，當(dāng)q=1/2 時(shí)，對(duì)于0到1之間的任何r，(r, 1-r)都是 (q, 1-q)的最優(yōu)反應(yīng)。2022-2-15張醒洲，大連25最優(yōu)反應(yīng)對(duì)應(yīng)古諾模型的最優(yōu)反應(yīng)函數(shù)*1 1/20,1 1/2qr qqq 這里，因?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)概念相比(我們只考慮了參與人1的純策略)，這是一個(gè)更強(qiáng)的概念。2022-2-15張醒洲，大連26對(duì)參與人1的混合策略，參與人2的最優(yōu)反應(yīng)完全信息靜態(tài)博弈中，參與人同時(shí)行動(dòng)， 并且參與人2和參與人1會(huì)以相同的方式考 慮此博弈

19、。對(duì)參與人1 的策略 (r, 1-r)，參與人2的最優(yōu) 反應(yīng)是 (q*(r), 1-q*(r),其中q*(r)=arg max (1-2r)+q(4r-2)0 1/20,1 1/2rqrrr2022-2-15張醒洲，大連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)，滿足納什均衡的要求。圖 1.3.62022-2-15張醒洲，大連28混合策略納什均衡的說(shuō)明一個(gè)混合策略納什均衡不依賴任何參與人扔硬幣、擲骰子或其他隨機(jī) 選擇策略的行為。更確切地，我們可以把參與人j 的

20、混合策略解釋為 參與人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)于自已行為的不確定性。2022-2-15張醒洲，大連29混合策略納什均衡混合策略納什均衡 : 兩人博弈定義 在兩個(gè)參與人標(biāo)準(zhǔn)式博弈 G= S1,S2; u1 ,u2 中，混合策略 (p*1,p*2) 是納什均衡的充要條件為：每一參與人的混合策略是另一個(gè)參與人混 合策略的最優(yōu)反應(yīng)，即11211212122122(,)(,),0,1(,)(,),0,1vppvppfor pvppvppfor p其中12121 ,211121 ,211(,)()()JkijkijkjkJkjkijkjkvppppussppuss 2022-2-15張醒洲，大連30納什均衡納什均衡: 性別戰(zhàn)博弈性別戰(zhàn)博弈 此博弈存