CH02混合策略(博弈论,张醒洲)

2019/9/7张醒洲，大连1混合策略找到不确定情况下的最优反应定义在一个n人博弈的标准式表述中，参与人的策略空间为,收益函数为,我们用表示此博弈。2019/9/7张醒洲，大连2纳什均衡博弈的标准式和纳什均衡1,,nSSnuu,,1nnuuS,,;,,SG112019/9/7张醒洲，大连3举例:猜硬币•模型–两个参与人{1,2}–每个参与人的策略空间为{H,T}–收益•零和•试着找到纳什均衡参与人2参与人1正面背面正面-1,11,-1背面1,-1-1,1两个男孩各自有一个硬币并且他们必须选择将硬币的正面朝上还是背面朝上。如果两个硬币朝上的面相同（即都是正面或都是背面），则参与人2将赢得参与人1的硬币；否则，参与人1将赢得参与人2的硬币。猜硬币•如果参与人的策略一致——(正面，正面)或(反面，反面)—则参与人1会偏向于改变策略；•但是如果两者策略不一致—(正面,反面)或(反面,正面)—则参与人2偏向于改变策略。参与人2正面背面正面-1,11,-1参与人1背面1,-1-1,1•没有一组策略满足(NE)2019/9/7张醒洲，大连5石头-剪刀-布博弈•此博弈也不存在纳什均衡–无论参与人1选择哪个纯策略，参与人都可以打败他。参与人2石头剪刀布石头0,01,00,1参与人1剪刀0,10,01,0布1,00,10,02019/9/7张醒洲，大连6猜对方策略•猜硬币博弈一个非常突出的特点是每个参与人都试图猜中对方的策略。•任何这一类都没有纳什均衡–至少不存在1.1.C节所定义的纳什均衡–因为这一类博弈的解包含了一个参与人对其他参与人行为的不确定。•现在我们介绍混合策略2019/9/7张醒洲，大连7纯策略，混合策略•考虑标准式博弈G={S1,····,Sn;u1,····,un}•此后我们定义Si中的策略为参与人i的纯策略–在本节的完全信息同时行动博弈中，一个参与人的纯策略就是他可以选择的不同行动；–例如，在猜硬币的博弈中，Si包含两个纯策略：正面和背面。•参与人i的一个混合策略是在其策略空间Si中的（一些或全部）策略的概率分布。2019/9/7张醒洲，大连8概率和信念•随机事件–事件有明确定义.我们可以区分不同的事件.–在进行观察或试验前,我们不能肯定的说一个具体的事件会出现.我们可以判断哪些事件有可能出现,并且能判断每一个事件出现的可能性大小.•概率–事件的概率是对一次随机试验中该事件出现的可能性的度量–如果对可能性的度量以某种客观规律或物质属性为基础,我们就用“概率”一词–如果对可能性的度量以个人经验、主观判断为基础，就用“主观概率”、“信念”、“置信度”等术语2019/9/7张醒洲，大连9概率分布•样本空间：Ω={ω1,ω2,…,ωn,…}–试验中可能出现的所有基本结果ωi的集合–事件由基本结果组成，是样本空间的子集。如果在试验中事件A中的一个结果出现了,就说事件A发生。•概率分布就是将总概率P(Ω)＝1分解到所有可能的样本点或事件上的一种方式．2019/9/7张醒洲，大连10概率的公理化定义•概率测度样本空间Ω上的一个概率测度是Ω的子集的一个函数P(·)，它满足三条公理：•公理(1)0≤P(E)≤1,对任一事件E•公理(2)P(Ω)＝1•公理(3)对任何一列互不相容的事件E1,E2,….,即Ei∩Ej=Ф(空集),i≠j,有我们称P(E)为事件E的概率。11P(E)P(E)iiii2019/9/7张醒洲，大连11混合粗略：猜硬币•参与人i的一个混合策略是在其策略空间Si中的策略的概率分布•举例:猜硬币–S2包含两个纯策略即正面和反面,因此参与人2的一个混合策略为概率分布(q,1-q),其中q为正面朝上的概率，1-q是背面朝上的概率,并且0q1.参与人2参与人1正面q背面1-q正面-1,11,-1背面1,-1-1,1混合策略(0,1)是背面朝上的纯策略;类似地,混合策略(1,0)是正面朝上的纯策略。2019/9/7张醒洲，大连12混合策略:举例•参与人2的一个混合策略为概率分布(q,r,1-q-r),其中q表示出左的概率，r表示出中的概率，1-q–r表示出右的概率。和前面一样，0q1,并且还应满足0r1和0q+r1。•混合策略(1/3,1/3,1/3)表示参与人出左、中、右的概率相同，而(1/2,1/2,0)表示出左、中的概率相同，但不可能出右。参与人2左中右上1,01,20,1参与人1下0,30,12,0图1.1.1atPager6•参与人的一个纯策略只是其混合策略的一个特例，例如参与人2出左的纯策略可表示为混合策略(1,0.0)。2019/9/7张醒洲，大连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内任意一个纯策略。定义对标准式博弈，假设Si={si1,…,siK}。那么，参与人i的一个混合策略为概率分布pi=(pi1,…,piK)，其中对所有k=1,…,K，0≤pik≤1，且pi1+···+piK=1。nnuuS,,;,,SG112019/9/7张醒洲，大连14参与人j的混合策略解释•当参与人i不确定参与人j会如何行动时，他可以把参与人j的混合策略作为参与人j行动的一个解释。参与人2参与人1正面q背面1-q正面-1,11,-1背面1,-1-1,1例如:猜硬币假设参与人1相信参与人会以q的概率出正面，以1-q的概率出背面；也就是说，1相信2的混合策略是(q,1-q)。2019/9/7张醒洲，大连15猜猜硬币另一面的颜色•这里有三枚硬币,每一面被贴上红色或白色纸片(如下图).为了方便从左向右编号1、2、3.123•现在从中任取一枚放在桌面，结果你看到白色。请猜一下，这枚硬币的背面是什么颜色?•统计频数–红色人–白色人–共人•计算频率–红色%–白色%2019/9/7张醒洲，大连16猜猜哪个硬币被标记了1/21/31/31/21/21/21/21/21/3NC2C1C3•这里有三枚硬币,每一面被贴上红色或白色纸片(如下图).为了方便从左向右编号1、2、3号硬币123•现在从中任取一枚放在桌面，结果你看到白色。请猜一下，这是几号硬币?2019/9/7张醒洲，大连17猜猜哪个硬币被标记了•提示:–根据条件“看到一面白色”,只考虑前两枚硬币(拿走两面全是红色的第三枚硬币).–区分第一枚硬币的两个面，尽管它们同色同质。你可以设想给第一枚的两面分别标记11与12。–现在知道，从前两枚硬币中任取一个并让白色朝上，共三种可能。–由于硬币质地均匀，随机抽取，随机搁置，我们认为这三种情形等可能。三枚硬币，任取一枚平放在桌面上，共有3×2=6种等可能的情形。满足条件“白色在上”的只有这三种。1-21-1211121112上下2019/9/7张醒洲，大连18期望收益Student=►白红2/31-11/3-11•试验有两种可能结果，你的信念是硬币以2:1的比例出现白色与红色.猜对得1分,猜错扣1分.•请估计你的策略“猜白色出现”与“猜红色出现”的预期支付各为多少？•预期支付就是概率加权支付—将你在所有可能结果上的支付按这些结果出现的概率加权求和2019/9/7张醒洲，大连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,11,-1背面1,-1-1,1–因为当且仅当q½时，1-2q2q-1成立,则•如果q1/2,参与人1的最优纯策略为出正面；•如果q1/2,参与人1的最优纯策略为出背面；•如果q=½,参与人1出正面与出背面没有差别。2019/9/7张醒洲，大连20严格劣于一个混合策略的策略•针对参与人1对参与人2的可能行动作出的任何推断(q,1-q)，1的最优反应是要么是T(当q1/2)，要么是M(当q1/2),但不会是B，虽然T或M并不严格优于B•关键：存在一个混合策略严格优于B–如果参与人1以1/2的概率出T，以1/2的概率出M，则1的期望收益是3/2–无论参与人2采取哪种策略（纯的或混合的），参与人1的收益3/2都大于其出B时所获得的收益。参与人2LqR1-qT3,—0,—参与人1M0,—3,—B1,—1,—图1.3.1•这个例子说明了在“寻找另外一个严格优于si的策略”时，混合策略所起的作用。2019/9/7张醒洲，大连21给定的纯策略可以是混合策略的最优反应•图1.3.2表明，一个给定的纯策略可以是一个混合策略的最优反应，即使这一纯策略并不是其他纯策略的最优反应。•在这个博弈中，B不是参与人1对参与人2的纯策略L或R的最优反应；•但B是参与人1对参与人2的混合策略(q,1-q)的最优反应，假定1/3q2/3；•这个例子说明了混合策略在“参与人i可能持有的推断”中的作用参与人2LqR1-qT3,—0,—参与人1M0,—3,—B2,—2,—Figure1.3.22019/9/7张醒洲，大连22对参与人j的混合策略，参与人i的最优混合策略•给定以下信念–如果参与人1出正面,他的期望收益是1-2q；–如果参与人1出背面，他的期望收益是2q-1.•考虑参与人1可能的混合策略参与人2参与人1正面q背面1-q正面r-1,11,-1背面1-r1,-1-1,1–令(r,1-r)为参与人1混合策略(以概率r出正面,以概率1-r出背面)；–对任意[0,1]上的q，计算r的值,用r*(q)表示。因此，参与人2选择混合策略(q,1-q)时，参与人1的最优反应是(r,1-r)。2019/9/7张醒洲，大连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,11,-1背面1-r1,-1-1,1rq•(-1)+r(1-q)•1+(1-r)q•1+(1-r)(l-q)•(-1)=(2q-1)+r(2-4q),(1.3.1)r*(q)=argmax2(q-1/2)+4r(1/2-q)2019/9/7张醒洲，大连24对参与人j的混合策略，参与人i的最优混合策略•参与人2:(q,1-q)q∈[0,1]•参与人1:(r,1-r)r*(q)=argmax2(q-1/2)+4r(1/2-q)图1.3.3*11/2()01/2[0,1]1/2qrqqq当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)的最优反应。2019/9/7张醒洲，大连25最优反应对应•古诺模型的最优反应函数*11/2()01/2[0,1]1/2qrqqq这里，因为存在一个q，使得r*(q)有不止一个解，我们称r*(q)为参与人1的最优反应对应。•最优反应对应和我们之前讨论的相关概念相比(我们只考虑了参与人1的纯策略)，这是一个更强的概念。2019/9/7张醒洲，大连26对参与人1的混合策略，参与人2的最优反应•完全信息静态博弈中，参与人同时行动，并且参与人2和参与人1会以相同的方式考虑此博弈。•对参与人1的策略(r,1-r)，参与人2的最优反应是(q*(r),1-q*(r)),其中q*(r)=argmax(1-2r)+q(4r-2)01/2*()11/2[0,1]1/2rqrrr