对策论应用示例

对策论应用示例

对策理论（Game Theory）现在广泛应用于军事、经济等领域。对策论的主要分类大致如下：

Game静态Game动态Game结盟Game不结盟Game微分Game重复Game联合Game合作Game有限Game无限Game2人Game多人Game2人Game多人Game零和

非零和零和非零和零和非零和零和非零和

§1 对策论应用举例

例1 齐王与田忌赛马（孙膑对策）

传说齐威王与大臣田忌赛马，每人都以上等马、中等马、下等马比赛，三局两胜制，胜者得1千金。齐王的同等马优于田忌的同等马，田忌总输。后来军事家孙膑为田忌出主意：田忌用上等马赢齐王的中等马、用中等马赢齐王的下等马，最后以下等马输给齐王一局，这样田忌就以总分3：2获胜。对局图如下：

齐王的马 田忌的马

上等马 上等马

中等马 中等马

下等马 下等马

在这个对策中，双方对于对方的情况十分熟悉，事先也知道比赛规则，这在对策论中叫做双方全信息的对策。另外，在这个对策中，一方用计谋和策略，另一方不用，这不是现代意义下的对策。现代意义下的对策，对局双方都用计谋和策略，并且双方都选择对自己有利的策略，这在对策论中叫理智的局中人（经济对策中叫理性的消费者）。

例2 1943年2月，由于战争的失败，日本舰队打算从新不列颠岛撤退到伊里安岛（如图）。美国西南太平洋空军奉命轰炸这支日本舰队。

北

新几亚（

新不列颠岛

新几内亚（伊里安岛） 南 日本舰队的可能撤退航线有两条：南线与北线，航程都是3天。气象预报：未来3天，北线阴雨、南线晴天。日本人应该选择哪一条撤退航线呢？

美军的选择是重点搜索的方向：（1）非重点搜索：派少量搜索飞机，发现目标后派大量飞机轰炸；（2）重点搜索：派大量搜索飞机，发现目标后再派大量飞机轰炸。根据气象预报，未来3天，北线阴雨，能见度很差，不利于侦察飞机巡

航侦察（二战时，主要依靠飞行员目测侦察）；南线晴天，能见度好，有利于侦察机巡航侦察。美军应该把搜索重点放在北边还是南边呢？

美军重点搜索方向 北 南 日本撤 北 -2/3 -1/3 退航线 南 -2/3 -3/3 表中第一行第一列的-2/3表示：日方若选择北线撤退，美军的重点搜索方向也在北线，日本舰队在3天中大约能安全行走一天，然后被美军侦察机发现，招来大批轰炸机，在未来2天被轰炸。下面讨论双方应该选择的较好的策略。

日本方面：北边的损失向量（-2/3，-1/3）≥南边的损失向量（-2/3，-3/3），表示北线损失比南线小，日方司令官若是理智的决策者就应选北线作为航线。那么,在上表中去掉第二行。于是，美军应该在第一行的两个数字中选择对日本造成损失最大的策略，所以，美军应该在日本选择北线作为航线的前提下，重点搜索方向选在北线。

事实上，双方司令官都如此分析并决策，结果，在双方预期的地点发生海空大战，日本舰队损失2/3。

例3狼追兔问题（达·芬齐）

兔子在原点处吃草（见下图），狼在离它100米的A处。狼发现了兔子，兔子也发现了狼，兔子开始往60米外的洞口跑，狼开始追，假设兔子的速度是狼的一半，达·芬齐问：狼是否能追上兔子？

y 洞口 60 Y=f(x) O A x 令A = 兔子与狼的距离，c = 兔子的速度 ： 狼的速度。狼的追击路线为 y = f(x)，则f(x) 满足下列微分方程：

dy代入，分离变量，得 dx y'dy1y'211cdx，y'kxcc2kxx，将

x1cAcx1cAc yc22A1c21c1c

以达·芬齐的数据，兔子在原点处，发现狼以后，向60米外的洞口跑去，另

12200将A = 100,c = 1/2代入，y，求此曲线与坐标轴的交点，x10x23032002606，结论：狼不可能追上兔子。 33评注：由此类追击问题发展成追踪—回避对策问题（Pursuit—Evasion Games），1965年，美国数学家Rufus Isaacs提出了微分对策理论，开拓了新的方法与应用领域。

例4 国际象棋的策略

1912年，E. Zermelo首先用集合论的方法研究下棋，他证明了国际象棋的三种着法（自始至终的着法）中，必定存在一种不依赖对方怎样行动，自己一方总能取胜的着法，或者有一方总能保证下成和局的着法。

例5 战略核武器杀伤力对策（非零和）

冷战时期，美国与前苏联核武竞赛。苏联主要是提高核武器的爆炸当量；美国主要是提高核武器的精度。设：杀伤力为k、威力（当量）为y、精度为c，经过大量实验，有如下公式：

31用x = 0代入，得 y0ky 2c*2323假定双方的参数都提高8倍。

苏联方面：精度c保持不变，威力提高8倍，y*=8y，k1*到杀伤力提高4倍。

*美国方面：威力y保持不变,精度提高8倍，c*=c/8，k2y*

，k1=4k，得c223y，k2*=k。得*2c到杀伤力提高倍。

结论：提高精度为最佳方案。

例6 美国戈宁公司生产的落地高保真收音机，10千周以上的频率范围都适用，销路好、利润大。老板的目的：降低成本，加大利润。降低成本的关键：放大电路中一种特殊型号的微调电容器。

市场上现有三家公司可以供货。第一种，便宜货（水货），价$1，若遇到次品，戈宁公司要另加其他费用$9，共$10；第二种，保用品，价$6，若遇到次品，由供货厂家负责其他一切费用；第三种，高档货，价$10，绝无次品。公司现在使用的是保用品，每只特殊型号的微调电容器成本价格是$6。公司应该怎样

调整进货策略？这是一个2人零和的矩阵对策。矩阵如下：

进货策略 次品 正品 S1 便宜货 -10 -1 S2 保用品 -6 -6 S3 高档货 0 -10 求得其Nash均衡解为 S1 ：S3=10：9，即进货策略为：以水货10与高档货9的比例进货，每只特殊型号的微调电容器的平均进价大约$5.26（V= -

555.26），公司节约了进价成本。具体求解过程见下节。 19

例7 设2人零和的矩阵对策甲方的收入矩阵（payoff matrix）为：

q1q2q3p1618Ap2324

p39110p4630甲方有4种策略可以选择：p1、p2、p3、p4，乙方有3种策略可供选择：q1、q2、

q3。矩阵中的数字是甲方对应的收入，也就是乙方的损失（将数字反号就是乙方的收入），甲方的收入 + 乙方的收入 = 0，所以叫零和的2 人矩阵对策。双方都希望自己的收入越大越好。以甲方为例，他的第一行收入向量（-6，1，-8）<第二行收入向量（3，2，4），所以甲方不会选择第一种策略p1，在矩阵中去掉

243，9110不会选择的第一行（-6，1，-8）得到一个新的矩阵 A*1306然后，行中求最小元，列中求最大元，得到Nash均衡（即鞍点—saddle point）：在A*1 的第一行与第二列交叉的地方，就是元素2。于是，双方的Nash均衡策略为，甲选p2；乙选q2。也就是甲选取各策略的概率为（0，1，0，0）；乙选

取各策略的概率为（0，1，0）。

例8 设2人零和的矩阵对策甲方的收入矩阵（payoff matrix）为：

7132A1613084，其Nash平衡点（即鞍点）在第二行与第二列交叉的地方：95就是元素2。于是，双方的Nash均衡策略为，甲选第二个策略，乙也第二个策略，于是，甲选取各策略的概率为（0，1，0，0）；乙选取各策略的概率为（0，1，0）。

例9 某单位秋天买煤，储藏，冬天取暖用。冬季正常情况下，耗煤15吨，较冷耗煤20吨，较暖耗煤10吨。而煤价随气温变化，正常15元/吨，较冷20元/吨，较暖10元/吨。秋季价10元/吨。问：储煤多少吨合理？

取暖实际费用 = 秋季购价 + 冬季补充价，得此单位的收入矩阵（也就是买煤的成本）如下：

大 自 然 B1（较暖） B2（正常） B3（较冷） 某 A1(10吨) -100 -175 -300 单 A2(15吨) -150 -150 -250 位 A3(20吨) -200 -200 -200 我们可以将此问题理解为单位与大自然的博弈问题。其Nash平衡解（鞍点）在第三行与第三列交叉的地方：-200，即，此单位应该采取的策略是第三个策略：A3 = 秋季储煤20吨。

13例10设2人零和的矩阵对策甲方的收入矩阵（payoff matrix）为：A，42111其Nash平衡解为 x*,;y*,22435;v。其中v = 5/2说明矩阵对策42的值为5/2，也就是若长期按这种规则进行博弈，甲方的期望收入为5/2。甲方

平均收获5/2，说明游戏规则对乙方不利。

例11设有2人零和的矩阵对策甲方的收入矩阵（payoff matrix）为：

35A746403002593959 68760883A是甲方的收入矩阵，越大越好，应该去掉小的行；对乙方来说，付出的越少越

好，应该去掉大的列。先去掉第一、二行，再去掉第三、四、五列，最后去掉第五行，得到：

73 A*46A*中保留了A的第三、四行，及第一、二列。根据2阶矩阵对策求解公式（见下节）求得：

A*的解 x3 = 1/3, x4 = 2/3；y1 = 1/2, y2 = 1/2；v = 5。 最后综合得

X* = (x1,x2,x3,x4,x5) = (0,0,1/3,2/3,0)； Y* = (y1,y2,y3,y4,y5) = (1/2,1/2,0,0,0)；

v = 5。

例12设2人零和的矩阵对策甲方的收入矩阵（payoff matrix）为：

41 31A是甲方的收入矩阵，越大越好，应该去掉小的行；对乙方来说，付出的越少越好，应该去掉大的列。先去掉第四、三列，再去掉第一行，然后去掉第二列，最后去掉第二、四行，得到这个矩阵对策的解：

X* = (x1,x2,x3,x4) = (0,0,1,0)；Y* = (y1,y2,y3,y4) = (1,0,0,0)；V = 2。

例13 设2人零和的矩阵对策甲方的收入矩阵（payoff matrix）为：

111 A11312111A200424302116343其Nash均衡解为x*,,;y*,,;v。

13131313131313

§2 2人零和矩阵对策的求解

I. 二阶2人零和矩阵对策的求解

假设二阶2人零和矩阵对策甲方的收入矩阵为

aA11a21则其求解公式为：

a12 a22

vAa11a22a12a21a22a21a11a22a12a21a11a12

a11a22a12a21a22a12a11a22a12a21a11a21a11a22a12a21x1x2y1y2其中v表示矩阵对策的值（即甲方的期望收入），x1、x2分别表示甲方选取第一、第二个策略的概率，y1、y2分别表示乙方选取第一、第二个策略的概率。

II. 一般2人零和矩阵对策的求解步骤如下：

设有2人零和矩阵对策（A, X, Y），其中A为m×n阶的甲方收益矩阵， X为甲方选取的策略（m阶），Y为乙方选取的策略（n阶），其Nash均衡（在经济学中也叫Pareto最优解）为（XA,YA,VA）。其中XA表示甲方选取m个可能策略的概率，YA表示乙方选取n个可能策略的概率，VA表示这个矩阵对策的值（也就是甲方的期望收入，或叫平均收入）。

Step1 将矩阵A每个元素都加一个适当的数，得到m×n阶的矩阵B，使得B>0。由此得到2人零和矩阵对策（B, X, Y）,设其Nash均衡解为（XB,YB,VB）。对策论中已经证明XB = XA, YB = YA。但VA不一定等于VB；

Step2 设XB=（x1, x2, …, xm ），YB = ( y1, y2, …, yn )。

令em = (1,1,…,1)是m维的全1 向量，en = (1,1,…,1)是n维的全1 向量。取两个过渡向量a=(a1,a2,…,am), b=(b1,b2,…,bn)。对策论方法告诉我们先通过下面的线性规划、对偶线性规划

minfa1a2...amaBens.t.a0maxFb1b2...bn 及

Bbems.t.b0

求出a和b，然后 XB =

ab、YB = 。

a1a2...amb1b2...bnStep3 XA = XB, YA = YB。

令Vm = { v, v, …, v }是m维的全v向量，Vn = { v, v, …, v }是n维的全v向量。通过下面的不等式组求解矩阵对策A的值VA：XB.AVn,A.YBVm

mminax根据对策论的知识，矩阵对策的值 VAmaxiji。其中aij是矩xS11jni1

阵对策A的元素。

Step4 将以上方法转化为数学软件包Mathematica能够编程的形式： minfa1a2...ammin(F)(b1b2...bn)BTaT(en)Ts.t.Ta0 及

Bbems.t.b0

注意：在Mathematica中向量与其转置是等价的。

Step5 数学软件包Mathematica的一般求解程序（其中k是一个适当的常数）：

k = ...; A = ...; B = A + k;

em = ...; en = ...;

BB = Transpose[ B ];

a = LinearProgramming[ em, BB, en ]; XB = a / a.em;

Print[“ XB = ”, XB ]

b = LinearProgramming[ -en, -B, -em ]; YB = b / b.en;

Print[ “ YB = ”, YB ]

运行以上程序，就可以求出XB、YB。然后通过下面的不等式组求解矩阵对策A的值VA：

Vm{VA,VA,...,VA};Vn{VA,VA,...,VA};。 XB.AVn,A.YBVm

例14 税收对策 某企业有甲、乙两个公司，每年应交的税款分别是400万元和1200万元。对于每个公司，企业可以如实申报税款，或者篡改帐目，申称税额为零。而国家税务局由于人力所限，对该企业每年只能检查一个公司的帐目。如果税务局发现有偷税现象，则该公司不但要如数交纳税款，而且将被处以r倍税款的罚金。（1）求r = 0.5时，双方的对策解；（2）罚金提高到税款的多少倍，企业才不敢偷税？

解：用T表示如实申报税款、F表示偷税。 （1）按r = 0.5求解。

企业的对策有：S1 = {T，T}，表示两个公司都如实申报；S2 = {F，T}，表示第一家公司偷税、第二家公司如实申报（以下同）；S3 = {T，F}；S4 = {F，F}。国家税务局的对策有：SS1 = 查甲公司；SS2 = 查乙公司。于是得到一个两人零和矩阵对策，其国家税务局的收入矩阵为（单位：百万元）：

r0.5;1(1r)1244(1r)

A1612412(1r)12(1r)

在Mathematica软件包中编程求解如下： k = 0; r = 0.5;

A = { { 16, 4(1+r)+12, 4, 4(1+r) }, { 16, 12, 4+12(1+r), 12(1+r) } }; B = A + k;

em = { 1, 1 }; en = { 1, 1, 1, 1 }; BB = Transpose[ B ];

a = LinearProgramming[ em, BB, en ]; XB = a / a.em;

Print[“ XB = ”, XB ]

b = LinearProgrmming[ -en, -B, -em ]; YB = b / b.en;

Print[ “ YB = ”, YB ]

运行以上程序，就可以求出XB、YB。得到如下结果： XB = { 1/3, 2/3 }

YB = { 0, 1/3, 0, 2/3 }

XB表示税务局应该以1/3的概率对企业的甲公司查账、以2/3的概率对企业的乙公司查账，YB表示企业采取4个策略S1 = {T，T}、S2 = {F，T}、S3 = {T，F}、S4 = {F，F}概率分别为0、1/3、0、2/3，即：有1/3的时间让甲公司偷税、乙公司不偷税，有2/3的时间甲乙公司都偷税。

再求矩阵对策A的值VA,程序如下：XB.AVn,A.YBVm

Vm = { VA, VA }; Vn = { VA, VA, VA, VA }; XB.A >= Vn A.YB <= Vm

执行以后得到如下结果：

{ 16, 14, 16, 14 } >= { VA, VA, VA, VA } { 14, 14 } <= { VA, VA }

求解以上不等式组，得到此矩阵对策的值 VA = 14,即税务局平均收取税款与罚金1400万。

（2）不断变动r的值，求解使得YB = { 1, 0, 0, 0 } 的最小的r，即，寻找使得企业不偷税的最小的r。企业不敢偷税漏税，表明企业的最佳策略为Y = { 1，0，0，0 }，即只能取策略s1 = { T，T }。

假设罚金是应交税款的r倍，国家税务局的收入矩阵为（单位：百万元）：

r?;1(1r)1244(1r)

A1612412(1r)12(1r)在Mathematica软件包中编程求解如下：

k = 0; r = 2;

A = { { 16, 4(1+r)+12, 4, 4(1+r) }, { 16, 12, 4+12(1+r), 12(1+r) } }; B = A + k;

em = { 1, 1 }; en = { 1, 1, 1, 1 };

BB = Transpose[ B ];

a = LinearProgramming[ em, BB, en ]; XB = a / a.em;

Print[“ XB = ”, XB ]

b = LinearProgrmming[ -en, -B, -em ]; YB = b / b.en;

Print[ “ YB = ”, YB ]

直到r = 2时，才有XB = { 1/2, 1/2 }、YB = { 1, 0, 0, 0 }，以及VA = 16。

由于Mathematica软件包与LINDO软件包的缺陷，它们不能求解系数矩阵中有参数的情形。我们只能逐步替换r的值计算。

例15 进货对策 在例2中，我们得到

进货策略 次品 正品 S1 便宜货 -10 -1 S2 保用品 -6 -6 S3 高档货 0 -10 101A66即，。

010具体求解过程如下（将A中元素都加11）： k = 11;

A = { { -10， -1 }， { -6， -6 }， { 0， -10 } }; B = A + k;

em = { 1， 1， 1 }; en = { 1， 1}; BB = Transpose[ B ];

a = LinearProgramming[ em, BB, en ]; XB = a / a.em;

Print[“ XB = ”, XB ]

b = LinearProgrmming[ -en, -B, -em ]; YB = b / b.en;

Print[ “ YB = ”, YB ]

运行以上程序，就可以求出XB、YB：

XB = { 10/19, 0, 9/19 } YB = { 9/19, 10/19 }

再利用XB及YB求得A的对策值：

Vm = { VA, VA, VA }; Vn = { VA, VA }; XB.A >= Vn A.YB <= Vm 得到：

{ - 100/19, -100/19 } >= { VA, VA }

{ - 100/19, -6, -100/19 } >= { VA, VA, VA }

求解以上不等式组，得到此矩阵对策的值VA = - 100/19 ≈ - 5.26316。

§3 n人合作对策模型

Shapley(1953)讨论了人合作对策问题：

记n人集合为I = {1,2,…,n}。SI，都有一个获利函数（或叫特征函数）V(S)，满足

V0;VS1S2VS1VS2,where,S1S2.

公平的分配向量（Imputation Vector）φ(V(I)) =φ(V) = (φ1, φ2,…, φn)应该满足以下4条公理：

公理1 第j人获利φj与自己的编号无关；

公理2 个人获利总和等于总获利，jV(I)；

公理3 若j对总获利没有贡献，即，若SI,jS,V(S)V(Sj)，则φj=0（不做贡献不获利）；

公理4 若总获利增加 W = V + V’，则φ(W) =φ(V) +φ(V’)。

Shapley证明满足以上4条公理的Φ是唯一的，用以下公式求得：

jsVsVsj

sSj其中V(s)V(sj)表示j对s的贡献；Sj = 含j的所有子集s组成的类 = j所可能参加的所有合作集合；

|s| = s中的元素个数；w(|s|)是加权因子 =

s1!ns!n!。

例16 三个商人经商。单干每人获利一万元；1、2合作，获利七万元；1、3合作，获利五万元；2、3合作，获利四万元；三人合作，获利十万元。问：三人合作，如何分配10万元的收入？

获利函数 V(1) = V(2) = V(3) = 1, V(1,2) = 7, V(1,3) = 5, V(2,3) = 4, V(1,2,3)=10。用Shapley方法求分配向量φ(10) = (φ1, φ2, φ3)。先求φ1。 s {1} {1,2} {1,3} {1,2,3} V(s) 1 7 5 10 V(s-1) 0 1 1 4 V(s)-V(s-1) 1 6 4 6

|s| 1 2 2 3 w(|s|) 1/3 1/6 1/6 1/3 w(|s|)( V(s)-V(s-1)) 1/3 1 2/3 2 φ1=4 同样可得, φ2=3.5，φ3=2.5。即，φ(10) = (φ1, φ2, φ3) =（4, 3.5, 2.5）。

例17 三人合作对策，其获利函数为：V(j) = 0 ( j = 1,2,3 ), V(1,2) = 1/3, V(1,3) = 1/6, V(2,3) = 5/6, V(1,2,3) = 1, 求得Shapley分配向量为 φ(V) =（ 5/36, 17/36, 14/36 ）。

例18 五政党联盟竞选，党1拥有3张投票权，党2、3、4、5都只拥有1张投票权，自由结成联盟后，总票数过半就可获胜。获胜后如何分配内阁名额？ 解：共7张投票权，大于等于4即可获胜。其获利函数求得如下：

V(φ) = 0； V(1,2) = V(1,3) = V(1,4) = V(1,5) = 1（此处1代表获胜）； V(1,2,3) = V(1,2,4) = V(1,2,5) = V(1,3,4) = V(1,3,5) = V(1,4,5) = 1； V(1,2,3,4) = V(1,2,3,5) = V(1,2,4,5) = V(1,3,4,5) = V(2,3,4,5) = 1； V(1,2,3,4,5) = 1；其他子集S, V(S) = 0。

求得Shapley分配向量为：

φ(V) =（ 6/10, 1/10, 1/10, 1/10, 1/10 ） 即，党1应该拥有6/10的内阁席位。

习题

（1）求齐王与田忌赛马的Nash均衡解。

（2）某企业有甲、乙、丙3个公司，每年应交的税款分别是400万元、1200万元和800万元。对于每个公司，企业可以如实申报税款，或者篡改帐目，申称税额为零。而国家税务局由于人力所限，对该企业每年只能检查一个公司的帐目。如果税务局发现有偷税现象，则该公司不但要如数交纳税款，而且将被处以r倍税款的罚金。（1）求r = 0.5时，双方的对策解；（2）罚金提高到税款的多少倍，企业才不敢偷税？