(数学建模教材)7第七章对策论

第七章 对策论

§1 引言

社会及经济的发展带来了人与人之间或团体之间的竞争及矛盾，应用科学的方法来 解决这样的问题开始于 17 世纪的科学家，如 C.，Huygens 和 W.，Leibnitz 等。现代对 策论起源于 1944 年 J.，V on Neumann 和 O.，Morgenstern 的著作《Theory of Games and Economic Behavior 》。

对策论亦称竞赛论或博弈论。是研究具有斗争或竞争性质现象的数学理论和方法。 一般认为，它既是现代数学的一个新分支，也是运筹学中的一个重要学科。对策论发展 的历史并不长，但由于它所研究的现象与人们的政治、经济、军事活动乃至一般的日常 生活等有着密切的联系，并且处理问题的方法又有明显特色。所以日益引起广泛的注意。

在日常生活中，经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对 抗性质的行为称为对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目 标和利益。为了达到各自的目标和利益，各方必须考虑对手的各种可能的行动方案，并 力图选取对自己最为有利或最为合理的方案。对策论就是研究对策行为中斗争各方是否 存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。 §2 对策问题

对策问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的 努力而是各方所采取的策略的综合结果。

先考察一个实际例子。

例 1（囚徒的困境） 警察同时逮捕了两人并分开关押，逮捕的原因是他们持有大 量伪币，警方怀疑他们伪造钱币，但没有找到充分证据，希望他们能自己供认，这两个 人都知道：如果他们双方都不供认，将被以持有大量伪币罪被各判刑 18 个月；如果双 方都供认伪造了钱币，将各被判刑 3 年；如果一方供认另一方不供认，则供认方将被从 宽处理而免刑，但另一方面将被判刑 7 年。将嫌疑犯 A 、 B 被判刑的几种可能情况列 于表 1。

表 1

表 1 中每对数字表示嫌疑犯 A 、B 被判刑的年数。如果两名疑犯均担心对方供认并希 望受到最轻的惩罚，最保险的办法自然是承认制造了伪币。

从这一简单实例中可以看出对策现象中包含有的几个基本要素。 2.1 对策的基本要素

（i ）局中人 在一个对策行为（或一局对策）中，有权决定自己行动方案的对策参加者，称为局 中人。通常用 I 表示局中人的集合．如果有 n 个局中人，则 I = {1,2,L , n }。一般要求 一个对策中至少要有两个局中人。在例 1 中，局中人是 A 、B 两名疑犯。

（ii ）策略集 一局对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个策略。参 加对策的每一局中人 i ， i ∈ I ，都有自己的策略集 S i 。一般，每一局中人的策略集中 至少应包括两个策略。

-154-

嫌疑犯 B

供认

不供认 嫌疑犯 A

供认

不供认

（3，3） （0，7） （7，0） （1.5，1.5）

（iii ）赢得函数（支付函数）

在一局对策中，各局中人所选定的策略形成的策略组称为一个局势，即若 s i 是第 i 个局中人的一个策略，则 n 个局中人的策略组

s = (s 1 , s 2 ,L , s n )

就是一个局势。全体局势的集合 S 可用各局中人策略集的笛卡尔积表示，即

S = S 1 ? S 2 ?L ? S n

当局势出现后，对策的结果也就确定了。也就是说，对任一局势， s ∈ S ，局中人 i 可以得到一个赢得 H i (s ) 。显然， H i (s ) 是局势 s 的函数，称之为第 i 个局中人的赢 得函数。这样，就得到一个向量赢得函数 H (s ) = (H 1 (s ),L , H n (s )) 。

本节我们只讨论有两名局中人的对策问题，其结果可以推广到一般的对策模型中 去。

2.2 零和对策（矩阵对策） 零和对策是一类特殊的对策问题。在这类对策中，只有两名局中人，每个局中人都

只有有限个策略可供选择。在任一纯局势下，两个局中人的赢得之和总是等于零，即双 方的利益是激烈对抗的。

设局中人Ⅰ、Ⅱ的策略集分别为 S 1 = {α1 ,L ,αm }， S 2 = {β1 ,L , βn } 当局中人Ⅰ选定策略αi 和局中人Ⅱ选定策略 β j 后，就形成了一个局势 (αi , β j ) ，可见 这样的局势共有 mn 个。对任一局势 (αi , β j ) ，记局中人Ⅰ的赢得值为 a ij ，并称

? a 11 'a a 12 a 1n / L

L L L

∞ a a A = ' 2n ∞ 21

22

' L ≤a m 1

L ∞ a mn ?

L a m 2 ' ∞ 为局中人Ⅰ的赢得矩阵（或为局中人Ⅱ的支付矩阵）。由于假定对策为零和的，故局中 人Ⅱ的赢得矩阵就是 - A 。

当局中人Ⅰ、Ⅱ和策略集 S 1 、 S 2 及局中人Ⅰ的赢得矩阵 A 确定后，一个零和对策 就给定了，零和对策又可称为矩阵对策并可简记成

G = {S 1 , S 2 ; A } 。

例 2

设有一矩阵对策 G = {S 1 , S 2 ; A } ，其 中 S 1 = {α1 ,α2 ,α3} ，

S 2 = {β1 , β2 , β3 , β4 } ，

? 12 - 6 2 0 30 18 - 10

- 22/ ∞ A = ' 14 10 '

'≤- 6 ∞ 16 ∞?

从 A 中可以看出，若局中人Ⅰ希望获得最大赢利 30，需采取策略α1 ，但此时若局

中人Ⅱ采取策略 β4 ，局中人Ⅰ非但得不到 30，反而会失去 22。为了稳妥，双方都应考 虑到对方有使自己损失最大的动机，在最坏的可能中争取最好的结果，局中人Ⅰ采取策 略α1、α2、α3 时，最坏的赢得结果分别为

-155-

min{12,-6,30,-22} = -22 min{14,2,18,10} = 2 min{-6,0,-10,16} = -10

其中最好的可能为 max{-22,2,-10} = 2 。如果局中人Ⅰ采取策略 α2 ，无论局中人Ⅱ

采取什么策略，局中人Ⅰ的赢得均不会少于 2。

局中人Ⅱ采取各方案的最大损失为 max{12,14,-6} = 14 ， max{-6,2,0} = 2 ，

max{30,18,-10} = 30 ，和 max{-22,10,16} = 16 。当局中人Ⅱ采取策略 β2 时，其损

失不会超过 2。注意到在赢得矩阵中，2 既是所在行中的最小元素又是所在列中的最大 元素。此时，只要对方不改变策略，任一局中人都不可能通过变换策略来增大赢得或减 少损失，称这样的局势为对策的一个稳定点或稳定解。

定义 1 设 f ( x , y ) 为一个定义在 x ∈ A 及 y ∈ B 上的实值函数，如果存在 x *∈ A ，

y *∈ B ，使得对一切 x ∈ A 和 y ∈ B ，有

f ( x , y *) ≤ f ( x *, y *) ≤ f ( x *, y )

则称 ( x *, y *) 为函数 f 的一个鞍点。

定义 2 设 G = {S 1 , S 2 ; A } 为矩阵 对策，其 中 S 1 = {α1 ,α2 ,L ,αm } ， S 2 = {β1 , β2 ,L , βn }， A = (a ij )m ?n 。若等式

max min a ij = min max a ij = a i * j *

（1）

i j j i

成立，记V G = a i * j * ，则称V G 为对策 G 的值，称使（1）式成立的纯局势 (αi * , β j * )

为

对策 G 的鞍点或稳定解，赢得矩阵中与 (αi * , β j * ) 相对应的元素 a i * j * 称为赢得矩阵的鞍 点，αi * 与 β j * 分别称为局中人Ⅰ与Ⅱ的最优纯策略。

给定一个对策 G ，如何判断它是否具有鞍点呢？为了回答这一问题，先引入下面

定理 1 设 G = {S 1, S 2 ; A } ，记 μ = max min a ij ， ν = - min max a ij ，则必有

i

j

j

i

μ +ν ≤ 0 。

证明 ν = max min(-a ij ) ，易见 μ 为Ⅰ的最小赢得，ν 为Ⅱ的最小赢得，由于 G j i

是零和对策，故 μ +ν ≤ 0 必成立。

定理 2 零和对策 G 具有稳定解的充要条件为 μ +ν = 0 。 证明：（充分性）由 μ 和ν 的定义可知，存在一行例如 p 行，μ 为 p 行中的最小元 素，且存在一列例如 q 列， -ν 为 q 列中的最大元素。故有

a pq ≥ μ 且 a pq ≤ -ν

又因 μ +ν = 0 ，所以 μ = -ν ，从而得出 a pq = μ ， a pq 为赢得矩阵的鞍点，(α p , βq ) 为 G 的稳定解。

（必要性）若 G 具有稳定解 (α p , βq ) ，则 a pq 为赢得矩阵的鞍点。故有

μ = max min ≥ min = a pq

a ij a pj i j

j -ν = min max ≤ max = a pq a ij a iq j i i

-156-

从而可得 μ +ν ≥ 0 ，但根据定理 1， μ +ν ≤ 0 必成立，故必有 μ +ν = 0 。

上述定理给出了对策问题有稳定解（简称为解）的充要条件。当对策问题有解时， 其解可以不唯一，当解不唯一时，解之间的关系具有下面两条性质：

性质 1 无差别性。 即若 (α , β ) 与 (α , β ) 是对策

G 的两个解， 则必有 i 1 j 1 i 2 j 2 a i j 1 1 = a i j 。 2 2

性质 2 可交换性。即若 (α , β ) 和 (α , β ) 是对策 G 的两个解，则 (α , β ) 和

i 1 j 1 i 2 j 2 i 1 j 2 (α , β ) 也是解。

i 2 j 1 §3 零和对策的混合策略

具有稳定解的零和问题是一类特别简单的对策问题，它所对应的赢得矩阵存在鞍 点，任一局中人都不可能通过自己单方面的努力来改进结果。然而，在实际遇到的零和 对策中更典型的是 μ +ν ≠ 0 的情况。由于赢得矩阵中不存在鞍点，此时在只使用纯策 略的范围内，对策问题无解。下面我们引进零和对策的混合策略。

设局中人Ⅰ用概率 x i 选用策略 αi ，局中人Ⅱ用概率 y j 选用策略 β j ，

m

∑ x i n

= ∑ y j

= 1 ，记 x = (x 1

,L , x ) ， y = ( y 1

,L , y n

)

T

T

，则局中人Ⅰ的期望赢得为

m

i =1

j =1

E (x , y ) = x T Ay 。

记

*

*

S ：策略

α1 ,L ,αm

S ：策略

β1 ,L , βn

1 2 x 1 ,L , x m

y 1 ,L , y n

概率 概率

分别称 S *

与

S *

为局中人Ⅰ和Ⅱ的混合策略。 1 2 下面简单地记

m

S = {(x 1 ,L , x m ) | x i ≥ 0, i = 1,L , m ; ∑ x * T

= 1} ， 1

i i = 1

n

S = {(

y 1 ,L , y n ) | y j ≥ 0, j = 1,L , n ; ∑ y = 1} *

T

2 j j =1

定义 4 若存在 m 维概率向量 x 和 n 维概率向量 y ，使得对一切 m 维概率向量 x 和 n 维概率向量 y 有

x Ay = max x T Ay = min x Ay

x y

则称 (x , y ) 为混合策略对策问题的鞍点。

定理 3 设 x ∈ S

*

，

y ∈ S

*

，则

(x , y ) 为 G = {S , S ; A } 的解的充要条件是： 1 2 1 2

? n ?∑ a y ≤ x T

Ay , i = 1,2,L , m ij j ? j =1 ? m

?∑

a x ≥ x Ay , j = 1,2,L , n ?? i =1 ij i 定理 4 任意混合策略对策问题必存在鞍点，即必存在概率向量 x 和 y ，使得：

-157-

x T

Ay = max min x T Ay = min max x T Ay 。

x

y

y

x

使用纯策略的对策问题（具有稳定解的对策问题）可以看成使用混合策略的对策问 题的特殊情况，相当于以概率 1 选取其中某一策略，以概率 0 选取其余策略。

例 3 A 、B 为作战双方， A 方拟派两架轰炸机Ⅰ和Ⅱ去轰炸 B 方的指挥部，轰 炸机Ⅰ在前面飞行，Ⅱ随后。两架轰炸机中只有一架带有炸弹，而另一架仅为护航。轰 炸机飞至 B 方上空，受到 B 方战斗机的阻击。若战斗机阻击后面的轰炸机Ⅱ，它仅受 Ⅱ的射击，被击中的概率为 0.3(Ⅰ来不及返回攻击它)。若战斗机阻击Ⅰ，它将同时受 到两架轰炸机的射击，被击中的概率为 0.7。一旦战斗机未被击中，它将以 0.6 的概率 击毁其选中的轰炸机。请为 A 、B 双方各选择一个最优策略，即：对于 A 方应选择哪 一架轰炸机装载炸弹？对于 B 方战斗机应阻击哪一架轰炸机？

解 双方可选择的策略集分别是

S A = {α1 ,α2 }，α1 ：轰炸机Ⅰ装炸弹，Ⅱ护航

α2 ：轰炸机Ⅱ装炸弹，Ⅰ护航

S B = {β1 , β2 }， β1 ：阻击轰炸机Ⅰ

β2 ：阻击轰炸机Ⅱ

赢得矩阵 R = (a ij )2?2 ，a ij 为 A 方采取策略αi 而 B 方采取策略 β j 时，轰炸机轰炸

B 方指挥部的概率，由题意可计算出： a 11 = 0.7 + 0.3(1 - 0.6) = 0.82

= 1 ， a 21 = 1

= 0.3 + 0.7(1 - 0.6) = 0.58

a 12 a 22 即赢得矩阵

R = ?

0.82 1 /

' ∞

1 0.58?

≤ 易求得 μ = max min a ij = 0.82 ，ν = - min max a ij = -1 。由于 μ +ν ≠ 0 ，矩阵

i j R 不存在鞍点，应当求最佳混合策略。

j i 现设 A 以概率 x 1 取策略 α1 、以概率 x 2 取策略 α2 ； B 以概率 y 1 取策略 β1 、以概 率 y 2 取策略 β2 。

先从 B 方来考虑问题。 B 采用 β1 时， A 方轰炸机攻击指挥部的概率期望值为

E (β1 ) = 0.82x 1 + x 2 ，而 B 采用 β2 时， A 方轰炸机攻击指挥部的概率的期望值为 E (β2 ) = x 1 + 0.58x 2 。若 E (β1 ) ≠ E (β2 ) ，不妨设 E (β1 ) < E (β2 ) ，则 B 方必采用 β1 以减少指挥部被轰炸的概率。故对 A 方选取的最佳概率 x 1 和 x 2 ，必满足：

?0.82x 1 + x 2 = x 1 + 0.58x 2

?

?x 1 + x 2 = 1

即

?a 11 x 1 + a 21 x 2 = a 12 x 1 + a 22 x 2 ?

?x 1 + x 2 = 1

-158-

由此解得 x 1 = 0.7 ， x 2 = 0.3 。

同样，可从 A 方考虑问题，得

?0.82 y 1 + y 2 ? y 1 + y 2 = 1

= y 1 + 0.58 y 2

?

即

?a 11 y 1 + a 12 y 2 = a 21 y 1 + a 22 y 2 ? y 1 + y 2 = 1

并解得 y 1 = 0.7 ， y 2 = 0.3 。 B 方指挥部被轰炸的概率的期望值V G = 0.874 。 记

零和对策 G 的解集为 T (G ) ，下面三个定理是关于对策解集性质的主要结果：

定理 5 设有两个零和对策

G 1 = {S 1, S 2 ; A 1}， G 2 = {S 1, S 2 ; A 2} 其中 A 1 = {a ij }， A 2 = {a ij + L } ， L 为任一常数。则

?

（i ）V G = V G + L 2 1

（ii ） T (G 1 ) = T (G 2 ) 定理 6 设有两个零和对策

G 1 = {S 1 , S 2 ; A } ， G 2 = {S 1 , S 2 ;αA } 其中α > 0 为任一常数。则

（i ）V = αV G 2 G

1

（ii ） T (G 1 ) = T (G 2 )

T

定理 7 设 G = {S 1 , S 2 ; A } 为一零和对策，且 A = - A 为反对称矩阵（亦称这种对 策为对称对策）。则

（i ）V G = 0

（ii ） T 1 (G ) = T 2 (G ) 其中 T 1 (G ) 和 T 2 (G ) 为局中人Ⅰ和Ⅱ的最优策略集。

§4 零和对策的线性规划解法

当 m > 2 且 n > 2 时，通常采用线性规划方法求解零和对策问题。 局中人Ⅰ选择混合策略 x 的目的是使得

n

x Ay = max min x T Ay = max min x T A (∑ y e ) j j x y x y

j =1

n

∑ E j y j

j =1

= max min x

y

T

其中 e j 为只有第 j 个分量为 1 而其余分量均为零的单位向量， E j = x Ae j 。记

-159-

n n u ≡ E k = min E j ，由于 ∑ y j = 1 ， min ∑ E j y j

在 y k = 1 ， y j = 0( j ≠ k ) 时达到最 j Y j =1

j =1

小值 u ，故 x 应为线性规划问题

max u

? m ?∑ a ij x i ≥ u , j = 1,2,L , n (即E j

≥

E ) ? i =1

? m ?∑ x i = 1 （2）

s.t. ? i =1

?x i ≥ 0, i = 1,2,L , m ? ?

的解。 同理， y 应为线性规划

min v

n

? ?∑ a ij y j ? j =

1 ≤ v , i = 1,2,L , m ? n

?∑ y j = 1

（3）

s.t. ? j =1

? y ≥ 0, j = 1,2,L , n j ? ??

的解。由线性规划知识，（2）与（3）互为对偶线性规划，它们具有相同的最优目标函

数值。

不妨设 u > 0 ，作变换

x i

x ' = ， i = 1,2,L , m i

u

则线性规划问题（2）化为：

m

min ∑ x 'i

i =1

? m

?∑ a ij x 'i ≥ 1, j = 1,2,L , n s.t. ? i =1 ?

?x 'i ≥ 0, i = 1,2,L , m

同理，作变换

y

=

j

，

y ' j = 1,2,L , n

j v

则线性规划问题（3）化为：

-160-

m

max ∑ y 'i

i =1

n

? ?∑ a ij y ' j ≤ 1, i = 1,2,L , m ? j =1

s.t. ? y ' ≥ 0, j = 1,2,L , n ? j

例 4 在一场敌对的军事行动中，甲方拥有三种进攻性武器 A 1 , A 2 , A 3 ，可分别用 于摧毁乙方工事；而乙方有三种防御性武器 B 1 , B 2 , B 3 来对付甲方。据平时演习得到的 数据，各种武器间对抗时，相互取胜的可能如下：

A 1 对

B 1 A 2 对 B 1 A 3 对 B 1 2：1； 3：7； 3：1； A 1 对 B 2 A 2 对 B 2 A 3 对 B 2 3：1； 3：2； 1：4； A 1 对 B 3 1：2； A 2 对 B 3 1：3；

A 3 对

B 3 2：1 解 先分别列出甲、乙双方的赢得的可能性矩阵，将甲方矩阵减去乙方矩阵的对应

元素，得零和对策时甲方的赢得矩阵如下：

1/ 3 1/ 2

1/ 5

- 3 / 5 - 1/ 3/

? A = '- 2 / 5

-1/ 2∞

' '≤ ∞

∞?

1/ 2 1/ 3 编写程序如下：

clear

a=[1/3,1/2,-1/3;-2/5,1/5,-1/2;1/2,-3/5,1/3];b=10; a=a+b*ones(3); %把赢得矩阵的每个元素变成大于0的数

[x0,u]=linprog(ones(3,1),-a',-ones(3,1),[],[],zeros(3,1)); x=x0/u,u=1/u-b

[y0,v]=linprog(-ones(3,1),a,ones(3,1),[],[],zeros(3,1)); y=y0/(-v),v=1/(-v)-b

解得 x = (0.5283,0, 0.4717)T

， y = (0, 0.3774, 0.6226)T

， u = -0.0189 ，故乙 方有利。

下面我们使用式（2）和（3），利用 LINGO 编程求例 4 的解。LINGO 程序如下：

model: sets:

player1/1..3/:x; player2/1..3/:y;

game(player1,player2):c; endsets data:

ctrl=?; !ctrl 取1求局中人1的策略，ctrl 取0求局中人2的策略; c=0.3333333 0.5 -0.3333333 -0.4 0.2 -0.5

0.5 -0.6 0.3333333; enddata

max=u*ctrl-v*(1-ctrl); @free(u);@free(v);

@for(player2(j):@sum(player1(i):c(i,j)*x(i))>u);

-161-

@for(player1(i):@sum(player2(j):c(i,j)*y(j))

@sum(player1:x)=1;

@sum(player2:y)=1;

end

由定理4知，混合对策问题的求解问题可以转化为求不等式约束的可行点，而

LINGO软件很容易做到这一点。我们编写如下Lingo程序求解上述问题。

model:

sets:

player1/1..3/:x;

player2/1..3/:y;

game(player1,player2):c;

endsets

data:

c=0.3333333 0.5 -0.3333333

-0.4 0.2 -0.5

0.5 -0.6 0.3333333;

enddata

@free(u);

u=@sum(game(i,j):c(i,j)*x(i)*y(j));

@for(player1(i):@sum(player2(j):c(i,j)*y(j))

@for(player2(j):@sum(player1(i):c(i,j)*x(i))>u);

@sum(player1:x)=1;

@sum(player2:y)=1;

end

§5 二人非常数和对策

所谓常数和对策是指局中人I和局中人II所赢得的值之和为一常数。显然，二人零和对策是二人常数和对策的特例，即常数为零。

对于二人常数和对策，有纯策略对策和混合策略对策，其求解方法与二人零和对策是相同的。

二人非常数和对策也称为双矩阵对策。也有纯策略对策和混合策略对策两种策略。

5.1 纯策略问题例1给出了典型的二人非常数和对策，每人的赢得矩阵是不相同

的，因此称为双矩

阵对策。

问题分析这是一个二人非常数和对策问题。从表面上看，两犯罪嫌疑人拒不供认，只能被

判18个月徒刑，结果是最好的。但仔细分析，却无法做到这一点。因为犯罪嫌疑人A 如果采用不供认策略，他可能被判刑的刑期为18个月或7年，而犯罪嫌疑人B 可能判的刑期为0或18个月。而A 选择供认，他被判的刑期为0或3年，此时，犯罪嫌疑人B 可能判的刑期为3年或7年。因此，犯罪嫌疑人A 一定选择供认。基于同样的道理，犯罪嫌疑人B 也只能选择供认。

选择供认是他们最好的选择，各自被判3年。

按照上面的论述，对于一般纯策略问题，局中人I、II 的赢得矩阵如表2 所示。其中局中人I 有m个策略α1 ,L,αm ，局中人II 有n个策略β1 ,L, βn ，分别记为= {α1 ,L,αm }，S2 = {β1 ,L, βn }

S

1

-162-

1 1

2 2 C = (c ) 为局中人 I 的赢得矩阵，C = (c ) 为局中人 II 的赢得矩阵。因此， ij m ?n ij m

?n 双矩阵对策记为

G = {S , S ,

C 1 , C 2 } 1 2 表 2

β1

β2

βn

… 1 2 1 2

1

2

α1 α2

M

αm

(c , c ) (c , c ) (c 1n , c 1n ) … 11 11 12 12 1 2 1 2 1

2 (c , c )

(c , c )

(c 2n , c 2n )

M …

21 M 21 22 M

22 1 2 1 2 1 2 (c , c )

(c , c )

(c , c )

…

m 1 m 1 m 2 m 2 mn mn ,

C 1

, C 2

}是一双矩阵对策，若等式 设 G = {S , S 定义

5 1 2 c 1

= min max c 1 ， c 2 = min max c 2

（4）

i * j * ij i * j * ij

j

i

i

j

成立，则记 v = c 1

，并称 v 为局中人I 的赢得值，记 v = c 2

，并称 v 为局中人II 1 i * j * 1 2 i * j * 2 赢得值，称 (α * , β * ) 为 G 在纯策略下的解（或Nash 平衡点），称α * 和 β * 分别为局i j 人I ，II 的最优纯策略。 i j 实际上，定义5也同时给出了纯策略问题的求解方法。因此，对于例1，((1,0), (1,0)) 是Nash 平衡点，这里 (1,0) 表示以概率1取第一个策略，也就是说，坦白是他们的最佳策 略。

5.2 混合对策问题 如果不存在使式（4）成立的对策，则需要求混合对策。类似于二人零和对策情况， 需要给出混合对策的最优解。

（1）混合对策问题的基本概念

定义6 在对策 G = {S , S , C 1

, C 2

}中，若存在策略对 x ∈ S * , y ∈ S *

，使得

1 2 1 2 ??x T

C 1

y ≤ x T C 1

y , ?x ∈ S *

1 ? ??x T C

2 y ≤ x T C 2 y , ?y ∈ S *

2 则称 (x , y 为 G 的一个非合作平衡点。记 v = x T C 1 y ， v = x T C 2

y ，则称 v , v 分别

1 2 1 2 为局中人I ，II 的赢得值。

对于混合对策问题有如下定理。

定理8 每个双矩阵对策至少存在一个非合作平衡点。

定理9 混合策略 (x , y 为对策 G = {S , S ,

C 1

, C 2

}的平衡点的充分必要条件是 1 2 ? n ∑ ij j c y ≤ x T C 1 y , 1 i = 1,2,L , m ? ? j = 1 （5）

? m

? ∑ ij c x ≤ x T C 2 y , 2 j = 1,2,L , n ?? i =1

i （2）混合对策问题的求解方法

由定义6可知，求解混合对策就是求非合作对策的平衡点，进一步由定理8得到， 求解非合作对策的平衡点，就是求解满足不等式约束（5）的可行点。因此，混合对策

问题的求解问题就转化为求不等式约束（5）的可行点，而LINGO 软件可以很容易做到

这一点。

例 5 有甲、乙两支游泳队举行包括三个项目的对抗赛。这两支游泳队各有一名健 将级运动员（甲队为李，乙队为王），在三个项目中成绩都很突出，但规则准许他们每 人只能参加两项比赛，每队的其他两名运动员可参加全部三项比赛。已知各运动员平时 成绩（秒）见表 3。

表 3 假定各运动员在比赛中都发挥正常水平，又比赛第一名得5分，第二名得3分，第

三名得1分，问教练员应决定让自己队健将参加哪两项比赛，使本队得分最多？（各队 参加比赛名单互相保密，定下来后不准变动）

解 分别用 α1 、 α2 和 α3 表示甲队中李姓健将不参加蝶泳、仰泳、蛙泳比赛的策 略，分别用 β1 、 β2 和 β3 表示乙队中王姓健将不参加蝶泳、仰泳、蛙泳比赛的策略。 当甲队采用策略 α1 ，乙队采用策略 β1 时，在100米蝶泳中，甲队中赵获第一、钱获第 三得6分，乙队中张获第二，得3分；在100米仰泳中，甲队中李获第二，得3分，乙队中 王获第一、张获第三，得6分；在100米蛙泳中，甲队中李获第一，得5分，乙队中王获 第二、张获第三，得4分。也就是说，对应于策略 (α1 , β1 ) ，甲、乙两队各自的得分为 (14,13) 。表4给出了在全部策略下各队的得分，计算的Matlab 程clc,clear

a=[59.7 63.2 57.1 58.6 61.4 64.8 67.2 68.4 63.2 61.5 64.7 66.5 74.1 75.5 70.3 72.6 73.4 76.9]; m=3;n=3;kk=3;T=1000;

sc1=[5:-2:1,zeros(1,3)]; %1-6 名的得分 sc2=repmat(sc1,kk,1); for i=1:m

for j=1:n

b=a;

b(i,3)=T;b(j,4)=T; %不参加比赛，时间成绩取为充分大 [b,ind]=sort(b,2); %对 b 的每一行进行排序 for k=1:m

sc2(k,ind(k,:))=sc1; %计算得分 end

A_sc(i,j)=sum(sum(sc2(:,1:m))); %统计得分 B_sc(i,j)=sum(sum(sc2(:,m+1:end))); end end

A_sc,B_sc

-164-

甲 队

乙

队

赵

钱 李 王 张

孙 100 米蝶泳 59.7 63.2 57.1 58.6 61.4 64.8 100 米仰泳 67.2 68.4 63.2 61.5 64.7 66.5 100 米蛙泳

74.1

75.5

70.3

72.6

73.4

76.9

fid=fopen('txt2.txt','w'); fprintf(fid,'%f\n',A_sc'); fwrite(fid,'~','char'); fprintf(fid,'%f\n',B_sc'); fclose(fid);

%往纯文本文件中写 LINGO 数据的分割符

表4

按照定理8，求最优混合策略，就是求不等式约束（5）的可行解，写出相应的LINGO

程序如下：

model: sets:

pa/1..3/:x; pb/1..3/:y;

link(pa,pb):c1,c2; endsets data:

c1=@file(txt2.txt); c2=@file(txt2.txt); enddata

v1=@sum(link(i,j):c1(i,j)*x(i)*y(j)); v2=@sum(link(i,j):c2(i,j)*x(i)*y(j)); @for(pa(i):@sum(pb(j):c1(i,j)*y(j))

求得甲队采用的策略是α1 、α3 方案各占50％，乙队采用的策略是 β2 、β3 方案各

占

习 题 七 1. 表 5 是一双矩阵对策，试求局中人 A , B 的最优策略。

表 5

2. 有三张纸牌，点数分别为 1，2，3，显然按大小顺序为 3 > 2 > 1 。先由 A 任抽 一张，看过后反放在桌上，并任喊大（ H ）或小（ L ）。然后由 B 从剩下纸牌中任抽一 张，看过后， B 有两种选择：第一，弃权，付给 A 1 元；第二，翻 A 的牌，当 A 喊 H 时，得点数小的牌者付给对方 3 元，当 A 喊 L 时，得点数大的牌者付给对方 2 元。要

-165-

局 中 人 B 局中人 A

(10,4)

(4,8) (6,6) (8,8) (2,12)

(4,10)

β1

β2 β3

α1

α2 α3

(14,13) (13,14) (12,15) (13,14) (12,15) (12,15) (12,15)

(12,15)

(13,14)

求：（i ）说明 A , B 各有多少个纯策略；（ii ）根据优超原则淘汰具有劣势的策略，并列 出 A 的赢得矩阵；（iii ）求解双方各自的最优策略和对策值。

3. “二指莫拉问题”。甲、乙二人游戏，每人出一个或两个手指，同时又把猜测对 方所出的指数叫出来。如果只有一个人猜测正确，则他所赢得的数目为二人所出指数之 和，否则重新开始。写出该对策中各局中人的策略集合及甲的赢得矩阵，并回答局中人 是否存在某种出法比其他出法更为有利。

4. 甲、乙两队进行乒乓球团体赛，每队由3名球员组成。双方可排出3种不同的阵

容。甲队的3种阵容记为 A , B ,C ；乙队的3种阵容为Ⅰ，Ⅱ，Ⅲ。根据以往的记录。两 队以不同的阵容交手的结果如表6所示。

表6 甲队得分数

表6中的数字为双方各种阵容下甲队的得分数。这次团体赛双方各采取什么阵容比较稳 妥？

-166-

乙队

甲队

Ⅰ Ⅱ Ⅲ A －3 －1 －2 B －6 0 3 C

5

1

－4