双人零和博弈

一、双人零和博弈的概念

零和博弈又称零和游戏，与非零和博弈相对，是博弈论的一个概

念，属非合作博弈，指参与博弈的各方，在严格竞争下，一方的收益

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

博弈各方的收益和损失相加总和永远为“零”.双方不存在合作的可

能.用通俗的话来讲也可以说是:自己的幸福是建立在他人的痛苦之

上的，二者的大小完全相等，因而双方在决策时都以自己的最大利益

为目标，想尽一切办法以实现“损人利己”.零和博弈的结果是一方

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

因此而增加一分.

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

建立双人零和博弈的模型，就是要根据对实际问题的叙述确定参

与人（局中人）的策略集以及相应的收益矩阵（支付矩阵）.我们记

双人零和博弈中的两个局中人为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 甲、乙两名儿童玩猜拳游戏.游戏中双方同时分别或伸出拳

头（代表石头）、或手掌（代表布）、或两个手指（代表剪刀）.规则

是剪刀赢布，布赢石头，石头赢剪刀，赢者得一分.若双方所出相同，

算和局，均不得分.试列出对儿童甲的赢得矩阵.

解 本例中儿童甲或乙均有三个策略:或出拳头，或出手掌，或出

两个手指，根据例子中所述规则，可列出对儿童甲的赢得矩阵见表

2.

表2

甲 乙 石头 布 剪刀

石头 0 -1 1

布 1 0 -1

剪刀 -1 1 0

例2 从一张红牌和一张黑牌中随机抽取一张，在对B保密情况

下拿给A看，若A看到的是红牌，他可选择或掷硬币决定胜负，或让

B猜.若选择掷硬币，当出现正面，A赢p元，出现反面，输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的策略有猜红和猜黑两种，据此可

归纳出各种情况下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中各栏数字可以这样来理解:因让A看到红牌时或掷硬币

或让B猜.若A决定选掷硬币这个策略，当出现正面，这时不管B猜

红或猜黑，A都赢p元;当出现反面，不管B猜红或猜黑，A都输q元.

同样A选择让B猜的策略后，他的输赢只同B猜红或猜黑有关，而与

3

掷硬币的正反面无关.又若抽到的牌是黑牌，A的决定只能让B猜，

因而掷硬币策略对A的胜负同样不起作用.考虑到抽牌时的红与黑的

概率各为1/2，掷硬币时出现正反面的概率也各为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，

如果存在混合战略=（，…）和=（，…）以



111

**



1m1



222

n

及一个常数v满足，对任意j有≥v，对任意的i有≤



a

ij1





a

ij2



i1

j1

***

*

m

i

*

n

j

*

v，那么战略组合（，）为该博弈的Nash均衡.其中，v为参



1

**



2

与人1在均衡中所得到的期望支付，亦称该博弈的值.

这个极小极大定理，其基本思想就是:参与人1考虑到对方使自

4

己支付最小的最优反应，从中选择使自己最好的策略.参与人2也遵

循同样的思路，这样才能满足Nash均衡的互为最优反应的条件.这样

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

定理2 对于给定的零和博弈，如果博弈的值v大于0，则博弈的

Nash均衡（，）为以下对偶线性规划问题的解



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均衡战略



11im

*

(vp,,vp,,vp)

，



21jn

*

(vq,,vq,vq)

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

情形，该定理所给出的方法需做适当的修改.

5

命题 如果支付矩阵U=的每个元素都大于0,即＞0,那么

(a)a

ijmxnij

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

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

'

(a)

'

ij

mxn

(a)

ijmxn

一个常数c得到，即，那么支付矩阵U和U所对应的零和

aac

'

ij

ij

'

博弈的Nash均衡战略相同，博弈的值相差c.

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

法:

(1) 若支付矩阵U中的所有元素都大于零，则可以直接根据定

理进行计算;若支付矩阵U中有小于0的元素,可以通过加上一个常数

使它们都大于0,然后再根据定理进行计算.

(2) 求解定理中的两个对偶线性规划问题.

下面通过实例来说明如何求解双人零和博弈的Nash均衡.

例3 求解下图中战略式博弈的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

通

通过求解对偶线性规划问题求零和博弈的Nash均衡

解 根据前面的介绍，可知该博弈的支付矩阵为



213



U=



231



422



6

不难发现，该博弈的支付矩阵U=的每个元素都大于0，即



a

ij

3x3

a

ij

>0,那么博弈的值大于0，即v>0.设参与人1和参与人2的混合战

略分别是=（）和=（）,利用对偶线性规划



1

vp,vp,vpvq,vq,vq

123123



2

求解方法求解该战略式博弈的Nash均衡，构造规划问题如下.

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

求解第一个规划问题，得到=1/4, =1/4, =0,参与人1的

p

1

p

2

p

3

支付v=2.因此，参与人1的混合战略=（1/2,1/2,0）.同理，对



1

*

对偶问题求解，得到=0，=1/4, =1/4,参与人2的损失v=2,因

qq

12

q

3

此参与人的混合战略=（0,1/2,1/2）.所以，该博弈存在一个混合



2

*

战略Nash均衡（（1/2,1/2,0）（0,1/2,1/2），）.

例4 求解下图中的战略式博弈的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

通过求解对偶线性规划问题求零和博弈的Nash均衡

解 该博弈的支付矩阵为



221



U=



110



302



在上树支付矩阵U=中，<0, <0.为了利用对偶线性规

(a)

ij3x3

aa

1221

划模型求解博弈的解，构造支付矩阵U=,其中=+c.

''

(a)

'

ij

3x3

a

令c=2，那么新构造的支付矩阵为



403



U=

'



132



524



ijij

a

设参与人1和参与人2的混合战略分别是=（vp, vp, vp）



11

'''

2

3

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



22

''''

1

3

v=v+2，利用对偶线性规划求解方法求解新战略式博弈的Nash均衡，

'

构造规划问题如下.

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的混合战略=（0,3/5,2/5）, 参与人2 的混合战



1

*

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



2

*'

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

9