1、一、雙人零和博弈的概念零和博弈又稱零和游戲，與非零和博弈相對，是博弈論的一個概念，屬非合作博弈，指參與博弈的各方，在嚴格競爭下，一方的收益必然意味著另一方的損失，一方收益多少，另一方就損失多少，所以博弈各方的收益和損失相加總和永遠為“零”.雙方不存在合作的可能.用通俗的話來講也可以說是：白己的幸福是建立在他人的痛苦之上的，二者的大小完全相等，因而雙方在決策時都以白己的最大利益為目標，想盡一切辦法以實現“損人利己”.零和博弈的結果是一方吃掉另一方，一方的所得正是另一方的所失，整個社會的利益并不會因此而增加一分.二、雙人零和博弈的模型的建立建立雙人零和博弈的模型，就是要根據對實際問題的敘述確定參與

2、人（局中人）的策略集以及相應的收益矩陣（支付矩陣）.我們記雙人零和博弈中的兩個局中人為A和B;局中人A的策略集為a”,am,局中人B的策略集為加，,bn;cj為局中人A采取策略a”局中人B采取策略bj時A的收益（這時局中人B的收益為-Cj）.則收益矩陣見下表aiC11c12Cin策a?C21C22C2n略.amCm1Cm2Cmn那么下面我們通過例子來說明雙人零和博弈模型的建立：例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元，試確定AB各白的策略，建立支付矩陣.解因A的贏得和損失分別是B的損失和贏得，故屬二人零和博弈.為便于分析，可畫

4、出如圖3的博弈樹圖.圖3中，。為隨機點，口分別為A和B的決策點，從圖中看出A的策略有擲硬幣和讓B猜兩種，B的策略有猜紅和猜黑兩種，據此可歸納出各種情況下A和B輸贏值分析的表格，見表4.抽到紅牌1/2抽到黑球1/2讓B猜擲硬幣t-u讓B猜猜黑B抽到紅牌（1/2）抽到(1/2)止面（1/2）及面（1/2）猜猜A猜紅猜黑猜紅猜黑紅里八、擲硬幣PP-q-qt-u讓B猜-rs-rst-u對表4中各欄數字可以這樣來理解：因讓A看到紅牌時或擲硬幣或讓B猜.若A決定選擲硬幣這個策略，當出現正面，這時不管B猜紅或猜黑，A都贏p元；當出現反面，不管B猜紅或猜黑，A都輸q元.同樣A選擇讓B猜的策略后，他的輸贏只同B

5、猜紅或猜黑有關，而與擲硬幣的正反面無關.又若抽到的牌是黑牌，A的決定只能讓B猜，因而擲硬幣策略對A的勝負同樣不起作用.考慮到抽牌時的紅與黑的概率各為1/2，擲硬幣時出現正反面的概率也各為1/2,故當A采取“擲硬幣”策略，而B選擇“猜紅”策略時，A的期望贏得為：2t1 1p-q+1t=1pq2 2224當A采取讓B猜策略，B選擇“猜紅”策略時，A的期望贏得為：r+1t=】22相應可求得其他策略對A的期望贏得值.由此可列出本例的收益矩陣，見表5.表5猜紅猜黑擲硬幣讓B猜1pq2t41一rt21cpq2u41-su2三、雙人零和博弈的求解定理1（極小極大定理）在零和博弈中，對于給定的支付矩陣U,如果

6、存在混合戰略1*=（ILlb和2*=（21，20*）以m*n.*及一個常數v滿足，對任意j有aij1>v，對任意的i有aij2J<v,那么戰略組合（1*,2*）為該博弈的Nash均衡.其中，v為參與人1在均衡中所得到的期望支付，亦稱該博弈的值.這個極小極大定理，其基本思想就是：參與人1考慮到對方使白己支付最小的最優反應，從中選擇使白己最好的策略.參與人2也遵循同樣的思路，這樣才能滿足Nash均衡的互為最優反應的條件.這樣我們就可以得到雙人零和博弈Nash均衡的計算方法了，如以下定理定理2對于給定的零和博弈，如果博弈的值v大于0,則博弈的Nash均衡(，2*)為以下對偶線性規劃問題的

7、解Minmpji1s.t.aijPi>1(j=1,n)i1Pia0(i=1,m)和Maxqjj1s.t.aoqj<1(i=1,m)j1qj>0(j=1,n)其中，Nash均衡支付11vm-PiqjNash均衡戰略*1(VP1,vpi,vpm),2(vq，vqj,vq”)由于此定理只適用于v大于0的情形，因此對于v小于等于0的情形，該定理所給出的方法需做適當的修改.命題如果支付矩陣U=(aij)mxn的每個元素都大于0,即aj>0,那么博弈的值大于0,即v>0.定理3如果支付矩陣U'=(a'ij)mxn是由U=(aj)mxn的每個元素都加上一個常數c

8、得到，即a'ijaijc,那么支付矩陣U和U'所對應的零和博弈的Nash均衡戰略相同，博弈的值相差c.根據以上定理，可以得到如下求解一般零和博弈Nash均衡的方法：(1)若支付矩陣U中的所有元素都大于零，則可以直接根據定理進行計算；若支付矩陣U中有小于0的元素,可以通過加上一個常數使它們都大于0,然后再根據定理進行計算.(2)求解定理中的兩個對偶線性規劃問題.下面通過實例來說明如何求解雙人零和博弈的Nash均衡.例3求解下圖中戰略式博弈的Nash均衡.參與人2LMRU參與人1CD2,-21,-13,-32,-23,-31,-14,-42,-22,-2通通過求解對偶線性規劃問題求

9、零和博弈的Nash均衡解根據前面的介紹，可知該博弈的支付矩陣為213U=231不難發現，該博弈的支付矩陣U=aj3x3的每個元素都大于0,即aj>0,那么博弈的值大于0,即v>0.設參與人1和參與人2的混合戰略分別是1=(VP1,VP2,VP3)和2=(vq,vq2,vq3)，利用對偶線性規劃求解方法求解該戰略式博弈的Nash均衡，構造規劃問題如下.MinPiP2P3s.t.2Pi2P24P3>1P13P22P3>13PiP22P3>1PlA0,P2A0,P3A0和Maxq1q2q3s.t.2q1q23q3<12q13q2q3<14q2q22q3<

10、;1qia0,q2a0,q3a0求解第一個規劃問題，得到P1=1/4,p2=1/4,P3=0,參與人1的支付v=2.因此，參與人1的混合戰略1*=(1/2,1/2,0).同理，對對偶問題求解，得到q=0,q2=1/4,q3=1/4,參與人2的損失V=2,因此參與人的混合戰略2*=(0,1/2,1/2).所以，該博弈存在一個混合戰略Nash均衡(1/2,1/2,0)(0,1/2,1/2),).例4求解下圖中的戰略式博弈的Nash均衡.參與人2U參與人1CD2,-2-2,21,-1-1,11,-10,03,-30,02,-2R通過求解對偶線性規劃問題求零和博弈的Nash均衡解該博弈的支付矩陣為22

11、1U=110a21<0.為了利用對偶線性規在上樹支付矩陣U=(aij)3x3中，a12<0,劃模型求解博弈的解，構造支付矩陣U=(a'j)3x3,其中a'j=aj+c.4 令c=2,那么新構造的支付矩陣為03U'=1325 24設參與人1和參與人2的混合戰略分別是1=(v'pi,v'p2,vp3)和2=(v'q，v02v'q3,),v為原博弈的值，v'為新博弈的值，且v'=v+2,利用對偶線性規劃求解方法求解新戰略式博弈的Nash均衡,構造規劃問題如下.Min-LP1P2P3s.t.4p1P25P3>13P22P3>13Pi2P24P3>1Pl>0,P2>0,P3>0Maxqiq2q3S.t.4q13q3<1qi3q22q3<15qi2q24q3<1qi>0,q2A0,q3>0通過求解對偶問題，得到Pi=0,P2=3/13,