双人零与博弈

《双人零与博弈》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、双人零和博弈的概念零和博弈又称零和游戏，与非零和博弈相对，是博弈论的一个概念，属非合作博弈，指参与博弈的各方，在严格竞争下，一方的收益必然意味着另一方的损失，一方收益多少，另一方就损失多少，所以博弈各方的收益和损失相加总和永远为“零”.双方不存在合作的可能.用通俗的话来讲也可以说是:自己的幸福是建立在他人的痛苦之上的，二者的大小完全相等，因而双方在决策时都以自己的最大利益为目标，想尽一切办法以实现“损人利己”.零和博弈的结果是一方吃掉另一方，一方的所得正是另一方的所失，整个社会的利益并不会因此而增加一分.二、双人零和博弈的模型的建立建立双人零和博弈的模型，就是要根据对实际问题

2、的叙述确定参与人（局中人）的策略集以及相应的收益矩阵（支付矩阵）.我们记双人零和博弈中的两个局中人为A和B;局中人A的策略集为a,…,a,局中人B的策略集为b,…,b;c为局中人A采取策略a、局中人B采取策略b时A的收益（这时局中人B的收益为-c）.则收益矩阵见下表表1局中人B局中人A策略bb…b9策略aa…acc…ccc…c………cc…c那么下面我们通过例子来说明双人零和博弈模型的建立:例1甲、乙两名儿童玩猜拳游戏.游戏中双方同时分别或伸出拳头（代表石头）、或手掌（代表布）、或两个手指（代表剪刀）.规则是剪刀赢布，布赢石头，石头赢剪刀，赢者得一分.若双方所出相同，算和局，均不得

3、分.试列出对儿童甲的赢得矩阵.解本例中儿童甲或乙均有三个策略:或出拳头，或出手掌，或出两个手指，根据例子中所述规则，可列出对儿童甲的赢得矩阵见表2.表2甲乙石头布剪刀石头布剪刀0-1110-1-110例2从一张红牌和一张黑牌中随机抽取一张，在对B保密情况下拿给A看，若A看到的是红牌，他可选择或掷硬币决定胜负，或让B猜.若选择掷硬币，当出现正面，A赢p元，出现反面，输q元;若让B猜，当B猜中是红牌，A输r元，反之B猜是黑牌，A赢9s元.若A看到的是黑牌，他只能让B猜.当B猜中是黑牌，A输u元，反之B猜是红牌，A赢t元，试确定A、B各自的策略，建立支付矩阵.解因A的赢得和损失分别是B

4、的损失和赢得，故属二人零和博弈.为便于分析，可画出如图3的博弈树图.图3中，○为随机点，□分别为A和B的决策点，从图中看出A的策略有掷硬币和让B猜两种，B的策略有猜红和猜黑两种，据此可归纳出各种情况下A和B输赢值分析的表格，见表4.图3表4BA抽到红牌（1/2）抽到（1/2）正面（1/2）反面（1/2）猜红猜黑猜红猜黑猜红猜黑掷硬币让B猜P-rPs-q-r-qstt-u-u对表4中各栏数字可以这样来理解:因让A看到红牌时或掷硬币或让B猜.若A决定选掷硬币这个策略，当出现正面，这时不管B猜红或猜黑，A都赢p元;当出现反面，不管B猜红或猜黑，A都输q元.同样A选择让B猜的策略后，他的

5、输赢只同B猜红或猜黑有关，而与9掷硬币的正反面无关.又若抽到的牌是黑牌，A的决定只能让B猜，因而掷硬币策略对A的胜负同样不起作用.考虑到抽牌时的红与黑的概率各为1/2，掷硬币时出现正反面的概率也各为1/2,故当A采取“掷硬币”策略，而B选择“猜红”策略时，A的期望赢得为:+=当A采取让B猜策略，B选择“猜红”策略时，A的期望赢得为:+=相应可求得其他策略对A的期望赢得值.由此可列出本例的收益矩阵，见表5.表5猜红猜黑掷硬币让B猜三、双人零和博弈的求解定理1（极小极大定理）在零和博弈中，对于给定的支付矩阵U，如果存在混合战略=（，…）和=（，…）以及一个常数v满足，对任意j有≥v，

6、对任意的i有≤v，那么战略组合（，）为该博弈的Nash均衡.其中，v为参与人1在均衡中所得到的期望支付，亦称该博弈的值.这个极小极大定理，其基本思想就是:9参与人1考虑到对方使自己支付最小的最优反应，从中选择使自己最好的策略.参与人2也遵循同样的思路，这样才能满足Nash均衡的互为最优反应的条件.这样我们就可以得到双人零和博弈Nash均衡的计算方法了，如以下定理定理2对于给定的零和博弈，如果博弈的值v大于0，则博弈的Nash均衡（，）为以下对偶线性规划问题的解Mins.t.≥1(j=1,…,n)≥0(i=1,…,m)和Maxs.t.≤1(i=1,…,m)≥0(j=1,…,n)其中

7、，Nash均衡支付Nash均衡战略，由于此定理只适用于v大于0的情形，因此对于v小于等于0的情形，该定理所给出的方法需做适当的修改.9命题如果支付矩阵U=的每个元素都大于0,即＞0,那么博弈的值大于0,即v＞0.定理3如果支付矩阵U=是由U=的每个元素都加上一个常数c得到，即，那么支付矩阵U和U所对应的零和博弈的Nash均衡战略相同，博弈的值相差c.根据以上定理，可以得到如下求解一般零和博弈Nash均衡的方法:(1)若支付矩阵U中的所有元素都大于零，则可以直接根据定理进行计算;若