《双人零和博弈》由会员分享，可在线阅读，更多相关《双人零和博弈（10页珍藏版）》请在金锄头文库上搜索。
1、一、双人零和博弈的概念零和博弈又称零和游戏，与非零和博弈相对，是博弈论的一个概 念，属非合作博弈，指参与博弈的各方，在严格竞争下，一方的收益 必然意味着另一方的损失，一方收益多少，另一方就损失多少，所以 博弈各方的收益和损失相加总和永远为“零”.双方不存在合作的可 能.用通俗的话来讲也可以说是：自己的幸福是建立在他人的痛苦之 上的，二者的大小完全相等，因而双方在决策时都以自己的最大利益 为目标，想尽一切办法以实现“损人利己”.零和博弈的结果是一方 吃掉另一方，一方的所得正是另一方的所失，整个社会的利益并不会 因此而增加一分.二、双人零和博弈的模型的建立建立双人零和博弈的模型，就是要根据对实际问
2、题的叙述确定参 与人（局中人）的策略集以及相应的收益矩阵（支付矩阵）.我们记 双人零和博弈中的两个局中人为 A和B;局中人A的策略集为 a ,a ,局中人B的策略集为b，,b ;c为局中人A采取策略a、 1m1n iji局中人B采取策略七时A的收益（这时局中人B的收益为-c）.则 收益矩阵见下表accc111121n策accc221222 n略acccmm1m 2mn那么下面我们通过例子来说明双人零和博弈模型的建立:例1甲、乙两名儿童玩猜拳游戏.游戏中双方同时分别或伸出拳 头（代表石头）、或手掌（代表布）、或两个手指（代表剪刀）.规则 是剪刀赢布，布赢石头，石头赢剪刀，赢者得一分若双方所出相同
3、， 算和局，均不得分.试列出对儿童甲的赢得矩阵.解 本例中儿童甲或乙均有三个策略:或出拳头，或出手掌，或出 两个手指，根据例子中所述规则，可列出对儿童甲的赢得矩阵见表 2.表2甲-一一_.乙石头布剪刀石头0-11布10-1剪刀-110例2从一张红牌和一张黑牌中随机抽取一张，在对B保密情况 下拿给A看，若A看到的是红牌，他可选择或掷硬币决定胜负，或让 B猜.若选择掷硬币，当出现正面，A赢p元，出现反面，输q元;若 让B猜，当B猜中是红牌，A输r元，反之B猜是黑牌，A赢s元. 若A看到的是黑牌，他只能让B猜.当B猜中是黑牌，A输u元，反之B猜是红牌，A赢t元，试确定A、8各自的策略，建立支付矩阵.
4、解因A的赢得和损失分别是B的损失和赢得，故属二人零和博 弈.为便于分析，可画出如图3的博弈树图.图3中，。为随机点，口分别为A和B的决策点，从图中看出A 的策略有掷硬币和让B猜两种，B的策略有猜红和猜黑两种，据此可 归纳出各种情况下A和B输赢值分析的表格，见表4.抽到红牌（1/2）抽到（1/2）正面（1/2）反面（1/2）猜红猜黑 八、猜红猜黑猜红猜黑掷硬币 让B猜P-rP s-q-r-qstt-U-U对表4中各栏数字可以这样来理解:因让A看到红牌时或掷硬币 或让B猜.若A决定选掷硬币这个策略，当出现正面，这时不管B猜 红或猜黑，A都赢p元;当出现反面，不管B猜红或猜黑，A都输q元. 同样A选
5、择让B猜的策略后，他的输赢只同B猜红或猜黑有关，而与掷硬币的正反面无关.又若抽到的牌是黑牌，A的决定只能让B猜， 因而掷硬币策略对A的胜负同样不起作用.考虑到抽牌时的红与黑的 概率各为1/2,掷硬币时出现正反面的概率也各为1/2,故当A采取“掷 硬币”策略，而B选择“猜红”策略时，A的期望赢得为：1 (11 V 11， 仁)p q 十一t-p - q + 2t) 2122 ) 2 42如-)+ 1 (一 r)1 +11 =1(-)22当入采取让8猜策略，B选择猜红”策略时，A的期望赢得为:122 )相应可求得其他策略对A的期望赢得值.由此可列出本例的收益矩 阵，见表5.表5猜 红猜黑掷硬币4
6、(p - q + 2t)4 (p 一 q + 2u )让B猜2 (- r +1) - u)三、双人零和博弈的求解定理1 (极小极大定理)在零和博弈中，对于给定的支付矩阵U， 如果存在混合战略b * = ( b 1*，a m * )和b * = ( b 1*，b n * )以111222及一个常数v满足，对任意j有栏a b i*小，对任意的i有咒a b j* Wij 1ij 2i=1j=1v，那么战略组合(b 1*，b 2*)为该博弈的Nash均衡.其中，v为参与人1在均衡中所得到的期望支付，亦称该博弈的值.这个极小极大定理，其基本思想就是:参与人1考虑到对方使自 己支付最小的最优反应，从中选择
7、使自己最好的策略.参与人2也遵 循同样的思路，这样才能满足Nash均衡的互为最优反应的条件.这样 我们就可以得到双人零和博弈Nash均衡的计算方法了，如以下定理定理2对于给定的零和博弈，如果博弈的值v大于0，则博弈的Nash均衡（G 1*，. 2*）为以下对偶线性规划问题的解Min &i i=1s.t. a p N1 （j=1,，n）i = 1p N0 （i=1,，m）i和Max &jj=1s.t. a q W1 （i=1,，m）j=1qj N0 （j=1,，n）其中，Nash均衡支付11v =pqiji=1j=1Nash均衡战略c * = （vp，vp，vp ）， c * = （vq，vq，
8、vq ）11im21jn由于此定理只适用于v大于0的情形，因此对于v小于等于0的 情形，该定理所给出的方法需做适当的修改.命题如果支付矩阵u=a、的每个元素都大于0,即七0,那么 博弈的值大于0,即v0.定理3如果支付矩阵U = (a，.)是由U= (a )的每个元素都加上 j mxnij mxn一个常数c得到，即a jj = a + c，那么支付矩阵U和U,所对应的零和 博弈的Nash均衡战略相同，博弈的值相差c.根据以上定理，可以得到如下求解一般零和博弈Nash均衡的方 法：(1) 若支付矩阵U中的所有元素都大于零，则可以直接根据定 理进行计算;若支付矩阵U中有小于0的元素，可以通过加上一
9、个常数 使它们都大于0,然后再根据定理进行计算.(2) 求解定理中的两个对偶线性规划问题.下面通过实例来说明如何求解双人零和博弈的Nash均衡.例3求解下图中战略式博弈的Nash均衡.参与人2LMRU参与人1CD2，-21，-13，-32，-23，-31，-14，-42，-22，-2通通过求解对偶线性规划问题求零和博弈的Nash均衡解根据前面的介绍，可知该博弈的支付矩阵为f2 1 3)U= 2 3 1、4 2 2不难发现，该博弈的支付矩阵U=()的每个元素都大于0,即 匕0,那么博弈的值大于0，即v0.设参与人1和参与人2的混合战 略分别是a =( vp ,vp ,vp)和。=(vq,vq ,
10、vq)，利用对偶线性规划 11232123求解方法求解该战略式博弈的Nash均衡，构造规划问题如下.Min p + p + p s.t. 2p + 2p + 4p 1p + 3 p + 2 p 13 p + p + 2 p 1p N0, p N0, p N0123和Max q + q + q st. 2q + q + 3q W12q + 3q + q W14q + 2q + 2q W 1q N0, q N0, q N0123求解第一个规划问题，得到p =1/4, p =1/4, p =0,参与人1的 123支付v=2.因此，参与人1的混合战略a 1* = (1/2,1/2,0).同理，对 对偶
11、问题求解，得到q =0， q =1/4, q =1/4,参与人2的损失V=2,因 123此参与人的混合战略a 了 = (0,1/2,1/2).所以，该博弈存在一个混合 战略 Nash 均衡(1/2,1/2,0) (0,1/2,1/2)，).例4求解下图中的战略式博弈的Nash均衡.参与人2参与人12，-2-2,21，-1-1，11,-10，03，-30 ,02，-2LM R通过求解对偶线性规划问题求零和博弈的Nash均衡解该博弈的支付矩阵为在上树支付矩阵U=(七)3X3中，12 0, a21 0.为了利用对偶线性规f 2-21)U=-1103v J02 /划模型求解博弈的解，构造支付矩阵U =
12、 (a )，其中a = a +c.j 3 x3ij ij令c=2,那么新构造的支付矩阵为f4 0 3U =13 25 2 4k设参与人1和参与人2的混合战略分别是。=(vp , vp , vp)1123和a =(vq , vq vq ,),v为原博弈的值，v为新博弈的值，且 v=v+2,利用对偶线性规划求解方法求解新战略式博弈的Nash均衡， 构造规划问题如下.Min p + p + p S.t. 4p + p + 5p 13 p + 2 p N13 p + 2 p + 4 p N1p N0, p N0, p N0 123Max q + q + q S.t. 4qi + 3q3 W1q + 3q + 2q W】5q + 2q + 4q W 1q N0, q N0, q N0123通过求解对偶问题，得到p =0, p =3/13, p =2/13,参与人1的 123支付 v=13/5, q =1/13, q =4/13, q =0,参与人 2 的损失 v=13/5. 123因此，参与人1的混合战略ai* = (0,3/5,2/5),参与人2的混合战 略。了 = (1/5,4/5,0)，原博弈的值v= v-2=3/5.所以，博弈存在一个 混合战略 Nash 均衡(0,3/5,2/5)，(1/5,4/5,0).
