混合策略课件.ppt

2024/9/23张醒洲，大连1混合策略找到不确定情况下的最优反应 定义 在一个n人博弈的标准式表述中，参与人的策略 空间为 ,收益函数为 ,我们用 表示此博弈2024/9/23张醒洲，大连2纳什均衡 博弈的标准式和纳什均衡2024/9/23张醒洲，大连3举例: 猜硬币•模型–两个参与人 {1,2}–每个参与人的策略 空间为{H,T}–收益•零和•试着找到纳什均衡 参与人2参与人 1 正面 背面正面 -1, 1 1, -1背面 1, -1 -1, 1 两个男孩各自有一个硬币并且他们必须选择将硬币的正面朝上还是背面朝上如果两个硬币朝上的面相同（即都是正面或都是背面），则参与人2将赢得参与人1的硬币；否则，参与人1将赢得参与人2的硬币猜硬币•如果参与人的策略一致——(正面，正面) 或 (反面，反 面)—则参与人1会偏向于改变策略；•但是如果两者策略不一致—(正面, 反面) 或 (反面, 正 面)—则参与人2偏向于改变策略。

参与人 2正面背面正面 -1, 1 1, -1参与人 1背面 1, -1 -1, 1•没有一组策略满足 (NE)2024/9/23张醒洲，大连5石头-剪刀-布博弈•此博弈也不存在纳什均衡–无论参与人1选择哪个纯策略，参与人都可以打败他 参与人 2石头剪刀布石头0, 01, 00, 1参与人 1剪刀0, 10, 01, 0布1, 00, 10, 02024/9/23张醒洲，大连6猜对方策略 •猜硬币博弈一个非常突出的特点是每个参与人都试图猜中对方的策略•任何这一类都没有纳什均衡–至少不存在1.1.C节所定义的纳什均衡–因为这一类博弈的解包含了一个参与人对其他参与人行为的不 确定• 现在我们介绍混合策略2024/9/23张醒洲，大连7纯策略，混合策略•考虑标准式博弈G={S1,····, Sn; u1 ,····, un}•此后我们定义Si 中的策略为参与人 i 的纯策略– 在本节的完全信息同时行动博弈中，一个参与人的纯策 略就是他可以选择的不同行动；– 例如，在猜硬币的博弈中，Si 包含两个纯策略：正面 和背面。

•参与人i的一个混合策略是在其策略空间Si中的 （一些或全部）策略的概率分布2024/9/23张醒洲，大连8概率和信念•随机事件–事件有明确定义事件有明确定义. .我们可以区分不同的事件我们可以区分不同的事件. .–在进行观察或试验前在进行观察或试验前, ,我们不能肯定的说一个具体的事我们不能肯定的说一个具体的事件会出现件会出现. .我们可以判断哪些事件有可能出现我们可以判断哪些事件有可能出现, ,并且能并且能判断每一个事件出现的可能性大小判断每一个事件出现的可能性大小. .•概率–事件的概率是对一次随机试验中该事件出现的可能性事件的概率是对一次随机试验中该事件出现的可能性的度量的度量–如果对可能性的度量以某种客观规律或物质属性为基如果对可能性的度量以某种客观规律或物质属性为基础础, , 我们就用我们就用“概率概率”一词一词–如果对可能性的度量以个人经验、主观判断为基础，如果对可能性的度量以个人经验、主观判断为基础，就用就用“主观概率主观概率”、、“信念信念”、、“置信度置信度”等术语等术语2024/9/23张醒洲，大连9概率分布•样本空间：Ω={ω1 , ω2 , …, ωn,…} –试验中可能出现的所有基本结果ωi的集合–事件由基本结果组成，是样本空间的子集。

如果在试验中事件A中的一个结果出现了,就说事件A发生•概率分布就是将总概率P(Ω)＝1分解到所有可能的样本点或事件上的一种方式．2024/9/23张醒洲，大连10概率的公理化定义•概率测度 样本空间Ω上的一个概率测度是Ω的子集的一个函数P( · ) ，它满足三条公理：•公理(1) 0≤P(E) ≤1, 对任一事件E•公理(2) P(Ω)＝1•公理(3) 对任何一列互不相容的事件E1,E2,….,即Ei∩Ej=Ф(空集), i≠j, 有 我们称P(E)为事件E的概率2024/9/23张醒洲，大连11混合粗略：猜硬币•参与人i的一个混合策略是在其策略空间Si中的策略的概率分布•举例: 猜硬币–S2 包含两个纯策略即正面和反面, 因此参与人2的一个混合策略为概率分布 (q, 1 - q), 其中q 为正面朝上的概率，1 - q 是背面朝上的概率, 并且 0 < q < 1. 参与人 2参与人 1正面 q背面 1-q正面 -1, 1 1, -1背面 1, -1 -1, 1混合策略 (0,1) 是背面朝上的纯策略; 类似地, 混合策略 (1,0) 是正面朝上的纯策略。

2024/9/23张醒洲，大连12混合策略: 举例 •参与人2 的一个混合策略为概率分布( q, r,1-q-r), 其中 q表示出左的概 率， r 表示出中的概率， 1 - q – r 表示出右的概率和前面一样， 0 < q < 1, 并且还应满足 0 < r < 1 和 0 < q + r < 1•混合策略 (1/3,1/3,1/3) 表示参与人出左、中、右的概率相同，而 (1/2,1/2,0) 表示出左、中的概率相同，但不可能出右 参与人 2左中中右 上1, 01, 20, 1参与人 1 下0, 30, 12, 0 图 1.1.1 at Pager 6•参与人的一个纯策略只 是其混合策略的一个特 例，例如参与人2出左的 纯策略可表示为混合策 略 (1,0.0)2024/9/23张醒洲，大连13混合混合策略策略:定义定义 更为一般地，假定参与人 i有K个纯策略：Si ={si1, …,siK}.参与人 i的一个混合策略是一个概率分布 ( pi1, …,piK ) ,其中 piK表示对所有k=1, …,K,参与人i选择策略 sik的概率，由于 pik是一个概率，对所有k=1, …,K，有 0≤pik≤ 1且 pi1+···+piK =1。

我们用 pi表示基于Si 的任意一个混合策略，其中包含了选择每一个纯策略的概率，正如我们用 si表示 Si 内任意一个纯策略定义 对标准式博弈 ，假设S i = { si1, …,siK } 那么，参与人i的一个混合策略为概率分布 pi= ( pi1, …,piK )，其中对所有 k=1, …,K， 0≤pik≤ 1，且 pi1+···+piK =12024/9/23张醒洲，大连14参与人 j的混合策略解释•当参与人 i不确定参与人 j会如何行动时，他可以把参与人 j的混合策略作为参与人 j行动的一个解释 参与人 2参与人 1正面 q背面 1-q正面 -1, 1 1, -1背面 1, -1 -1, 1例如: 猜硬币 假设参与人1相信参与人会以q 的概率出正面，以1 - q 的概率出背面；也就是说，1 相信2的混合策略是 ( q, 1-q )2024/9/23张醒洲，大连15猜猜硬币另一面的颜色•这里有三枚硬币,每一面被贴上红色或白色纸片(如下图).为了方便从左向右编号1、2、3.123•现在从中任取一枚放在桌面，结果你看到白色。

请猜一下，这枚硬币的背面是什么颜色?•统计频数–红色 人–白色 人–共 人•计算频率–红色 %–白色 %2024/9/23张醒洲，大连16猜猜哪个硬币被标记了1/21/31/31/21/21/21/21/21/3NC2C1C3•这里有三枚硬币,每一面被贴上红色或白色纸片(如下图).为了方便从左向右编号1、2、3号硬币123•现在从中任取一枚放在桌面，结果你看到白色请猜一下，这是几号硬币?2024/9/23张醒洲，大连17猜猜哪个硬币被标记了•提示:–根据条件“看到一面白色”, 只考虑前两枚硬币(拿走两面全是红色的第三枚硬币).–区分第一枚硬币的两个面，尽管它们同色同质你可以设想给第一枚的两面分别标记11与12–现在知道，从前两枚硬币中任取一个并让白色朝上，共三种可能–由于硬币质地均匀，随机抽取，随机搁置，我们认为这三种情形等可能三枚硬币，任取一枚平放在桌面上，共有3×2=6种等可能的情形满足条件“白色在上”的只有这三种1-21-1211121112上上下2024/9/23张醒洲，大连18期望收益Student =►白红 2/31-1 1/3-11•试验有两种可能结果，你的信念是硬币以2:1 的比例出现白色与红色.猜对得1分,猜错扣1分.•请估计你的策略“猜白色出现”与“猜红色出现”的预期支付各为多少？•预期支付就是概率加权支付—将你在所有可能结果上的支付按这些结果出现的概率加权求和2024/9/23张醒洲，大连19对参与人j的混合策略，参与人i的最优纯策略•给定以下信念–如果参与人1的反应是出正面， 则他的期望收益是 q · (-1) + (1 - q) · 1 = 1 - 2q –如果参与人1的反应是出正面， 则他的期望收益是 q · 1 + (1 - q) ·(- 1) = 2q-1. 参与人 2参与人 1正面 q背面1-q正面 -1, 1 1, -1背面 1, -1 -1, 1–因为当且仅当当且仅当 q < ½时，时，1-2q >2q-1成立, 则•如果q < 1/2, 参与人1的最优纯策略为出正面； •如果q > 1/2,参与人1的最优纯策略为出背面；•如果 q = ½,参与人1出正面与出背面没有差别。

2024/9/23张醒洲，大连20严格劣于一个混合策略的策略•针对参与人1对参与人2的可能行动作出的任何推断 (q, 1-q)，1的 最优反应是要么是T (当 q > 1/2) ， 要么是M (当q < 1/2), 但不会是 B，虽然T 或 M 并不严格优于 B•关键：存在一个混合策略严格优于B –如果参与人1以1/2的概率出T，以1/2 的概率出 M ，则1的期望收益是3/2– 无论参与人2采取哪种策略（纯的 或混合的），参与人1的收益3/2 都 大于其出B时所获得的收益参与人 2L qR 1-qT3, —0, — 参与人 1M 0, —3, —B1, —1, —图 1.3.1•这个例子说明了在“寻找另外一个严格优于 si 的策略”时，混合策略所起的作 用2024/9/23张醒洲，大连21给定的纯策略可以是混合策略的最优反应•图 1.3.2表明，一个给定的纯策略可以是一个混合策略的最优反应，即使这一纯策略并不是其他纯策略的最优反应•在这个博弈中，B不是参与人 1对参与人2的纯策略L或R的 最优反应；•但B是参与人1对参与人2的 混合策略 (q, 1 - q) 的最优反 应，假定 1/3 < q < 2/3；•这个例子说明了混合策略在 “参与人i可能持有的推断”中 的作用参与人 2L qR 1-qT3, —0, —参与人 1M0, —3, —B2, —2, —Figure 1.3.22024/9/23张醒洲，大连22对参与人j的混合策略，参与人i的最优混合策略•给定以下信念–如果参与人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混合策略(以概率 r 出正面,以概率1-r出背面)；–对任意 [0,1] 上的q，计算r的值, 用 r*(q)表示。

因此， 参与人2选择混 合策略 (q, 1 - q)时， 参与人1的最优反应是(r, 1 - r)2024/9/23张醒洲，大连23对参与人j的混合策略，参与人i的最优混合策略•参与人 2: ( q, 1-q )•参与人 1: ( r, 1- r )•求解 r*(q)–当参与人2的混合策略为(q, 1 - q)时，参与人选择 (r, 1 - r) 的期望收益如下： 参与人 2参与人 1正面 q背面1-q正面 r -1, 1 1, -1背面 1-r 1, -1 -1, 1 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)2024/9/23张醒洲，大连24对参与人j的混合策略，参与人i的最优混合策略•参与人 2: ( q, 1-q ) q∈[0,1]∈[0,1]•参与人 1: ( r, 1- r ) r*(q) = arg max 2(q-1/2)+4r(1/2-q)图 1.3.3 当q=1/2时，参与人1的期望收益2(q-1/2)+4r(1/2-q)与r无关，且参与人1的所有混合策略 (r, 1-r) 都是无差异的。

也就是说，当q=1/2 时，对于0到1之间的任何r，(r, 1-r)都是 (q, 1-q)的最优反应2024/9/23张醒洲，大连25最优反应对应•古诺模型的最优反应函数 这里，因为存在一个q，使得r*(q) 有不止一个解，我们称r*(q) 为参与人1的最优反应对应•最优反应对应和我们之前讨论的相关概念相比(我们只考虑了参与人1的纯策略)，这是一个更强的概念2024/9/23张醒洲，大连26对参与人1的混合策略，参与人2的最优反应•完全信息静态博弈中，参与人同时行动， 并且参与人2和参与人1会以相同的方式考 虑此博弈•对参与人1 的策略 (r, 1-r)，参与人2的最优 反应是 (q*(r), 1-q*(r)),其中q*(r)=arg max (1-2r)+q(4r-2)2024/9/23张醒洲，大连27最优反应对应的解释•最优反应r*(q)和q*(r)的交点确定了猜硬币博弈的纳什均衡：–如果参与人i的策略是 (1/2,1/2) ，则参与人j的最 优反应是 (1/2,1/2)，满足纳什均衡的要求图 1.3.62024/9/23张醒洲，大连28混合策略纳什均衡的说明•一个混合策略纳什均衡不依赖任何参与人扔硬币、掷骰子或其他随机 选择策略的行为。

更确切地，我们可以把参与人j 的混合策略解释为 参与人i对参与人j选择哪一个纯策略的不确定性•每一个参与人确定性的选择一个纯策略. 但对方不具备关于这一策略的充分信息, 这时就要作相应的预测, 将对方的行为理解为一个混合策略,并作出相应的对策(chose a best response to a mixed strategy)•每一个参与人选择一个纯战略, 正是利用了对手关于自已行为的不确定性2024/9/23张醒洲，大连29混合策略纳什均衡混合策略纳什均衡 : 两人博弈•定义 在两个参与人标准式博弈 G={ S1,S2; u1 ,u2 } 中，混合策略 (p*1,p*2) 是纳什均衡的充要条件为：每一参与人的混合策略是另一个参与人混 合策略的最优反应，即其中2024/9/23张醒洲，大连30纳什均衡纳什均衡: 性别战博弈性别战博弈•此博弈存在两个纯策略纳什均衡– (Opera, Opera) 和 (Fight, Fight) 都是纳什均衡2024/9/23张醒洲，大连31纳什均衡纳什均衡: 性别战博弈性别战博弈•找到性别战博弈所有纳什均衡•混合策略组 : (r,1-r)=(2/3, 1/3)和(q, 1-q)=(1/3, 2/3)是一个纳什均衡 PatChrisOpera qFight1-qOpera r 2, 1 0, 0Fight 1-r 0, 0 1, 22024/9/23张醒洲，大连32纳什均衡的存在性•John Nash, “Equilibrium points in n-person games,” Proceedings of the National Academy of Sciences, 36 (1950), 48-49.•在一个n人标准博弈中，如果参与人的数量以及每个参与人的策略空间都是有限的，那么此博弈存在至少一个纳什均衡，可能包含混合策略。

2024/9/23张醒洲，大连33Brower的不动点定理 纳什定理的证明需用到不动点定理作为不动点定理的一个简单例子，假定 f(x) 是一个定义域和值域都在[0,1]之间的连续函数，则Brower的不动点定理保证了存在至少一个固定的点—即在[0,1]中存在至少一个值x*，使得 f*(x)=x*图1.3.13给出了一个例子2024/9/23张醒洲，大连34作业 1.9, 1.12,1.9 什么是标准式博弈的混合战略? 什么是标准式博弈的混合战略纳什均衡?2024/9/23张醒洲，大连35Assignment (1.13 选作) 。