雙人零和博弈

一、雙人零和博弈的概念

零和博弈又稱零和游戲，與非零和博弈相對，是博弈論的一個概

念，屬非合作博弈，指參與博弈的各方，在嚴格競爭下，一方的收益

必然意味著另一方的損失，一方收益多少，另一方就損失多少，所以

博弈各方的收益和損失相加總和永遠為“零”.雙方不存在合作的可

能.用通俗的話來講也可以說是:自己的幸福是建立在他人的痛苦之

上的，二者的大小完全相等，因而雙方在決策時都以自己的最大利益

為目標，想盡一切辦法以實現(xiàn)“損人利己”.零和博弈的結(jié)果是一方

吃掉另一方，一方的所得正是另一方的所失，整個社會的利益并不會

因此而增加一分.

二、雙人零和博弈的模型的建立

建立雙人零和博弈的模型，就是要根據(jù)對實際問題的敘述確定參

與人（局中人）的策略集以及相應的收益矩陣（支付矩陣）.我們記

雙人零和博弈中的兩個局中人為A和B;局中人A的策略集為

a,…,a,局中人B的策略集為b,…,b;c為局中人A采取策略a、

11

mni

ij

局中人B采取策略b時A的收益（這時局中人B的收益為- c）.則

jij

收益矩陣見下表

表1

局中人B 策 略

局中人A

b b … b

1

2

n

1

策

略 … … … …

a

1

a

2

a c c … c

mm1m2mn

c c … c

1112

1n

c c … c

2122

2n

那么下面我們通過例子來說明雙人零和博弈模型的建立:

例1 甲、乙兩名兒童玩猜拳游戲.游戲中雙方同時分別或伸出拳

頭（代表石頭）、或手掌（代表布）、或兩個手指（代表剪刀）.規(guī)則

是剪刀贏布，布贏石頭，石頭贏剪刀，贏者得一分.若雙方所出相同，

算和局，均不得分.試列出對兒童甲的贏得矩陣.

解 本例中兒童甲或乙均有三個策略:或出拳頭，或出手掌，或出

兩個手指，根據(jù)例子中所述規(guī)則，可列出對兒童甲的贏得矩陣見表

2.

表2

甲 乙 石頭 布 剪刀

石頭 0 -1 1

布 1 0 -1

剪刀 -1 1 0

例2 從一張紅牌和一張黑牌中隨機抽取一張，在對B保密情況

下拿給A看，若A看到的是紅牌，他可選擇或擲硬幣決定勝負，或讓

B猜.若選擇擲硬幣，當出現(xiàn)正面，A贏p元，出現(xiàn)反面，輸q元;若

讓B猜，當B猜中是紅牌，A輸r元，反之B猜是黑牌，A贏s元.

若A看到的是黑牌，他只能讓B猜.當B猜中是黑牌，A輸u元，反

2

之B猜是紅牌，A贏t元，試確定A、B各自的策略，建立支付矩陣.

解 因A的贏得和損失分別是B的損失和贏得，故屬二人零和博

弈.為便于分析，可畫出如圖3的博弈樹圖.

圖3中，○為隨機點，□分別為A和B的決策點，從圖中看出A

的策略有擲硬幣和讓B猜兩種，B的策略有猜紅和猜黑兩種，據(jù)此可

歸納出各種情況下A和B輸贏值分析的表格，見表4.

圖3

抽到紅牌抽到黑球

1/2

○

1/2

讓B猜

□

擲硬幣

讓B猜

○

正面反面猜紅

1/21/2

p-q-rst-u

□□

猜黑

猜紅猜黑

表4

B 抽到紅牌（1/2） 抽到（1/2）

A

擲硬幣 P t -u P -q -q

讓B猜 -r t -u s -r s

正面（1/2） 反面（1/2） 猜 猜

猜紅 猜黑 猜紅 猜黑

紅 黑

對表4中各欄數(shù)字可以這樣來理解:因讓A看到紅牌時或擲硬幣

或讓B猜.若A決定選擲硬幣這個策略，當出現(xiàn)正面，這時不管B猜

紅或猜黑，A都贏p元;當出現(xiàn)反面，不管B猜紅或猜黑，A都輸q元.

同樣A選擇讓B猜的策略后，他的輸贏只同B猜紅或猜黑有關，而與

3

擲硬幣的正反面無關.又若抽到的牌是黑牌，A的決定只能讓B猜，

因而擲硬幣策略對A的勝負同樣不起作用.考慮到抽牌時的紅與黑的

概率各為1/2，擲硬幣時出現(xiàn)正反面的概率也各為1/2,故當A采取“擲

硬幣”策略，而B選擇“猜紅”策略時，A的期望贏得為:

111

??

1

1

p?q

+=

??

p?q?2t

t

??

222

??

2

4

當A采取讓B猜策略，B選擇“猜紅”策略時，A的期望贏得為:

111

??

1

1

??

????

?r??r

+=

t

??

?r?t

222

??

2

2

相應可求得其他策略對A的期望贏得值.由此可列出本例的收益矩

陣，見表5.

表5

猜 紅 猜 黑

擲硬幣

讓B猜

11

????

p?q?2tp?q?2u

44

11

????

?r?ts?u

22

三、雙人零和博弈的求解

定理1（極小極大定理）在零和博弈中，對于給定的支付矩陣U，

如果存在混合戰(zhàn)略=（，…）和=（，…）以

??

111

**

?

1m1

???

222

n

及一個常數(shù)v滿足，對任意j有≥v，對任意的i有≤

?

a

ij1

?

?

a

ij2

?

i?1

j?1

***

*

m

i

*

n

j

*

v，那么戰(zhàn)略組合（，）為該博弈的Nash均衡.其中，v為參

?

1

**

?

2

與人1在均衡中所得到的期望支付，亦稱該博弈的值.

這個極小極大定理，其基本思想就是:參與人1考慮到對方使自

4

己支付最小的最優(yōu)反應，從中選擇使自己最好的策略.參與人2也遵

循同樣的思路，這樣才能滿足Nash均衡的互為最優(yōu)反應的條件.這樣

我們就可以得到雙人零和博弈Nash均衡的計算方法了，如以下定理

定理2 對于給定的零和博弈，如果博弈的值v大于0，則博弈的

Nash均衡（，）為以下對偶線性規(guī)劃問題的解

?

1

**

?

2

Min

?

p

i

i?1

m

s.t. ≥1 (j=1,…,n)

?

ap

iji

i?1

m

≥0 (i=1,…,m)

p

i

和

Max

?

q

j

j?1

n

s.t. ≤1 (i=1,…,m)

?

aq

ijj

j?1

n

≥0 (j=1,…,n)

q

j

其中，Nash均衡支付

v??

11

mn

ij

??

pq

i?1j?1

Nash均衡戰(zhàn)略

?

11im

*

?(vp,?,vp,?,vp)

，

?

21jn

*

?(vq,?,vq,?vq)

由于此定理只適用于v大于0的情形，因此對于v小于等于0的

情形，該定理所給出的方法需做適當?shù)男薷?/span>.

5

命題 如果支付矩陣U=的每個元素都大于0,即＞0,那么

(a)a

ijmxnij

博弈的值大于0,即v＞0.

定理3 如果支付矩陣U=是由U=的每個元素都加上

'

(a)

'

ij

mxn

(a)

ijmxn

一個常數(shù)c得到，即，那么支付矩陣U和U所對應的零和

a?a?c

'

ij

ij

'

博弈的Nash均衡戰(zhàn)略相同，博弈的值相差c.

根據(jù)以上定理，可以得到如下求解一般零和博弈Nash均衡的方

法:

(1) 若支付矩陣U中的所有元素都大于零，則可以直接根據(jù)定

理進行計算;若支付矩陣U中有小于0的元素,可以通過加上一個常數(shù)

使它們都大于0,然后再根據(jù)定理進行計算.

(2) 求解定理中的兩個對偶線性規(guī)劃問題.

下面通過實例來說明如何求解雙人零和博弈的Nash均衡.

例3 求解下圖中戰(zhàn)略式博弈的Nash均衡.

參與人2

L M R

U

參與人1 C

D

2，-2 1，-1 3，-3

2，-2 3，-3 1，-1

4，-4 2，-2 2，-2

通

通過求解對偶線性規(guī)劃問題求零和博弈的Nash均衡

解 根據(jù)前面的介紹，可知該博弈的支付矩陣為

??

213

??

U=

??

231

??

422

??

6

不難發(fā)現(xiàn)，該博弈的支付矩陣U=的每個元素都大于0，即

??

a

ij

3x3

a

ij

>0,那么博弈的值大于0，即v>0.設參與人1和參與人2的混合戰(zhàn)

略分別是=（）和=（）,利用對偶線性規(guī)劃

?

1

vp,vp,vpvq,vq,vq

123123

?

2

求解方法求解該戰(zhàn)略式博弈的Nash均衡，構(gòu)造規(guī)劃問題如下.

Min ｛｝

p?p?p

123

s.t. ≥1

2p?2p?4p

123

≥1

p?3p?2p

123

≥1

3p?p?2p

123

≥0,≥0,≥0

p

1

p

2

p

3

和

Max ｛｝

q?q?q

123

s.t. ≤1

2q?q?3q

123

≤1

2q?3q?q

123

≤1

4q?2q?2q

123

≥0,≥0,≥0

qq

12

q

3

求解第一個規(guī)劃問題，得到=1/4, =1/4, =0,參與人1的

p

1

p

2

p

3

支付v=2.因此，參與人1的混合戰(zhàn)略=（1/2,1/2,0）.同理，對

?

1

*

對偶問題求解，得到=0，=1/4, =1/4,參與人2的損失v=2,因

qq

12

q

3

此參與人的混合戰(zhàn)略=（0,1/2,1/2）.所以，該博弈存在一個混合

?

2

*

戰(zhàn)略Nash均衡（（1/2,1/2,0）（0,1/2,1/2），）.

例4 求解下圖中的戰(zhàn)略式博弈的Nash均衡.

7

參與人2

L M R

U

參與人1 C

D

2，-2 -2,2 1，-1

-1，1 1,-1 0，0

3，-3 0 ,0 2，-2

通過求解對偶線性規(guī)劃問題求零和博弈的Nash均衡

解 該博弈的支付矩陣為

??

2?21

??

U=

??

?110

??

302

??

在上樹支付矩陣U=中，<0, <0.為了利用對偶線性規(guī)

(a)

ij3x3

aa

1221

劃模型求解博弈的解，構(gòu)造支付矩陣U=,其中=+c.

''

(a)

'

ij

3x3

a

令c=2，那么新構(gòu)造的支付矩陣為

??

403

??

U=

'

??

132

??

524

??

ijij

a

設參與人1和參與人2的混合戰(zhàn)略分別是=（vp, vp, vp）

?

11

'''

2

3

和=（vq, vq vq,）,v為原博弈的值，v為新博弈的值，且

?

22

''''

1

3

v=v+2，利用對偶線性規(guī)劃求解方法求解新戰(zhàn)略式博弈的Nash均衡，

'

構(gòu)造規(guī)劃問題如下.

Min ｛｝

p?p?p

123

s.t. ≥1

4p?p?5p

123

≥1

3p?2p

23

≥1

3p?2p?4p

123

8

≥0, ≥0, ≥0

p

1

p

2

p

3

Max ｛｝

q?q?q

123

s.t. ≤1

4q?3q

13

≤1

q?3q?2q

123

≤1

5q?2q?4q

123

≥0,≥0,≥0

qq

12

q

3

通過求解對偶問題，得到=0，=3/13, =2/13,參與人1的

p

1

p

2

p

3

支付v=13/5, =1/13, =4/13, =0,參與人2的損失v=13/5.

''

qq

12

q

3

因此，參與人1的混合戰(zhàn)略=（0,3/5,2/5）, 參與人2 的混合戰(zhàn)

?

1

*

略=(1/5,4/5,0)，原博弈的值v= v-2=3/5.所以，博弈存在一個

?

2

*'

混合戰(zhàn)略Nash均衡（（0,3/5,2/5），(1/5,4/5,0)）.

9