簡單二人零和博弈的一種圖解法

馬贊甫，劉妍珺

（1.貴州財經大學 經濟研究所，貴州 貴陽 550004；2.貴州財經大學 數學與統(tǒng)計學院，貴州 貴陽 550004）

簡單二人零和博弈的一種圖解法

馬贊甫1，劉妍珺2

（1.貴州財經大學 經濟研究所，貴州 貴陽 550004；2.貴州財經大學 數學與統(tǒng)計學院，貴州 貴陽 550004）

利用等分量線及支付凸多邊形這兩個基本概念，以圖解方式確定簡單二人零和博弈（2×n或m×2）的納什均衡.這一方法與通常的圖解法是互補的，可率先確定持有多個純策略的局中人的均衡策略.

二人零和博弈；圖解；凸組合；等分量線

二人零和博弈是現(xiàn)實生活中常見的博弈形式，也是博弈論發(fā)展早期數學家特別感興趣的一類博弈模型.事實上，與有限零和博弈相聯(lián)系的最小最大值原理[1]在博弈論中占有極為重要的地位.

對于有限二人零和博弈混合戰(zhàn)略納什均衡的確定，一般是借助最小最大值原理，將之轉換為一個線性規(guī)劃問題，然后利用單純形方法確定最優(yōu)策略.而對于某局中人只有兩個純戰(zhàn)略的簡單的二人零和博弈，習慣上采用基于最小最大值原理的一般圖解法.一般圖解法簡單直觀，對于確定一個參與人的均衡戰(zhàn)略極為便利，早期的博弈論著作都對這一方法有所提及[2-3].

一般圖解法只能確定一個局中人的最優(yōu)策略，確切地說，只能確定純戰(zhàn)略個數為2的局中人的最優(yōu)策略，在此基礎上再以代數方法確定另一參與人的均衡策略.我們提出另外一種基于凸組合的互補方法，可率先確定純戰(zhàn)略個數大于2的局中人的最優(yōu)策略.另外，這一方法也可直接確定博弈的值.

1 二人零和博弈

考慮一個二人有限零和博弈模型.假設局中人1的純策略有m個，局中人2的純策略有n個，分別記局中人1、2的混合策略為

其中x1,…,xm,y1,…,yn≥0，分別滿足.當局中人1選擇第i個純戰(zhàn)略而局中人2選擇第j個純戰(zhàn)略時，局中人1的支付為aij，局中人2的支付為（-aij），i=1，…，m，j=1，…，n.該博弈可由如下支付矩陣A給出：

稱一個策略組合（X*，Y*）為納什均衡（Nash Equilibrium，N.E.），當且僅當X*∈argmXax{XTAY*}與Y*∈argmYax{X*TAY} 同時成立，此時稱v*=X*TAY*為博弈的值.

對于由A所給出的二人零和博弈，當m與n皆大于2的時候，確定均衡比較棘手，但對于兩者最小值為2的情形，有簡單的處理方法，即利用圖解法確定最優(yōu)策略.一般的對策論著作中都會介紹2×n或m×2型零和博弈的圖解法，基本思路是利用最小最大值原理，描繪最?。ɑ蜃畲螅┲登€，然后再求最小(或最大)值曲線的最高（或最低）點.我們稱這種方法為一般圖解法.

一般圖解法能直接確定雙戰(zhàn)略擁有者的最優(yōu)戰(zhàn)略，但兩個以上純戰(zhàn)略持有者的均衡戰(zhàn)略是以間接方式給出的.我們提出另外一種互補方法，能直接確定多戰(zhàn)略持有者的均衡戰(zhàn)略，該方法的理論基礎是最大等收益法則.

一般而言，若（X*，Y*）是純戰(zhàn)略均衡，則可根據最小最大值原理直接予以確定，若納什均衡（X*，Y*）不是純戰(zhàn)略均衡，則需滿足最大等收益法則.所謂最大等收益法則，即：如果

存在兩個非零分量＞0與＞0，則當局中人2選擇Y*時，局中人1的第i1、i2個純戰(zhàn)略所對應的期望支付必須都等于v*，且均不小于其它任意純戰(zhàn)略所帶來的期望支付；類似地，若

存在非零分量＞0與＞0，則當局中人1選擇X*時，局中人2的第j1、j2個純戰(zhàn)略也對應等量的最大的期望支付（-v*）.

利用最大等收益法則，可考慮一種凸組合圖解方法：在支付凸組合的基礎上，利用等分量線確定博弈的解與值.

2 凸組合圖解法

考慮一個由2×n階支付矩陣所定義的簡單零和博弈.設該博弈的納什均衡為（X*，Y*），所對應的博弈值為v*=X*TAY*.由于AY*是矩陣n個列向量的凸組合：

因此，當均衡戰(zhàn)略X*=(x*,1-x*) 滿足0＜x*＜1時，必有

則v*與向量AY*的任一分量值相等.這表明，均衡狀態(tài)對應凸組合圖形中的一個向量，該向量的兩個分量必須相等.

視支付矩陣A的每一列為二維坐標平面上的一個點，對這n個點做凸組合，得到一個凸多邊形，另，定義等分量線v1=v2，則等分量線與凸多邊形的位置關系無外乎相離與相交兩種情況.

1）凸多邊形位于等分量線同側.如圖1所示.在這種情況下，參與人1存在一個（弱）占優(yōu)策略，博弈有一個重復剔除占優(yōu)均衡.

圖1 等分量線與凸多邊形相離Fig.1 The separation set of iso-component line and convex polygon

2）等分量線與凸多邊形相交，在這種情況下存在混合戰(zhàn)略均衡，且坐標最小的一個交點給出博弈值及均衡策略.不妨考慮一個2×3的零和博弈，其一般形式如表1所示：

表1 2×3型零和博弈的一般形式Tab.1 The General Form of 2×3 Zero-Sum Game

可解得

另一方面，由于局中人2在均衡狀態(tài)下以零概率選擇純戰(zhàn)略R，因此有

就幾何位置而言，若支付點(a13,a23)T位于點(a11,a21)T及點(a12,a22)T所連直線

的上方①該線段必須是下降的，否則其上側端點必對應于參與人2的劣戰(zhàn)略，不可能出現(xiàn)于其混合戰(zhàn)略之中.因此，其它支付點當位于該線段所在直線上方.為防止出現(xiàn)意外情況，畫圖前最好先剔除劣戰(zhàn)略.，則必有

則局中人2選擇純戰(zhàn)略R對應的負支付滿足

或者說，給定局中人1的均衡戰(zhàn)略(x,1-x)T，相較純戰(zhàn)略R而言，局中人2選擇純戰(zhàn)略L或C將帶來更高的期望收益.如圖2所示，三角形的頂點L、C、R分別由支付矩陣的列向量1、2、3所確定，由于R點位于直線LC的上側，這一幾何位置關系使得均衡狀態(tài)下的局中人2必須以零概率選擇純戰(zhàn)略R.

進一步可證明，根據直線LC與等分量線交點N.E.的幾何位置可確定博弈值及均衡戰(zhàn)略組合.顯然，N.E.點可表示為三角形頂點L、C、R的一個凸組合，或者說，N.E.點坐標(e11,e21)T滿足如下條件：

圖2 等分量線與凸多邊形相交Fig.2 The intersection of iso-component line and convex polygon

無疑，均衡未必單一，甚至存在無窮多均衡的情況.比如，當支付列向量存在至少三點共線時，可能出現(xiàn)無窮多均衡.如圖3所示，支付點L、C、R共線，等分量線與直線LCR的交點N.E.存在無窮多的凸組合形式，此時有無窮多均衡.

以上考慮的是2×n型零和博弈的圖解法，相仿佛的，對于m×2型零和博弈，可先確定參與人1的均衡戰(zhàn)略.方法是視支付矩陣A的每一行為二維坐標平面上的一個點，對其進行凸組合得到一個凸多邊形，考慮等分量線與該凸多邊形坐標最大的一個交點，該交點確定了博弈的均衡.

圖3 無窮多均衡Fig.3 The infinite Nash Equilibrium

3 示例及結語

考慮一個2×n型的零和博弈.設參與人1有兩個純戰(zhàn)略：U、D，參與人2有三個純戰(zhàn)略：L、C、R；給定純戰(zhàn)略組合，參與人1的支付見表2.

表2 一個2×n型零和博弈Tab.2A 2×n Zero-Sum Game

圖4 2×n型零和博弈求解示意Fig.4The schematicdiagram for the 2×n zero-sum game

圖5 一般圖解法示意Fig.5The General graphic method diagram for the zero-sum game

再考慮一個m×2型的零和博弈.設參與人1有三個純戰(zhàn)略：U、M、D，參與人2有兩個純戰(zhàn)略：L、R；給定純戰(zhàn)略組合，參與人1的支付如表3所示.

本例中需要先確定局中人1的均衡策略，如前所述，均衡由等分量線與凸多邊形坐標最大的交點所決定.在圖6中，UM所在直線方程為17，與等分量線的交點為N.E.，博弈均衡由N.E.點給出，由于

表3 一個m×2型零和博弈Tab.3A m×2 Zero-Sum Game

圖6 m×2型零和博弈求解示意Fig.6The schematic diagram for the m×2 zero-sum game

總之，與一般圖解法一樣，凸組合方法可以確定簡單零和博弈的納什均衡及均衡的值，不同點在于凸組合方法首先確定的是多個純策略擁有者的混合策略，而一般圖解法確定的是僅擁有2個純策略的局中人的混合策略.因此，凸組合方法可說是一般圖解法的互補方法.

[1]John von Neumann.Zur Theorie der Gesellschaftsspiele[J].Mathematische Annalen,1928(100):295-300.

[2]J·麥克金賽.博弈論導引[M].北京:人民教育出版社,1960.

[3]王建華.對策論[M].北京:清華大學出版社,1986.

責任編輯：畢和平

A Graphic Method for the Simple Two-Person Zero-Sum Games

MA Zanfu1，LIU Yanjun2
（1.Institute of Economic Research，Guizhou University of Finance and Economics，Guiyang 550004，China；2.School of Mathematics and Statistics，Guizhou University of Finance and Economics，Guiyang 550004，China）

By the introduction of iso-component line and convex polygon,a graphic method was presented to solve sim?ple zero-sum two-person games.This approach,which is complementary to the general graphic method,can determine the Nash equilibrium strategy of the player who holds more pure strategies.

two-person zero-sum game；graphic method；convex combination；iso-component line

F 224.32

A

1674-4942（2012）03-0249-05

2012-02-27

教育部人文社科基金項目（12YJC790140）