策略与博弈.

策略与博弈StrategiesandGames华南热带农业大学基础学院数学教研室舒兴明获取讲义或者演示稿邮箱：[e-mail]密码：31115085交流信息或交作业邮箱：[e-mail]博弈的游戏游戏1拿子游戏(Nim和Marienbad)有两堆火柴，以及两个局中人。游戏从局中人1开始，此后两个局中人轮流行动。在每个局中人的轮次里，他可以从两堆火柴的任何一堆中拿走任何（整数）数量的火柴。只要任何一堆火柴中尚有剩余的火柴，则要求每个局中人拿走一定数量且不能空手而返，但是每次只能从其中一堆中取火柴。在“拿子游戏”Nim中，无论哪个局中人，取走最后一根火柴者都算赢。在Marienbad中，谁难走最后一根火柴者就算输。感兴趣问题在拿子游戏中，任何一个人是否存在赢的策略。也就是是否存在这样的策略，只要在你的轮次中使用它，不管以后游戏如何进行，可以保证你稳操胜券？游戏分析如果两堆火柴数目相同，称为两堆平衡，则局中人2存在赢策略。反之，如果两堆不平衡，则局中人1存在赢策略。对于平衡问题，局中人2仿照局中人1在另外一堆中拿子；对于非平衡问题，局中人1通过第一次拿子，使得两堆平衡，然后，回到平衡问题，局中人2和1的位置置换。Nim游戏思考Nim拿子游戏是否存在其他策略？如果火柴堆不止两堆，你认为会发生什么？试试Marienbad游戏，找出赢的策略。游戏2投票假设有两个竞争议案A与B；3个议员，投票人1，2和3，他们投票决定是否通过这些议案。结局可能会有两个：要么通过A和B中的一个，要么议员们没有通过任何一项议案（延缓而代之以现行法律）。投票过程如下：首先，让议案A和B相互竞争；然后，竞争的获胜方与原法律相互竞争，为了简便，我们将原来的法律成为“都不赞成”（N）。在两轮投票中的每一轮，获多数的法案胜出。三个议员在可适用的选择中有如下偏好：投票人1：A＞N＞B投票人2：B＞A＞N投票人3：N＞A＞BA＞B：喜欢议案A甚于喜欢议案B感兴趣问题如果三个议员都“真实”投票，谁将胜出；如果存在“不真实”投票，那么谁将胜出第一轮，第二轮呢？游戏分析比较系统的分析方法：首先，注意到在第二轮投票中每个投票人有可能真实地投票。这是因为如果议员对不太喜欢的议案投赞成票，那就可能让他通过，因为这显然比阻止它通过更加糟糕（为什么？）。因此，如果A在第一轮中胜出，最终结局就是A，而如果B在第一轮胜出，最后结局是N。每个理性的议员都了解这点。所以，在第一轮关于A和B的竞争投票时，他们实际上是在A和N之间投票。因而，投票人1和投票人2在第一轮中投票给A，于是A最终被选中。思考策略投票和真实投票有什么不同？结局呢？游戏3囚徒困境两个囚徒，Calvin和Klein被怀疑犯罪而被逮捕拘押。地方检察官Kash分别同他们谈话，告诉他们，她或多或少有点证据证明他们有罪。但如果他们认罪的话，就可以使她的工作稍微容易一些（同时也帮助了他们自己）。她对每个人提供如下政策：“认罪，并为政府翻出证据来，并揭发另一个同伙——你将用不着服刑。当然，如果另外一个同伙也认罪的话，你的认罪价值将大大减少。出现这种情况，你们每个人将服刑5年。但是，如果你拒绝认罪，就要意识到我们将以另外一个同伙的招供而逮捕你，于是你将服刑15年。在我们不能够从你们任何一个那里得到认罪的情况下，我们将有足够的证据将你们送进监狱1年。”最古老的博弈论问题之一问题的表示形式：Calvin\klein认罪不认罪认罪5，50，15不认罪15，01，1上表中各项为囚禁期限。对于（认罪、不认罪）项的第一个数字表示Calvin认罪，而klein不认罪时分别对Calvin的判刑期限（0年）与对klein的判刑期限（15年）。由于这些都是囚禁期限，因此较小的数优于较大的数。游戏分析如果两个人合作，最好的结果就是（不认罪，不认罪）。问题是，在押期间，两人无法合作，只能看成两个独立的理性人。经过分析得到最后结果为（认罪，认罪）。思考1两个大国的军备竞赛（削减军费，增加军费）；争执的双方（离婚、劳务争端）等（请律师、不请律师）。思考2利用囚徒困境，说明个体理性和集体理性之间的矛盾。思考3看看下面的例子是不是囚徒困境？价格战，恶性广告竞争，初等和高等的应试教育.思考4在囚徒困境模型中，如果把服刑时间修改一下，会有什么结果？又在这个博弈中，如果嫌疑犯存在行动的先后顺序，会怎么样？博弈要素playersstrategies参与人或者局中人，局中人可以是个体，也可以是团体，自然；局中人是一个理性决策人：以自己的利益最大化作出行动选择。局中人可以是两个，也可以是多个，记I={1,2,…,n}策略，例如，乒乓球团体比赛的运动员出场顺序就是一个策略；这里所说的策略，是局中人在竞争中，为了对抗其他局中人所采取的一个完整的办法，并不是某一步采取的办法。例如，下象棋的“当头炮”，只能算是策略的一个组成部分，并非完整的策略。局中人所有的策略的集合，就构成了该局中人的策略集合，可以是有限的，也可以是无限的。用Si表示第i个局中人的策略集合。每个局中人都从自己的集合中选出一个策略，得到一个博弈结果，这样的每个局中人的策略放在一起，就构成一个局势。payoffs支付函数，或者叫赢得函数，表示可能的对局结果。支付函数定义在局势集合上的函数。用Hi表示第i个人的支付函数。对策模型（博弈模型）Ii),s(H,Ii,S,n,,2,1Iii对策过程每个局中人都从自己的策略集合中选出一个策略s(i),s(i)∈Si，就组成一个局势ni1i)n()2()1(Ss,,s,ss把局势带入每个人的支付函数中，获得Hi(s)。案例1有两个人决斗，这两个人从相距1的地方同时起步，迎面走向对方，只能前进，不能后退，他们在决斗开始后任何地点都可以开枪，每个人只有一发子弹，如果一个人开了枪而没有击中对方，那么他的对手知道他已用掉了仅有的一发子弹，就可以走到面对面的地方，然后开枪，一定击中对方，现开枪的当然可能先击中对方，但距离较远的时候击中的概率比较小，后开枪击中对方概率大，但是有可能先被对方击中。所以要选择合适的距离开枪。二人决斗模型（支付函数连续，多元函数表达）规定胜利者得到支付为1，败者支付为-1，双方同时开枪，都击中对方或者都没有击中对方的时候，支付都为0。分析局中人1的策略为x：距离x处开枪；局中人2的策略为y：距离y处开枪。策略集合分别为I={1，2}；局中人集合]1,0[y|yS]1,0[x|xS21策略集合1y0,1x0|)y,x(SS21局势集合xyS1S2011局势集合一个局势点局中人1的策略局中人2的策略支付函数yx)y(p21)]y(p1[1)y(p)1(yx)x(p)x(p)x(p)]x(p1)[1()]x(p1)[x(p1yx1)x(p2)]x(p1)[1()x(p1)y,x(H2222121211111局中人1xy)x(p21)]x(p1[1)x(p)1(xy)y(p)y(p)x(p)]y(p1)[1()]x(p1)[y(p1xy1)y(p2)]y(p1)[1()y(p1)y,x(H1111212122222局中人2案例2布什上校（支付离散，矩阵表达）在一场战斗中，布什上校有两个步兵团可以自由分派到一对地点（1,21,31,42,32,43,4);而萨达姆上校只有一个步兵团派往四个地点（1,2,3,4)的任何一处。如果一个团到达无人争夺的地点，那么它就赢得这一处；如果敌方一个团也来到同一地点，那么它们将进行战斗而陷入困境。赢可以获得一个单元效用；陷入困境则产生零效用。萨达姆＼布什1,21,31,42,32,43,410,10,10,11,21,21,220,11,21,20,10,11,231,20,11,20,11,20,141,21,20,11,20,10,1双支付矩阵占优策略型对策Calvin\klein认罪(a1)不认罪(a2)认罪(b1)5，50，15不认罪(b2)15，01，1案例分析囚徒困境如果Calvin是个理性的个体，他的策略有“认罪”和“不认罪”两种，如果他选择不认罪，Klein不管认罪不认罪，他的判刑都比Calvin年限少，故对Calvin不利。所以Calvin认为他的两个策略中，“认罪”策略比“不认罪”策略好。同样的分析，Klein也会认为“认罪”比“不认罪”策略好。所以，最后，两个囚徒的合理的博弈结果应该是“认罪”，“认罪”，各判5年。这里我们记：“认罪”优于“不认罪”b1﹥b2，a1﹥a2又记：H1(a1,b1)=5=a11H1(a1,b2)=15=a12H1(a2,b1)=0=a21H1(a2,b2)=1=a22则22211211aaaa1015512221121aa,aa即)2b,2a(1H)2b,1a(1H)1b,2a(1H)1b,1a(1H于是，得到如下定义注意：数字越小越优不管其他局中人选择怎样的策略，局中人i的策略si’盈利严格大于他的其他任何其他策略的盈利，即强优策略)s,s(H)s,'s(Hiiiiii对一切和都成立。isis则称策略si’强优于局中人i的所有其他策略。其中，s-i表示除了局中人i外的其他所有局中人的策略向量。在囚徒困境中,局中人1的策略a1=“认罪”，就是他的所有策略的强优策略；同理，局中人2的策略b1=“认罪”也是他的所有策略中的强优策略。所以，最后局势为（a1，b1）。思考1在博弈对策中，一个局中人如果存在强优策略，是否存在两个或者两个以上的强优策略？（利用定义判别）思考2分析案例2，布什上校和萨达姆上校是否分别存在强优策略？如果局中人i存在强优策略si’，那么他的其他策略si都称为强劣策略。对于局中人i来说，没有理由选择强劣策略。对于局中人i来说，并不是强优策略都存在，比如：1,30,73,53,7左右顶底局中人1局中人2弱优策略如果不管其他局中人选择怎样的策略，局中人i的策略si’盈利不小于他的其他任何其他策略的盈利，即)s,s(H)s,'s(Hiiiiii对一切和都成立。isis则称策略si’弱优于局中人i的所有其他策略。其中，s-i表示除了局中人i外的其他所有局中人的策略向量。1,30,73,53,7左右顶底局中人1局中人2强优策略和弱优策略统称优策略。非劣策略对于局中人i的策略si#和si*,若对于其他局中人的所有策略向量s-i，有)s,s(H)s,s(Hi#iii*ii而对于其他局中人的某些策略向量s1-i，有)s,s(H)s,s(Hi1#iii*ii则称si#为局中人i的劣策略。如果一个策略不是劣策略，则称为非劣策略。前面所讲的优策略是非劣策略的特殊类型。一般来说，局中人i有许多策略。下面两件事必有一件真:(1)可能存在一个优策略；（2）必然存在一个非劣策略。案例3（伯川德）价格竞争模型假设双寡头垄断市场中的两个公司都可以开出三个价格中的任何一个——高、中、低。不管哪个公司开出较低的价格就可以得到整个市场。如果两个公司开价相同，则他们将平分市场。他们的价格局势造成的收益矩阵如下：公司1\公司2高中低高6，60，100，8中10，05，50，8低8，08，04，4利用优策略概念，求解两个公司的最终局势（价格对）。分析由盈利矩阵可以观察出，对于两个公司，“高”价格策略劣于“中”价格策略，于是，每个公司都没有理由选择这个“差”策略。于是“剔除”这个策略，得到：公司1\公司2中低中5，50，8低8，04，4从这个新的盈利矩阵可以看出，对任何一家公司，“低”价格策略优于“中”价格策略，故最后两家公司的有效局势为（低，低）。思考1在一个没有品牌的市场（产品完全一样）旁边有一个价格低的小商贩，你认为顾客趋向如何？思考2举例分析两家相邻的食品店和折扣家电的商店的情况。案例4奥