一、雙人零和博弈的概念零和博弈又稱零和游戲，與非零和博弈相對，是博弈論的一個概念，屬非合作博弈，指參與博弈的各方，在嚴(yán)格競爭下，一方的收益必然意味著另一方的損失，一方收益多少，另一方就損失多少，所以博弈各方的收益和損失相加總和永遠(yuǎn)為“零”.雙方不存在合作的可能.用通俗的話來講也可以說是：自己的幸福是建立在他人的痛苦之上的，二者的大小完全相等，因而雙方在決策時都以自己的最大利益為目標(biāo)，想盡一切辦法以實現(xiàn)“損人利己”.零和博弈的結(jié)果是一方吃掉另一方，一方的所得正是另一方的所失，整個社會的利益并不會因此而增加一分.二、雙人零和博弈的模型的建立建立雙人零和博弈的模型，就是要根據(jù)對實際問題的敘述確定參與人（局中人）的策略集以及相應(yīng)的收益矩陣（支付矩陣）.我們記雙人零和博弈中的兩個局中人為A和B；局中人A的策略集為a,…,a,局中人B的策略集為b，…,b;c為局中人A采取策略a、1m1niji

局中人B采取策略b時A的收益（這時局中人B的收益為-c）.則jij收益矩陣見下表

acC12???cin策acc???c221222n略????????????acc???cmmlm2mn那么下面我們通過例子來說明雙人零和博弈模型的建立:例1甲、乙兩名兒童玩猜拳游戲.游戲中雙方同時分別或伸出拳頭（代表石頭）、或手掌（代表布）、或兩個手指（代表剪刀）.規(guī)則是剪刀贏布，布贏石頭，石頭贏剪刀，贏者得一分.若雙方所出相同，算和局，均不得分.試列出對兒童甲的贏得矩陣.解本例中兒童甲或乙均有三個策略:或出拳頭，或出手掌，或出兩個手指，根據(jù)例子中所述規(guī)則，可列出對兒童甲的贏得矩陣見表2.表2審' 一乙石頭布剪刀石頭0-11布10-1剪刀-110例2從一張紅牌和一張黑牌中隨機(jī)抽取一張，在對B保密情況下拿給A看，若A看到的是紅牌，他可選擇或擲硬幣決定勝負(fù)，或讓B猜.若選擇擲硬幣，當(dāng)出現(xiàn)正面，A贏p元，出現(xiàn)反面，輸q元;若讓B猜，當(dāng)B猜中是紅牌，A輸r元，反之B猜是黑牌，A贏s元.若A看到的是黑牌，他只能讓B猜.當(dāng)B猜中是黑牌，A輸u兀，反之B猜是紅牌，A贏t元，試確定A、B各自的策略，建立支付矩陣.解因A的贏得和損失分別是B的損失和贏得，故屬二人零和博弈.為便于分析，可畫出如圖3的博弈樹圖.圖3中，O為隨機(jī)點，□分別為A和B的決策點，從圖中看出A的策略有擲硬幣和讓B猜兩種，B的策略有猜紅和猜黑兩種，據(jù)此可歸納出各種情況下A和B輸贏值分析的表格，見表4.p-q-rst-u表4\B抽到紅牌（1/2）抽到（1/2）\正面（1/2）反面（1/2）猜猜A\猜紅猜黑猜紅猜黑紅黑八、、擲硬幣PP-q-qt-U讓B猜-rs-rst-u對表4中各欄數(shù)字可以這樣來理解:因讓A看到紅牌時或擲硬幣或讓B猜.若A決定選擲硬幣這個策略，當(dāng)出現(xiàn)正面，這時不管B猜紅或猜黑，A都贏p元;當(dāng)出現(xiàn)反面，不管B猜紅或猜黑，A都輸q元.同樣A選擇讓B猜的策略后，他的輸贏只同B猜紅或猜黑有關(guān)，而與擲硬幣的正反面無關(guān).又若抽到的牌是黑牌，A的決定只能讓B猜，因而擲硬幣策略對A的勝負(fù)同樣不起作用.考慮到抽牌時的紅與黑的概率各為1/2,擲硬幣時出現(xiàn)正反面的概率也各為1/2，故當(dāng)A采取“擲硬幣”策略，而B選擇“猜紅”策略時，A的期望贏得為：+2t=4(p-q+2t)當(dāng)A采取讓B猜策略，B選擇“猜紅”策略時，A的期望贏得為:-f-（-r）+-（-r）］+-1=-（-r+1）2（2 2丿22相應(yīng)可求得其他策略對A的期望贏得值.由此可列出本例的收益矩陣，見表5.表5猜 紅猜黑擲硬幣—(p-q+2t)4—(p-q+2u)4讓B猜1(-r+1)1(s-u)22三、雙人零和博弈的求解定理1（極小極大定理）在零和博弈中，對于給定的支付矩陣U，如果存在混合戰(zhàn)略Q*=（b1*，…bm*）和Q*=（Q1*，…Qn*）以111222及一個常數(shù)V滿足,對任意j有￡abi*$v,對任意的i有—bj*Wij1 ij2i=1 j=1v，那么戰(zhàn)略組合（b*，b*）為該博弈的Nash均衡.其中，v為參12與人1在均衡中所得到的期望支付，亦稱該博弈的值.這個極小極大定理，其基本思想就是:參與人1考慮到對方使自

己支付最小的最優(yōu)反應(yīng)，從中選擇使自己最好的策略.參與人2也遵循同樣的思路，這樣才能滿足Nash均衡的互為最優(yōu)反應(yīng)的條件.這樣我們就可以得到雙人零和博弈Nash均衡的計算方法了，如以下定理定理2對于給定的零和博弈，如果博弈的值v大于0,則博弈的Nash均衡（。*，.*）為以下對偶線性規(guī)劃問題的解12Min另pii=1s.t.s.t.遲ap上1（j=l,…,n）s.t.s.t.ijii=1p20（i=l,…，m）iMax工qjj=1工aqW1（i=1,…,m）ijjj=1q20（j=1,…，n）j其中，Nash均衡支付11v= =瓦p 工qiji=1 j=1Nash均衡戰(zhàn)略b*=（vp，…，vp，…，vp），b*=（vq，…，vq，…vq）1 1 i m 2 1 jn由于此定理只適用于v大于0的情形，因此對于v小于等于0的情形，該定理所給出的方法需做適當(dāng)?shù)男薷?

命題如果支付矩陣U=(a)的每個元素都大于0,即a〉0,那么ijmxnij博弈的值大于0,即v>0.定理3如果支付矩陣U'=(a;.)是由U=(a)的每個元素都加上ijmxnijmxn一個常數(shù)C得到，即a'=a+c，那么支付矩陣U和U‘所對應(yīng)的零和ijij博弈的Nash均衡戰(zhàn)略相同，博弈的值相差c.根據(jù)以上定理，可以得到如下求解一般零和博弈Nash均衡的方法:若支付矩陣U中的所有元素都大于零，則可以直接根據(jù)定理進(jìn)行計算;若支付矩陣U中有小于0的元素，可以通過加上一個常數(shù)使它們都大于0,然后再根據(jù)定理進(jìn)行計算.求解定理中的兩個對偶線性規(guī)劃問題.下面通過實例來說明如何求解雙人零和博弈的Nash均衡.例3求解下圖中戰(zhàn)略式博弈的Nash均衡.參與人2參與人12，-21，-13，參與人12，-21，-13，-32，-23，-31，-14，-42，-22，-2LMRUCD通通過求解對偶線性規(guī)劃問題求零和博弈的Nash均衡解根據(jù)前面的介紹，可知該博弈的支付矩陣為‘213、U=231<422>

不難發(fā)現(xiàn)，該博弈的支付矩陣U二()的每個元素都大于0,即ij3x3a〉0,那么博弈的值大于0，即v〉0.設(shè)參與人1和參與人2的混合戰(zhàn)ij略分別是b=(vp,vp,vp)和b=(vq,vq,vq)，利用對偶線性規(guī)劃11232123求解方法求解該戰(zhàn)略式博弈的Nash均衡，構(gòu)造規(guī)劃問題如下.Min{p+p+p}123s.t.2p+2p+4p上1123p+3p+2p上11233p+p+2p上11 2 3p$0,p$0,p上0123Max{q+q+q}123S.t.2q+q+3qW11 2 32q+3q+qW11 2 34q+2q+2qW1123$0,q$0,$0,q$0,2q$03求解第一個規(guī)劃問題，得到p=1/4,p=1/4,p=0,參與人1的123支付v=2.因此，參與人1的混合戰(zhàn)略b*=(1/2,1/2,0).同理，對1對偶問題求解，得到q=0，q=1/4,q=1/4,參與人2的損失V=2,因1 2 3此參與人的混合戰(zhàn)略b*=(0,1/2,1/2).所以，該博弈存在一個混合2戰(zhàn)略Nash均衡((1/2,1/2,0)(0,1/2,1/2),).例4求解下圖中的戰(zhàn)略式博弈的Nash均衡.參與人2參與人12，-2-2,2參與人12，-2-2,21，-1-1，11,-10，03，-30,02，-2LMR通過求解對偶線性規(guī)劃問題求零和博弈的Nash均衡解該博弈的支付矩陣為'2-21、U=-1 1 0a〈0.為了利用對偶線性規(guī)21<302>a〈0.為了利用對偶線性規(guī)21在上樹支付矩陣U=(a)中，a〈0,ij3x3 12劃模型求解博弈的解，構(gòu)造支付矩陣U'=(a')，其中a'=a+C.ij3x3 ijij令C=2,那么新構(gòu)造的支付矩陣為'403、U'=132<524丿設(shè)參與人1和參與人2的混合戰(zhàn)略分別是b=(v'p,v'p,v'p)1 1 2 3和b=(v'q,v'qv'q,),v為原博弈的值，v'為新博弈的值，且2 1 2 3v'=v+2,利用對偶線性規(guī)劃求解方法求解新戰(zhàn)略式博弈的Nash均衡,構(gòu)造規(guī)劃問題如下Min{p+p+p}123s.t.4p+p+5p上11 2 33p+2p上1233p+2p+4p上1p$0, p$0, p$0123Max{q+q+q}123S.t.4q+3qW113q+3q+2qW11235q+2q+4qW1123q$0,q$0,q上0123通過求解對偶問題，得到p=0,