CH02混合策略(博弈論,張醒洲)

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

2、2偏向于改變策略。沒有一組策略滿足 (NE)4石頭-剪刀-布博弈此博弈也不存在納什均衡無論參與人1選擇哪個純策略,參與人都可以打敗他。猜對方策略 猜硬幣博弈一個非常突出的特點(diǎn)是每個參與人都試圖猜中對方的策略。任何這一類都沒有納什均衡至少不存在1.1.C節(jié)所定義的納什均衡因?yàn)檫@一類博弈的解包含了一個參與人對其他參與人行為的不 確定。 現(xiàn)在我們介紹混合策略純策略，混合策略考慮標(biāo)準(zhǔn)式博弈G=S1, Sn; u1 , un此后我們定義Si 中的策略為參與人 i 的純策略 在本節(jié)的完全信息同時行動博弈中,一個參與人的純策 略就是他可以選擇的不同行動； 例如,在猜硬幣的博弈中,Si 包含兩個純策略：正面

3、和反面。參與人i的一個混合策略是在其策略空間Si中的 （一些或全部）策略的概率分布。概率和信念隨機(jī)事件事件有明確定義.我們可以區(qū)分不同的事件.在進(jìn)行觀察或試驗(yàn)前,我們不能肯定的說一個具體的事件會出現(xiàn).我們可以判斷哪些事件有可能出現(xiàn),并且能判斷每一個事件出現(xiàn)的可能性大小.概率事件的概率是對一次隨機(jī)試驗(yàn)中該事件出現(xiàn)的可能性的度量如果對可能性的度量以某種客觀規(guī)律或物質(zhì)屬性為根底, 我們就用“概率一詞如果對可能性的度量以個人經(jīng)驗(yàn)、主觀判斷為根底,就用“主觀概率、“信念、“置信度等術(shù)語概率分布樣本空間：=1 , 2 , , n, 試驗(yàn)中可能出現(xiàn)的所有根本結(jié)果i的集合事件由根本結(jié)果組成,是樣本空間的子集。

4、如果在試驗(yàn)中事件A中的一個結(jié)果出現(xiàn)了,就說事件A發(fā)生。概率分布就是將總概率P()1分解到所有可能的樣本點(diǎn)或事件上的一種方式概率的公理化定義概率測度 樣本空間上的一個概率測度是的子集的一個函數(shù)P( ) ,它滿足三條公理：公理(1) 0P(E) 1, 對任一事件E公理(2) P()1公理(3) 對任何一列互不相容的事件E1,E2,.,即EiEj=(空集), ij, 有 我們稱P(E)為事件E的概率。混合粗略：猜硬幣參與人i的一個混合策略是在其策略空間Si中的策略的概率分布舉例: 猜硬幣S2 包含兩個純策略即正面和反面, 因此參與人2的一個混合策略為概率分布 (q, 1 - q), 其中q 為正面朝

5、上的概率,1 - q 是反面朝上的概率, 并且 0 q 1. 混合策略 (0,1) 是反面朝上的純策略; 類似地, 混合策略 (1,0) 是正面朝上的純策略?；旌喜呗? 舉例 參與人2 的一個混合策略為概率分布( 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) 表示出左、中的概率相同,但不可能出右。參與人的一個純策略只 是其混合策略的一個特 例,例如參與人2出

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

7、i1, ,piK ),其中對所有 k=1, ,K, 0pik 1,且 pi1+piK =1。參與人 j的混合策略解釋當(dāng)參與人 i不確定參與人 j會如何行動時,他可以把參與人 j的混合策略作為參與人 j行動的一個解釋。例如: 猜硬幣 假設(shè)參與人1相信參與人會以q 的概率出正面,以1 - q 的概率出反面；也就是說,1 相信2的混合策略是 ( q, 1-q )。猜猜硬幣另一面的顏色這里有三枚硬幣,每一面被貼上紅色或白色紙片(如以下圖).為了方便從左向右編號1、2、3.123現(xiàn)在從中任取一枚放在桌面,結(jié)果你看到白色。請猜一下,這枚硬幣的反面是什么顏色?統(tǒng)計頻數(shù)紅色 人白色 人共 人計算頻率紅色 %白

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

9、共有32=6種等可能的情形。滿足條件“白色在上的只有這三種。1-21-1211121112上下期望收益Student =白紅 2/31-1 1/3-11試驗(yàn)有兩種可能結(jié)果,你的信念是硬幣以2:1 的比例出現(xiàn)白色與紅色.猜對得1分,猜錯扣1分.請估計你的策略“猜白色出現(xiàn)與“猜紅色出現(xiàn)的預(yù)期支付各為多少？預(yù)期支付就是概率加權(quán)支付將你在所有可能結(jié)果上的支付按這些結(jié)果出現(xiàn)的概率加權(quán)求和對參與人j的混合策略，參與人i的最優(yōu)純策略給定以下信念如果參與人1的反響是出正面, 則他的期望收益是 q (-1) + (1 - q) 1 = 1 - 2q 如果參與人1的反響是出正面, 則他的期望收益是 q 1 + (

10、1 - q) (- 1) = 2q-1.因?yàn)楫?dāng)且僅當(dāng) q 2q-1成立, 則如果q 1/2,參與人1的最優(yōu)純策略為出反面；如果 q = ,參與人1出正面與出反面沒有差異。嚴(yán)格劣于一個混合策略的策略針對參與人1對參與人2的可能行動作出的任何推斷 (q, 1-q),1的 最優(yōu)反響是要么是T (當(dāng) q 1/2) , 要么是M (當(dāng)q 1/2), 但不會是 B,雖然T 或 M 并不嚴(yán)格優(yōu)于 B關(guān)鍵：存在一個混合策略嚴(yán)格優(yōu)于B 如果參與人1以1/2的概率出T,以1/2 的概率出 M ,則1的期望收益是3/2 無論參與人2采取哪種策略（純的 或混合的）,參與人1的收益3/2 都 大于其出B時所獲得的收益。

11、圖 1.3.1這個例子說明了在“尋找另外一個嚴(yán)格優(yōu)于 si 的策略時,混合策略所起的作 用。給定的純策略可以是混合策略的最優(yōu)反應(yīng)圖 1.3.2說明,一個給定的純策略可以是一個混合策略的最優(yōu)反響,即使這一純策略并不是其他純策略的最優(yōu)反響。在這個博弈中,B不是參與人 1對參與人2的純策略L或R的 最優(yōu)反響；但B是參與人1對參與人2的 混合策略 (q, 1 - q) 的最優(yōu)反 應(yīng),假定 1/3 q 2/3；這個例子說明了混合策略在 “參與人i可能持有的推斷中 的作用Figure 1.3.2對參與人j的混合策略，參與人i的最優(yōu)混合策略給定以下信念如果參與人1出正面, 他的期望 收益是1 - 2q ；如

12、果參與人1出反面,他的期望 收益是2q-1.考慮參與人1可能的混合策略令 (r, 1- r) 為參與人1混合策略(以概率 r 出正面,以概率1-r出反面)；對任意 0,1 上的q,計算r的值, 用 r*(q)表示。因此, 參與人2選擇混 合策略 (q, 1 - q)時, 參與人1的最優(yōu)反響是(r, 1 - r)。對參與人j的混合策略，參與人i的最優(yōu)混合策略參與人 2: ( q, 1-q )參與人 1: ( r, 1- r )求解 r*(q)當(dāng)參與人2的混合策略為(q, 1 - q)時,參與人選擇 (r, 1 - r) 的期望收益如下： rq (-1) + r(1 - q) 1 + (1 - r

13、)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)對參與人j的混合策略，參與人i的最優(yōu)混合策略參與人 2: ( q, 1-q ) 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時,參與人1的期望收益2(q-1/2)+4r(1/2-q)與r無關(guān),且參與人1的所有混合策略 (r, 1-r) 都是無差異的。也就是說,當(dāng)q=1/2 時,對于0到1之間的任何r,(r, 1-r)都是

14、 (q, 1-q)的最優(yōu)反響。最優(yōu)反應(yīng)對應(yīng)古諾模型的最優(yōu)反響函數(shù) 這里,因?yàn)榇嬖谝粋€q,使得r*(q) 有不止一個解,我們稱r*(q) 為參與人1的最優(yōu)反響對應(yīng)。最優(yōu)反響對應(yīng)和我們之前討論的相關(guān)概念相比(我們只考慮了參與人1的純策略),這是一個更強(qiáng)的概念。對參與人1的混合策略，參與人2的最優(yōu)反應(yīng)完全信息靜態(tài)博弈中,參與人同時行動, 并且參與人2和參與人1會以相同的方式考 慮此博弈。對參與人1 的策略 (r, 1-r),參與人2的最優(yōu) 反響是 (q*(r), 1-q*(r),其中q*(r)=arg max (1-2r)+q(4r-2)最優(yōu)反應(yīng)對應(yīng)的解釋最優(yōu)反響r*(q)和q*(r)的交點(diǎn)確定了猜

15、硬幣博弈的納什均衡：如果參與人i的策略是 (1/2,1/2) ,則參與人j的最 優(yōu)反響是 (1/2,1/2),滿足納什均衡的要求。圖 1.3.6混合策略納什均衡的說明一個混合策略納什均衡不依賴任何參與人扔硬幣、擲骰子或其他隨機(jī) 選擇策略的行為。更確切地,我們可以把參與人j 的混合策略解釋為 參與人i對參與人j選擇哪一個純策略的不確定性。每一個參與人確定性的選擇一個純策略. 但對方不具備關(guān)于這一策略的充分信息, 這時就要作相應(yīng)的預(yù)測, 將對方的行為理解為一個混合策略,并作出相應(yīng)的對策(chose a best response to a mixed strategy)每一個參與人選擇一個純戰(zhàn)略,

16、 正是利用了對手關(guān)于自已行為的不確定性?；旌喜呗约{什均衡 : 兩人博弈定義 在兩個參與人標(biāo)準(zhǔn)式博弈 G= S1,S2; u1 ,u2 中,混合策略 (p*1,p*2) 是納什均衡的充要條件為：每一參與人的混合策略是另一個參與人混 合策略的最優(yōu)反響,即其中納什均衡: 性別戰(zhàn)博弈此博弈存在兩個純策略納什均衡 (Opera, Opera) 和 (Fight, Fight) 都是納什均衡納什均衡: 性別戰(zhàn)博弈找到性別戰(zhàn)博弈所有納什均衡混合策略組 : (r,1-r)=(2/3, 1/3)和(q, 1-q)=(1/3, 2/3)是一個納什均衡納什均衡的存在性John Nash, “Equilibrium points in n-person games, Proceedings of the National Academy of Sciences, 36 (1950), 48-49.在一個n人標(biāo)準(zhǔn)博弈中,如果參與人的