混合策略课件

定义 在一个n人博弈的标准式表述中，参与人的策略 空间为 ,收益函数为 ,我们用 表示此博弈。博弈的标准式和纳什均衡2024/7/71张醒洲，大连v模型两个参与人 1,2每个参与人的策略 空间为H,T收益v零和v试着找到纳什均衡 两个男孩各自有一个硬币并且他们必须选择将硬币的正面朝上还是背面朝上。如果两个硬币朝上的面相同（即都是正面或都是背面），则参与人2将赢得参与人1的硬币；否则，参与人1将赢得参与人2的硬币。2024/7/72张醒洲，大连v如果参与人的策略一致(正面，正面)或(反面，反 面)则参与人1会偏向于改变策略；v但是如果两者策略不一致(正面,反面)或(反面,正 面)则参与人2偏向于改变策略。没有一组策略满足(NE)v此博弈也不存在纳什均衡无论参与人1选择哪个纯策略，参与人都可以打败他。2024/7/74张醒洲，大连v猜硬币博弈一个非常突出的特点是每个参与人都试图猜中对方的策略。v任何这一类都没有纳什均衡至少不存在1.1.C节所定义的纳什均衡因为这一类博弈的解包含了一个参与人对其他参与人行为的不 确定。v 现在我们介绍混合策略2024/7/75张醒洲，大连v考虑标准式博弈G=S1,Sn;u1,unv此后我们定义Si 中的策略为参与人 i 的纯策略 在本节的完全信息同时行动博弈中，一个参与人的纯策 略就是他可以选择的不同行动；例如，在猜硬币的博弈中，Si 包含两个纯策略：正面 和背面。v参与人i的一个混合策略是在其策略空间Si中的（一些或全部）策略的概率分布。2024/7/76张醒洲，大连v随机事件事件有明确定义事件有明确定义.我们可以区分不同的事件我们可以区分不同的事件.在进行观察或试验前在进行观察或试验前,我们不能肯定的说一个具我们不能肯定的说一个具体的事件会出现体的事件会出现.我们可以判断哪些事件有可能我们可以判断哪些事件有可能出现出现,并且能判断每一个事件出现的可能性大小并且能判断每一个事件出现的可能性大小.v概率事件的概率是对一次随机试验中该事件出现的可事件的概率是对一次随机试验中该事件出现的可能性的度量能性的度量如果对可能性的度量以某种客观规律或物质属性如果对可能性的度量以某种客观规律或物质属性为基础为基础,我们就用我们就用“概率概率”一词一词如果对可能性的度量以个人经验、主观判断为基如果对可能性的度量以个人经验、主观判断为基础，就用础，就用“主观概率主观概率”、“信念信念”、“置信度置信度”等术语等术语2024/7/77张醒洲，大连v样本空间：=1,2,n,试验中可能出现的所有基本结果i的集合事件由基本结果组成，是样本空间的子集。如果在试验中事件A中的一个结果出现了,就说事件A发生。v概率分布就是将总概率P()1分解到所有可能的样本点或事件上的一种方式2024/7/78张醒洲，大连v概率测度 样本空间上的一个概率测度是的子集的一个函数P()，它满足三条公理：v公理(1)0P(E)1,对任一事件Ev公理(2)P()1v公理(3)对任何一列互不相容的事件E1,E2,.,即EiEj=(空集),ij,有 我们称P(E)为事件E的概率。2024/7/79张醒洲，大连v参与人i的一个混合策略是在其策略空间Si中的策略的概率分布v举例:猜硬币S2 包含两个纯策略即正面和反面,因此参与人2的一个混合策略为概率分布(q,1-q),其中q 为正面朝上的概率，1-q 是背面朝上的概率,并且 0 q 1.混合策略(0,1)是背面朝上的纯策略;类似地,混合策略(1,0)是正面朝上的纯策略。2024/7/710张醒洲，大连v参与人2 的一个混合策略为概率分布(q,r,1-q-r),其中 q表示出左的概 率，r 表示出中的概率，1-q r 表示出右的概率。和前面一样，0 q 1,并且还应满足 0 r 1 和 0 q+r 1。v混合策略(1/3,1/3,1/3)表示参与人出左、中、右的概率相同，而 (1/2,1/2,0)表示出左、中的概率相同，但不可能出右。参与人的一个纯策略只 是其混合策略的一个特 例，例如参与人2出左的 纯策略可表示为混合策 略(1,0.0)。2024/7/711张醒洲，大连 更为一般地，假定参与人 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 内任意一个纯策略。定义 对标准式博弈 ，假设S i=si1,siK 。那么，参与人i的一个混合策略为概率分布 pi=(pi1,piK)，其中对所有 k=1,K，0pik 1，且 pi1+piK=1。2024/7/712张醒洲，大连v当参与人 i不确定参与人 j会如何行动时，他可以把参与人 j的混合策略作为参与人 j行动的一个解释。例如:猜硬币 假设参与人1相信参与人会以q 的概率出正面，以1-q 的概率出背面；也就是说，1 相信2的混合策略是(q,1-q)。2024/7/713张醒洲，大连v这里有三枚硬币,每一面被贴上红色或白色纸片(如下图).为了方便从左向右编号1、2、3.123现在从中任取一枚放在桌面，结果你看到白色。请猜一下，这枚硬币的背面是什么颜色?统计频数红色 人白色 人共 人计算频率红色%白色%2024/7/714张醒洲，大连1/21/31/31/21/21/21/21/21/3NC2C1C3这里有三枚硬币,每一面被贴上红色或白色纸片(如下图).为了方便从左向右编号1、2、3号硬币123现在从中任取一枚放在桌面，结果你看到白色。请猜一下，这是几号硬币?2024/7/715张醒洲，大连v提示:根据条件“看到一面白色”,只考虑前两枚硬币(拿走两面全是红色的第三枚硬币).区分第一枚硬币的两个面，尽管它们同色同质。你可以设想给第一枚的两面分别标记11与12。现在知道，从前两枚硬币中任取一个并让白色朝上，共三种可能。由于硬币质地均匀，随机抽取，随机搁置，我们认为这三种情形等可能。三枚硬币，任取一枚平放在桌面上，共有32=6种等可能的情形。满足条件“白色在上”的只有这三种。1-21-1211121112上上下2024/7/716张醒洲，大连试验有两种可能结果，你的信念是硬币以2:1 的比例出现白色与红色.猜对得1分,猜错扣1分.请估计你的策略“猜白色出现”与“猜红色出现”的预期支付各为多少？预期支付就是概率加权支付将你在所有可能结果上的支付按这些结果出现的概率加权求和2024/7/717张醒洲，大连v给定以下信念如果参与人1的反应是出正面，则他的期望收益是 q (-1)+(1-q)1=1-2q 如果参与人1的反应是出正面，则他的期望收益是 q 1+(1-q)(-1)=2q-1.因为当且仅当当且仅当 q 2q-1成立,则如果q 1/2,参与人1的最优纯策略为出背面；如果 q=,参与人1出正面与出背面没有差别。2024/7/718张醒洲，大连v针对参与人1对参与人2的可能行动作出的任何推断(q,1-q)，1的 最优反应是要么是T(当 q 1/2)，要么是M(当q 1/2),但不会是 B，虽然T 或 M 并不严格优于 Bv关键：存在一个混合策略严格优于B 如果参与人1以1/2的概率出T，以1/2 的概率出 M，则1的期望收益是3/2 无论参与人2采取哪种策略（纯的 或混合的），参与人1的收益3/2 都 大于其出B时所获得的收益。图 1.3.1这个例子说明了在“寻找另外一个严格优于 si 的策略”时，混合策略所起的作 用。2024/7/719张醒洲，大连v图 1.3.2表明，一个给定的纯策略可以是一个混合策略的最优反应，即使这一纯策略并不是其他纯策略的最优反应。在这个博弈中，B不是参与人 1对参与人2的纯策略L或R的 最优反应；但B是参与人1对参与人2的 混合策略(q,1-q)的最优反 应，假定 1/3 q 2/3；这个例子说明了混合策略在 “参与人i可能持有的推断”中 的作用Figure 1.3.22024/7/720张醒洲，大连对参与人j的混合策略，参与人i的最优混合策略给定以下信念如果参与人1出正面,他的期望 收益是1-2q；如果参与人1出背面，他的期望 收益是2q-1.考虑参与人1可能的混合策略令(r,1-r)为参与人1混合策略(以概率 r 出正面,以概率1-r出背面)；对任意 0,1 上的q，计算r的值,用 r*(q)表示。因此，参与人2选择混 合策略(q,1-q)时，参与人1的最优反应是(r,1-r)。2024/7/721张醒洲，大连v参与人 2:(q,1-q)v参与人 1:(r,1-r)v求解 r*(q)当参与人2的混合策略为(q,1-q)时，参与人选择(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)2024/7/722张醒洲，大连参与人 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 当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/7/723张醒洲，大连古诺模型的最优反应函数 这里，因为存在一个q，使得r*(q)有不止一个解，我们称r*(q)为参与人1的最优反应对应。最优反应对应和我们之前讨论的相关概念相比(我们只考虑了参与人1的纯策略)，这是一个更强的概念。2024/7/724张醒洲，大连v完全信息静态博弈中，参与人同时行动，并且参与人2和参与人1会以相同的方式考 虑此博弈。v对参与人1 的策略(r,1-r)，参与人2的最优 反应是(q*(r),1-q*(r),其中q*(r)=arg max(1-2r)+q(4r-2)2024/7/725张醒洲，大连v最优反应r*(q)和q*(r)的交点确定了猜硬币博弈的纳什均衡：如果参与人i的策略是 (1/2,1/2)，则参与人j的最 优反应是(1/2,1/2)，满足纳什均衡的要求。图 1.3.62024/7/726张醒洲，大连v一个混合策略纳什均衡不依赖任何参与人扔硬币、掷骰子或其他随机 选择策略的行为。更确切地，我们可以把参与人j 的混合策略解释为 参与人i对参与人j选择哪一个纯策略的不确定性。v每一个参与人确定性的选择一个纯策略.但对方不具备关于这一策略的充分信息,这时就要作相应的预测,将对方的行为理解为一个混合策略,并作出相应的对策(chose a best response to a mixed strategy)v每一个参与人选择一个纯战略,正是利用了对手关于自已行为的不确定性。2024/7/727张醒洲，大连v定义 在两个参与人标准式博弈 G=S1,S2;u1,u2 中，混合策略(p*1,p*2)是纳什均衡的充要条件为：每一参与人的混合策略是另一个参与人混 合策略的最优反应，即其中2024/7/728张醒洲，大连此博弈存在两个纯策略纳什均衡(Opera,Opera)和(Fight,Fight)都是纳什均衡2024/7/729张醒洲，大连v找到性别战博弈所有纳什均衡v混合策略组:(r,1-r)=(2/3,1/3)和(q,1-q)=(1/3,2/3)是一个纳什均衡2024/7/730张醒洲，大连vJohn Nash,“Equilibrium points in n-person games,”Proceedings of the National Academy of Sciences,36(1950),48-49.v在一个n人标准博弈中，如果参与人的数量以及每个参与人的策略空间都是有限的，那么此博弈存在至少一个纳什均衡，可能包含混合策略。2024/7/731张醒洲，大连 纳什定理的证明需用到不动点定理。作为不动点定理的一个简单例子，假定 f(x)是一个定义域和值域都在0,1之间的连续函数，则Brower的不动点定理保证了存在至少一个固定的点即在0,1中存在至少一个值x*，使得 f*(x)=x*。图1.3.13给出了一个例子。2024/7/732张醒洲，大连1.9 什么是标准式博弈的混合战略?什么是标准式博弈的混合战略纳什均衡?2024/7/733张醒洲，大连2024/7/734张醒洲，大连