《数学模型与数学实验》课程书籍文献（数学建模算法大全）第07章 对策论

第七章对策论 §1引言 社会及经济的发展带来了人与人之间或团体之间的竞争及矛盾，应用科学的方法米 解决这样的问题开始于I7世纪的科学家，如C.,Huygens和W.,Leibnitz等。现代对 策论起源于1944年J.,Von Neumann和O.,Morgenstern的著作《Theory of Games and Economic Beh 策论亦 论或博弈论。 一般 是研究具有斗争或竞争性质现象的数学理论和方 代所研究的现象 军 对 的日常 日处理的 在日常生活中，经常看到一些只有相互之间斗争或竞争性质的行为。具有竞争或对 抗性质的行为称为对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目 标和利益。为了达到各自的目标和利益，各方必须考虑对手的各种可能的行动方案，并 力图选取对自己最为有利或最为合理的方案，对策论就是研究对策行为中斗争各方是否 存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。 52对策问题 对策问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的 努力而是各方所采取的策略的综合结果。 先考察一个实际例子。 例1（囚徒的困境）警察同时逮捕了两人并分开关押，速捕的原因是他们持有大 量伪币，警方怀疑他们伪造钱币，但没有找到充分证据，希望他们能自己供认，这两个 人都知道：如果他们双方都不供认，将被以持有大量伪币罪被各判刑18个月：如果双 方都供认伪造了钱币，将各被判刑3年：如果一方供认另一方不供认，则供认方将被从 宽处理而免刑，但另一方面将被判刑7年。将嫌疑犯A、B被判刑的几种可能情况列 于表1。 表」 嫌疑犯B 供认 不供认 嫌疑犯A （15,1.5) 表】中每对数字表示嫌疑犯A、B被判刑的年数。如果两名疑犯均担心对方供认并希 望 轻的惩罚，最保险的办法自然是承认制 从这 伪巾 中人。通常用表示局 中人的集 个对策中 要有两个局中人。在例1中，局中人是A、B两名疑犯。 局对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个策略。参 加对策的每 局中人i,i∈I,都有自己的策略集S,。一般，每一局中人的策略集中 至纱心包括两个筑暗

-154- 第七章 对策论 §1 引言 社会及经济的发展带来了人与人之间或团体之间的竞争及矛盾，应用科学的方法来 解决这样的问题开始于 17 世纪的科学家，如 C.，Huygens 和 W.，Leibnitz 等。现代对 策论起源于 1944 年 J.，Von Neumann 和 O.，Morgenstern 的著作《Theory of Games and Economic Behavior》。 对策论亦称竞赛论或博弈论。是研究具有斗争或竞争性质现象的数学理论和方法。 一般认为，它既是现代数学的一个新分支，也是运筹学中的一个重要学科。对策论发展 的历史并不长，但由于它所研究的现象与人们的政治、经济、军事活动乃至一般的日常 生活等有着密切的联系，并且处理问题的方法又有明显特色。所以日益引起广泛的注意。 在日常生活中，经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对 抗性质的行为称为对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目 标和利益。为了达到各自的目标和利益，各方必须考虑对手的各种可能的行动方案，并 力图选取对自己最为有利或最为合理的方案。对策论就是研究对策行为中斗争各方是否 存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。 §2 对策问题 对策问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的 努力而是各方所采取的策略的综合结果。 先考察一个实际例子。 例 1（囚徒的困境） 警察同时逮捕了两人并分开关押，逮捕的原因是他们持有大 量伪币，警方怀疑他们伪造钱币，但没有找到充分证据，希望他们能自己供认，这两个 人都知道：如果他们双方都不供认，将被以持有大量伪币罪被各判刑 18 个月；如果双 方都供认伪造了钱币，将各被判刑 3 年；如果一方供认另一方不供认，则供认方将被从 宽处理而免刑，但另一方面将被判刑 7 年。将嫌疑犯 A 、 B 被判刑的几种可能情况列 于表 1。 表 1 嫌疑犯 B 供认 不供认 嫌疑犯 A 供认 不供认 （3，3） （0，7） （7，0） （1.5，1.5） 表 1 中每对数字表示嫌疑犯 A、B 被判刑的年数。如果两名疑犯均担心对方供认并希 望受到最轻的惩罚，最保险的办法自然是承认制造了伪币。 从这一简单实例中可以看出对策现象中包含有的几个基本要素。 2.1 对策的基本要素 （i）局中人 在一个对策行为（或一局对策）中，有权决定自己行动方案的对策参加者，称为局 中人。通常用 I 表示局中人的集合．如果有n 个局中人，则 I = {1,2,L,n}。一般要求 一个对策中至少要有两个局中人。在例 1 中，局中人是 A、B 两名疑犯。 （ii）策略集 一局对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个策略。参 加对策的每一局中人i ，i ∈ I ，都有自己的策略集 Si 。一般，每一局中人的策略集中 至少应包括两个策略

(i)赢得函数（支付函数） 在一局对策中，各局中人所选定的策略形成的策略组称为一个局势，即若5，是第 个局中人的一个策略，则n个局中人的策略组 s) 就是一个局势。全体局势的集合S可用各局中人策略集的笛卡尔积表示，即 S=S×S,×.×S_ 当局势出现后，对策的结果也就确定了。也就是说，对任一局势，s∈S,局中人 i可以得到一个赢得H,(S)。显然，H,(s)是局势s的函数，称之为第1个局中人的扇 得函数。这样，就得到一个向量赢得函数H(s)=(H,(s,H(s》。 本节我们只讨论有两名局中人的对策问题，其结果可以推广到一般的对策模型中 去。 2.2零和对策（矩阵对策） 和对策是 设局中人1、Ⅱ的策略集分别为 S1={a,.,am},S2={B,.,Bn} 当局中人I选定策略（和局中人Ⅱ选定策略B,后，就形成了一个局势(a,B,),可见 这样的局势共有mm个。对任一局势(C,B,),记局中人【的赢得值为a,并称 a1a12.a1n .a a 当局中) Ⅱ和策略集S、S,及局中人I的赢得矩阵A确定后， 个零和对策 就给定了，零和对策又可称为矩阵对策并可简记成 G={S,S2;4A. 例2 设有一矩阵对策G={S,S2A，其中S={a,4a}, S2={B,B2,B,B}, [12-630-22 A=1421810 -60-1016 从A中可以看出，若局中人「希望获得最大赢利30，需采取箭路心，但此时若局 中人Ⅱ采取策略B,局中人1非但得不到30，反而会失去22。为了稳妥，双方都应考 虑到对方有使自己损失最大的动机，在最坏的可能中争取最好的结果，局中人【采取策 略42、a时，最坏的赢得结果分别为 -155

-155- （iii）赢得函数（支付函数） 在一局对策中，各局中人所选定的策略形成的策略组称为一个局势，即若 i s 是第i 个局中人的一个策略，则n 个局中人的策略组 ( , , , ) 1 2 n s = s s L s 就是一个局势。全体局势的集合 S 可用各局中人策略集的笛卡尔积表示，即 S = S1 × S2 ×L× Sn 当局势出现后，对策的结果也就确定了。也就是说，对任一局势， s∈S ，局中人 i 可以得到一个赢得 H (s) i 。显然， H (s) i 是局势 s 的函数，称之为第i 个局中人的赢 得函数。这样，就得到一个向量赢得函数 ( ) ( ( ), , ( )) 1 H s H s H s = L n 。 本节我们只讨论有两名局中人的对策问题，其结果可以推广到一般的对策模型中 去。 2.2 零和对策（矩阵对策） 零和对策是一类特殊的对策问题。在这类对策中，只有两名局中人，每个局中人都 只有有限个策略可供选择。在任一纯局势下，两个局中人的赢得之和总是等于零，即双 方的利益是激烈对抗的。 设局中人Ⅰ、Ⅱ的策略集分别为 { , , } S1 = α1 L α m ， { , , } S2 = β1 L β n 当局中人Ⅰ选定策略αi 和局中人Ⅱ选定策略 β j 后，就形成了一个局势( , ) αi β j ，可见 这样的局势共有mn 个。对任一局势( , ) αi β j ，记局中人Ⅰ的赢得值为aij ，并称 ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = m m mn n n a a a a a a a a a A L L L L L L L 1 2 21 22 2 11 12 1 为局中人Ⅰ的赢得矩阵（或为局中人Ⅱ的支付矩阵）。由于假定对策为零和的，故局中 人Ⅱ的赢得矩阵就是 − A。 当局中人Ⅰ、Ⅱ和策略集 1 S 、 2 S 及局中人Ⅰ的赢得矩阵 A 确定后，一个零和对策 就给定了，零和对策又可称为矩阵对策并可简记成 { , ; } G = S1 S2 A 。 例 2 设有一矩阵对策 { , ; } G = S1 S2 A ，其中 { , , } S1 = α1 α 2 α3 ， { , , , } S2 = β1 β 2 β 3 β 4 ， ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − − − − = 6 0 10 16 14 2 18 10 12 6 30 22 A 从 A 中可以看出，若局中人Ⅰ希望获得最大赢利 30，需采取策略α1，但此时若局 中人Ⅱ采取策略 β 4 ，局中人Ⅰ非但得不到 30，反而会失去 22。为了稳妥，双方都应考 虑到对方有使自己损失最大的动机，在最坏的可能中争取最好的结果，局中人Ⅰ采取策 略α1 、α 2、α3 时，最坏的赢得结果分别为

min{12,-6,30,-22}=-22 min14.2.1810!=2 minf-6,0,-10,16=-10 其中最好的可能为max{-22,2,-10;=2。如果局中人I采取策略%2，无论局中人Ⅱ 采取什么策略，局中人I的赢得均不会少于2。 局中人Ⅱ采取各方案的最大损失为max{12,14,-6}=14,max{-6,2,0}=2, ma取3018-10}=30.和max-221016}=16。当局中人Ⅱ采取笛路B.时.比括 失不会超过2。 生意到在廊网矩陈中2既品所在行中的最小元蓬又是所在列中的最 只要对方 策略 局中人新 称这样的局势为对策的 可能通过变换策 或 定义1设f(x,y)为一个定义在x∈A及y∈B上的实值函数，如果存在x*∈A, y*∈B,使得 x∈A和y∈B,有 f(x,y*)≤(x*,*)≤f(x*,y) 则称(x*,y*)为函数∫的一个鞍点。 定义2设G={S,S2;A为矩阵对策，其中S={a,a,.,a}, S2={B,B2,.,Bn},A=(an）mn·若等式 max mind min maxdy=d (1) 成立，记V。=a,则称V。为对策G的值，称使(1)式成立的纯局势(a,B,)为 对策G的鞍点或稳定解，赢得矩阵中与(a,B)相对应的元素a称为赢得矩阵的鞍 点，a,与B,分别称为局中人I与Ⅱ的最优纯策略。 的极关小 对策G,如何判断它是香具有鞍点呢？为了回答这一问题，先引入下面 定理1设G={S,S2;A,记μ=max mina,v=-min max d,则必有 4+v≤0. 证明v=max min(-a,),易见μ为I的最小赢得，v为Ⅱ的最小赢得，由于G 是零和对策，故H+y≤0必成立. 定理2零和对策G具有稳定解的充要条件为“+V=0。 证明：（充分性）由“和v的定义可知，存在一行例如p行，4为p行中的最小元 素，且存在一列例如g列，-V为q列中的最大元素。故有 am2μ且ag≤- 又因μ+v=0,所以μ=-v,从而得出a网=Ⅱ，a网为赢得矩阵的鞍点，(Cp,B,) 为G的稳定解。 (必要性)若G具有稳定解(a,B,),则a为赢得矩阵的鞍点。故有 u=max mindy之mina=a网 156

-156- 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 = S1 S2 A 为矩阵对策，其中 { , , , } S1 = α1 α 2 L α m ， { , , , } S2 = β1 β 2 L β n ， A = aij m×n ( ) 。若等式 max min minmax ij i* j* j i ij i j a = a = a （1） 成立，记VG = ai* j* ，则称VG 为对策G 的值，称使（1）式成立的纯局势( , ) αi* β j* 为 对策G 的鞍点或稳定解，赢得矩阵中与( , ) αi* β j* 相对应的元素ai* j* 称为赢得矩阵的鞍 点，αi* 与 β j* 分别称为局中人Ⅰ与Ⅱ的最优纯策略。 给定一个对策G ，如何判断它是否具有鞍点呢？为了回答这一问题，先引入下面 的极大极小原理。 定理 1 设 { , ; } G = S1 S2 A ，记 ij i j μ = max min a ， ij j i ν = −minmax a ，则必有 μ +ν ≤ 0 。 证明 max min( )ij j i ν = −a ，易见 μ 为Ⅰ的最小赢得，ν 为Ⅱ的最小赢得，由于G 是零和对策，故 μ +ν ≤ 0 必成立。 定理 2 零和对策G 具有稳定解的充要条件为 μ +ν = 0。 证明：（充分性）由 μ 和ν 的定义可知，存在一行例如 p 行，μ 为 p 行中的最小元 素，且存在一列例如 q 列， −ν 为 q 列中的最大元素。故有 apq ≥ μ 且apq ≤ −ν 又因 μ +ν = 0，所以 μ = −ν ，从而得出apq = μ ，apq 为赢得矩阵的鞍点，( , ) α p β q 为G 的稳定解。 （必要性）若G 具有稳定解( , ) α p β q ，则apq 为赢得矩阵的鞍点。故有 pj pq j ij i j μ = max min a ≥ min a = a iq pq i ij j i −ν = minmax a ≤ max a = a

从而可得4+v≥0，但根据定理1,4+y≤0必成立，故必有4+v=0。 上述定理给出了对策问题有稳定解（简称为解）的充要条件。当对策问题有解时， 其解可以不唯一，当解不唯一时，解之间的关系具有下面两条性质： 性质1无差别性。即若(a,P,)与(a,P2)是对策G的两个解，则必有 a=a2h· 性质2可交换性。即若(a,B)和(a,Bn)是对策G的两个解，则(a,Bn)和 (a,B)也是解。 §3零和对策的混合策略 具有稳定解的零和问题是一类特别简单的对策问题，它所对应的赢得矩阵存在鞍 点，任一局中人都不可能通过自己单方面的努力来改进结果。然而，在实际遇到的零和 对策中更典型的是山+V≠0的情况。由于赢得矩阵中不存在鞍点，此时在只使用纯策 略的范用内，对策问题无解。下面我们引进零和对童的混合策略。 设局中人1用概率x选用策略a,局中人Ⅱ用概率y选用策略阝， 三x=名，=1，起=，一，y=0“火Y,则同中人1的期望赢得为 E(x,y)=x'Ay。 记 S:策略 S:策略」月，B 概率x,.,xm 概率乃，.，y。 分别称S与S为局中人I和Ⅱ的混合策略 下面简单地记 S={x,.,xn)》1x,≥0，i=1.,m∑x=1, S={0,.,)1y,≥0j=1,.,m∑y,=1 定义4若存在m维概率向最x和n维概率向最卫，使得对一切m维概率向量x和 n维概率向最y有 Ay max x"Ay =minx"Ay 则称（任，）为混合策略对策问题的鞍点。 定理3设∈S,∈S,则(，列为G={S,S,；4的解的充要条件是 a,i=12.,m 定理4任意混合策略对策问题必存在鞍点，即必存在概率向量下和下，使得： -157

-157- 从而可得 μ +ν ≥ 0 ，但根据定理 1， μ +ν ≤ 0 必成立，故必有 μ +ν = 0。 上述定理给出了对策问题有稳定解（简称为解）的充要条件。当对策问题有解时， 其解可以不唯一，当解不唯一时，解之间的关系具有下面两条性质： 性质 1 无差别性。即若 ( , ) 1 1 αi β j 与 ( , ) 2 2 αi β j 是对策 G 的两个解，则必有 1 1 2 2 ai j = ai j 。 性质 2 可交换性。即若( , ) 1 1 αi β j 和( , ) 2 2 αi β j 是对策G 的两个解，则( , ) 1 2 αi β j 和 ( , ) 2 1 αi β j 也是解。 §3 零和对策的混合策略 具有稳定解的零和问题是一类特别简单的对策问题，它所对应的赢得矩阵存在鞍 点，任一局中人都不可能通过自己单方面的努力来改进结果。然而，在实际遇到的零和 对策中更典型的是 μ +ν ≠ 0的情况。由于赢得矩阵中不存在鞍点，此时在只使用纯策 略的范围内，对策问题无解。下面我们引进零和对策的混合策略。 设局中人Ⅰ用概率 i x 选用策略 αi ，局中人Ⅱ用概率 j y 选用策略 β j ， ∑ ∑ = = = = m i n j i j x y 1 1 1，记 T m x (x , , x ) = 1 L ， T n y ( y , , y ) = 1 L ，则局中人Ⅰ的期望赢得为 E x y x Ay T ( , ) = 。 记 * S1 ：策略 α α m , , 1 L * S2 ：策略 β β n , , 1 L 概率 m x , , x 1 L 概率 n y , , y 1 L 分别称 * S1 与 * S2 为局中人Ⅰ和Ⅱ的混合策略。 下面简单地记 {( , , ) | 0, 1, , ; 1} 1 1 * 1 = ≥ = ∑ = = m i i i T m S x L x x i L m x ， {( , , ) | 0, 1, , ; 1} 1 1 * 2 ∑= = ≥ = = n j j j T n S y L y y j L n y 定义4 若存在m 维概率向量 x 和n 维概率向量 y ，使得对一切m 维概率向量 x 和 n 维概率向量 y 有 x Ay x Ay x Ay T y T x T = max = min 则称(x, y) 为混合策略对策问题的鞍点。 定理 3 设 * S1 x ∈ ， * S2 y ∈ ，则(x, y) 为 { , ; } G = S1 S2 A 的解的充要条件是： ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ = ≤ = ∑ ∑ = = a x x Ay j n a y x Ay i m T i m i ij T n j ij j , 1,2, , , 1,2, , 1 1 L L 定理 4 任意混合策略对策问题必存在鞍点，即必存在概率向量 x 和 y ，使得：

y=max minx'Ay=minmaxx'Ay. 使用纯策略的对策问颗（具有稳定解的对策问颗）可以看成使用混合策略的对策问 题的特殊情况，相当于以概率1选取其中某一策略，以概率0选取其余策略。 例3A、B为作战双方，A方拟派两架轰炸机I和Ⅱ去轰炸B方的指挥部，轰 炸机I在前面飞行，Ⅱ随后。两架轰炸机中只有一架带有炸弹，而另一架仅为护航。轰 炸机飞至B方上空，受到B方战斗机的阻击。若战斗机阻击后面的轰炸机Ⅱ，它仅受 到胸架委拉技击中的概丰为0川来不及运回政击它若减斗机阻击 ,它将时受 ,被击中的概率为07。 旦战斗机未被击中，它将以0.6的概 。请为A、B双方各选择 个最优策略，即：对于A方应选择哪 选的筑略集分别 斗机应阻击哪一架轰炸机 S4={a,a2},a:轰炸机1装炸弹，Ⅱ护航 %：轰炸机Ⅱ装炸弹，I护航 S。={B,B},月：阻击轰炸机1 B,：阻击轰炸机川 赢得矩阵R=(a)22,a为A方采取策略a,而B方采取策略B,时，轰炸机轰炸 B方指挥部的概率 由题意可计算出 41=0.7+0.31-0.6)=0.82 a2=1,a21=1 =0.3+0.71-0.6)=0.58 R=08217 10.58 易求得μ=max mind,=0.82,v=-min maxa,=-l。由于μ+v≠0，矩阵 R不存在鞍点，应当求最佳混合策略。 现设A以概率x,取策略、以概率x,取策略2B以概率y取策略B,、以概 率y2取策略B。 先从B方来考虑问题。B采用B时，A方轰炸机攻击指挥部的概率期望值为 E(B)=0.82x+x,而B采用B,时，A方轰炸机攻击指挥部的概率的期望值为 E(B2)=x,+0.58x2·若E(B)≠E(B2),不妨设E(B)<E(B),则B方必采用B 以减少指挥部被轰炸的概率。故对A方选取的最佳概率x,和2，必满足： 0.82x,+x,=x,+0.58x +x3=1 即 x1+x2=1 -158

-158- x Ay x Ay x Ay T y x T x y T = maxmin = min max 。 使用纯策略的对策问题（具有稳定解的对策问题）可以看成使用混合策略的对策问 题的特殊情况，相当于以概率 1 选取其中某一策略，以概率 0 选取其余策略。 例 3 A、B 为作战双方， A 方拟派两架轰炸机Ⅰ和Ⅱ去轰炸 B 方的指挥部，轰 炸机Ⅰ在前面飞行，Ⅱ随后。两架轰炸机中只有一架带有炸弹，而另一架仅为护航。轰 炸机飞至 B 方上空，受到 B 方战斗机的阻击。若战斗机阻击后面的轰炸机Ⅱ，它仅受 Ⅱ的射击，被击中的概率为 0.3(Ⅰ来不及返回攻击它)。若战斗机阻击Ⅰ，它将同时受 到两架轰炸机的射击，被击中的概率为 0.7。一旦战斗机未被击中，它将以 0.6 的概率 击毁其选中的轰炸机。请为 A、B 双方各选择一个最优策略，即：对于 A 方应选择哪 一架轰炸机装载炸弹？对于 B 方战斗机应阻击哪一架轰炸机？ 解 双方可选择的策略集分别是 { , } A = α1 α 2 S ，α1 ：轰炸机Ⅰ装炸弹，Ⅱ护航 α2 ：轰炸机Ⅱ装炸弹，Ⅰ护航 { , } B = β1 β 2 S ， β1：阻击轰炸机Ⅰ β 2 ：阻击轰炸机Ⅱ 赢得矩阵 2 2 ( ) R = aij × ，aij 为 A 方采取策略αi 而 B 方采取策略 β j 时，轰炸机轰炸 B 方指挥部的概率，由题意可计算出： 0.7 0.3(1 0.6) 0.82 a11 = + − = 1 a12 = ， 1 a21 = 0.3 0.7(1 0.6) 0.58 a22 = + − = 即赢得矩阵 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ = 1 0.58 0.82 1 R 易求得 = max min = 0.82 ij i j μ a ， = −minmax = −1 ij j i ν a 。由于 μ +ν ≠ 0，矩阵 R 不存在鞍点，应当求最佳混合策略。 现设 A 以概率 1 x 取策略α1 、以概率 2 x 取策略α2 ； B 以概率 1 y 取策略 β1、以概 率 2 y 取策略 β 2 。 先从 B 方来考虑问题。 B 采用 β1 时， A 方轰炸机攻击指挥部的概率期望值为 1 1 2 E(β ) = 0.82x + x ，而 B 采用 β 2 时， A 方轰炸机攻击指挥部的概率的期望值为 2 1 2 E(β ) = x + 0.58x 。若 ( ) ( ) E β1 ≠ E β 2 ，不妨设 ( ) ( ) E β1 < E β 2 ，则 B 方必采用 β1 以减少指挥部被轰炸的概率。故对 A 方选取的最佳概率 1 x 和 2 x ，必满足： ⎩ ⎨ ⎧ + = + = + 1 0.82 0.58 1 2 1 2 1 2 x x x x x x 即 ⎩ ⎨ ⎧ + = + = + 1 1 2 11 1 21 2 12 1 22 2 x x a x a x a x a x

由此解得x=0.7,x2=0.3。 同样，可从A方考虑问题，得 0.82y+2=片+0.58y y+2=1 Ja月+a2y2=a2y+a22乃2 y+=1 并解得片=0.7,2=0.3。B方指挥部被轰炸的概率的期望值'。=0.874。 记零和对策G的解集为T(G),下面三个定理是关于对策解集性质的主要结果： 定理5设有两个零和对策 G={S,S2;A},G2={S,S2:A} 其中4={a},4={a,+,L为任一常数。则 (i)'a='o+L (i)T(G,)=T(G) 定理6设有两个零和对策 G={S,S2;A,G3={S1,S2:a4 其中a>0为任一常数。则 (i)Va.=ava (ii)T(G)=T(G2) 定理7设G={S,S2;A)为一零和对策，且A=-A'为反对称矩阵（亦称这种对 (i T(G)=T(G) 其中T(G)和T,(G)为局中人I和Ⅱ的最优策略集 4零和对策的线性规划解法 当m>2且n>2时，通常采用线性规划方法求解零和对策问题。 局中人I选择混合策略下的目的是使得 =maxminx'Ay=max min =maxmE,y 其中e,为贝有第j个分量为1而其余分量均为零的单位向量，E,=x'A,。记 59

-159- 由此解得 0.7 x1 = ， 0.3 x2 = 。 同样，可从 A 方考虑问题，得 ⎩ ⎨ ⎧ + = + = + 1 0.82 0.58 1 2 1 2 1 2 y y y y y y 即 ⎩ ⎨ ⎧ + = + = + 1 2 1 11 1 12 2 21 1 22 2 y y a y a y a y a y 并解得 0.7 y1 = ， 0.3 y2 = 。 B 方指挥部被轰炸的概率的期望值VG = 0.874 。 记零和对策G 的解集为T(G) ，下面三个定理是关于对策解集性质的主要结果： 定理 5 设有两个零和对策 { , ; } 1 1 2 A1 G = S S ， { , ; } G2 = S1 S2 A2 其中 { } A1 = aij ， { } A2 = aij + L ， L 为任一常数。则 （i）VG =VG + L 2 1 （ii） ( ) ( ) T G1 = T G2 定理 6 设有两个零和对策 { , ; } G1 = S1 S2 A ， { , ; } G2 = S1 S2 αA 其中α > 0 为任一常数。则 （i） G2 G1 V =αV （ii） ( ) ( ) T G1 = T G2 定理 7 设 { , ; } G = S1 S2 A 为一零和对策，且 T A = −A 为反对称矩阵（亦称这种对 策为对称对策）。则 （i）VG = 0 （ii） ( ) ( ) T1 G = T2 G 其中 ( ) T1 G 和 ( ) T2 G 为局中人Ⅰ和Ⅱ的最优策略集。 §4 零和对策的线性规划解法 当m > 2 且n > 2时，通常采用线性规划方法求解零和对策问题。 局中人Ⅰ选择混合策略 x 的目的是使得 j n j j x y n j j j T x y T x y T E y x Ay x Ay x A y e ∑ ∑ = = = = = 1 1 max min max min max min ( ) 其中 j e 为只有第 j 个分量为 1 而其余分量均为零的单位向量， j T Ej = x Ae 。记

=E。=minE,由于立y,=1,mn公Ey,在4=1，y,=0U≠k)时达到最 小值u,故x应为线性规划问题 max u 1 (2) x≥0，i=12,.,m 的解 同理，下应为线性规划 miny st∑y,=1 (3) y,20,j=1,2,n 的解。由线性规划知识，(2)与(3)互为对偶线性规划，它们具有相同的最优目标函 数值 不妨设u>0,作变换 X,=立，i=12.,m 则线性规划问题(2)化为： min∑x S.t 2a,2lj=l2,.,n x,20,i=12,.,m 同理，作变换 y y=,j=12.n 则线性规划问题(3)化为： -160-

-160- j j u ≡ Ek = min E ，由于 ∑= = n j j y 1 1， ∑= n j j j Y E y 1 min 在 yk = 1， y 0( j k) j = ≠ 时达到最 小值u ，故 x 应为线性规划问题 max u s.t. ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ = = ≥ = ≥ ∑ ∑ = = x i m x a x u j n E E i m i i m i ij i j k 0, 1,2, , 1 , 1,2, , ( ) 1 1 L L 即 （2） 的解。 同理， y 应为线性规划 min v s.t. ⎪ ⎪ ⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎪ ⎨ ⎧ ≥ = = ≤ = ∑ ∑ = = y j n y a y v i m j n j j n j ij j 0, 1,2, , 1 , 1,2, , 1 1 L L （3） 的解。由线性规划知识，（2）与（3）互为对偶线性规划，它们具有相同的最优目标函 数值。 不妨设u > 0 ，作变换 u x x i ' i = ，i = 1,2,L,m 则线性规划问题（2）化为： ∑= m i i x 1 min ' s.t. ⎪ ⎩ ⎪ ⎨ ⎧ ≥ = ∑ ≥ = = x i m a x j n i m i ij i ' 0, 1,2, , ' 1, 1,2, , 1 L L 同理，作变换 v y y j ' j = ， j = 1,2,L,n 则线性规划问题（3）化为：

max∑y ∑ay,≤L,i=l2,.,m S.L y,20,j=1,2,.,n 例4在一场敌对的军事行动中，甲方拥有三种进攻性武器A,A2,A,可分别用 于摧毁乙方工事：而乙方有三种防御性武器B,B,B,来对付甲方。据平时演习得到的 数据，各种武器间对抗时，相互取胜的可能如下： A对B2:1:A对B23:1:A对B1:2: 4对B3:7:4对B,3:2: 4对B1:3: A对B3:1:4对B21:4:A对B2:1 解先分别列出甲、乙双方的赢得的可能性矩阵，将甲方矩阵减去乙方矩阵的对应 元素，得零和对策时甲方的赢得矩阵如下： 「1/31/2-1/3 A=-2/51/5-1/2 1/2 -3/51/3 编写程序如下： 973,1/2,-1/3；-2/5,1/5,-1/2:1/2-/5,1/3110: 1,zeros(3,1): 9672n899{9meg3,1a,one33,1,1,1,2ero33,11: 解得x=(0.5283,0,0.4717),=(0,0.3774,0.6226),u=-0.0189,故乙 方有利。 下面我们使用式(2)和(3)，利用LNG0编程求例4的解。LNG0程序如下： model endsets ctr1=?:!ctx1取1求局中人1的策略，ctr1取0求局中人2的策略： c0:3333339 0.5-0.3333333 0.5-0.60.3333333: sagcuetrl-y(-ctr) (player1 (()()u) -161-

-161- ∑= m i i y 1 max ' s.t. ⎪ ⎩ ⎪ ⎨ ⎧ ≥ = ∑ ≤ = = y j n a y i m j n j ij j ' 0, 1,2, , ' 1, 1,2, , 1 L L 例 4 在一场敌对的军事行动中，甲方拥有三种进攻性武器 1 2 3 A , A , A ，可分别用 于摧毁乙方工事；而乙方有三种防御性武器 1 2 3 B ,B ,B 来对付甲方。据平时演习得到的 数据，各种武器间对抗时，相互取胜的可能如下： A1 对 B1 2：1； A1 对 B2 3：1； A1 对 B3 1：2； A2 对 B1 3：7； A2 对 B2 3：2； A2 对 B3 1：3； A3对 B1 3：1； A3对 B2 1：4； A3对 B3 2：1 解 先分别列出甲、乙双方的赢得的可能性矩阵，将甲方矩阵减去乙方矩阵的对应 元素，得零和对策时甲方的赢得矩阵如下： ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − − − − = 1/ 2 3/ 5 1/ 3 2 / 5 1/ 5 1/ 2 1/ 3 1/ 2 1/ 3 A 编写程序如下： 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 解得 T x = (0.5283,0, 0.4717) ， T y = (0, 0.3774, 0.6226) ， 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);

o(y((player2())) 8ap1ayr2: sets: dat 33333330.5-0.3333333 0.40.2 003333333: enddata efree(u); (i):c(i esum(player1:x)-1; endm(player2:y)- 、5二个非花数指高中人理局中人所赢得的值之和为一常数。显然·号 ,二人零 对于二人常数和对策，有纯策略对 策是相同的。 流高合英略对流。其求新方法与二人零和对 二人非常数和对策也称为双矩阵对策。也有纯策略对策和混合策略对策两种策略。 5.1纯策略问题 例1给出了典型的二人非常数和对策，每人的赢得矩阵是不相同的，因此称为双矩 阵对 问题分析 只能 个月纯那好的策同表看心犯绿藏人拒不 采用 策略 他可能 犯罪嫌疑 期为0为3年或 B也只能洗 因此，犯罪嫌疑人A一定 基于同样的道 们最好的选怪 白被判3 按照上面的论述，对于 般纯策略问题，局中人、Ⅱ的赢得矩阵如表2所示。其 中局中人I有m个策略a,a,局中人Ⅱ有n个策略B,B,分别记为 S1={a1,.,am},S2={B,.,fn} -162

-162- @for(player1(i):@sum(player2(j):c(i,j)*y(j))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 个策略α α m , , 1 L ，局中人 II 有n 个策略 β β n , , 1 L ，分别记为 { , , } S1 = α1 L α m ， { , , } S2 = β1 L β n

C=(c)为局中人I的赢得矩阵，C2=(c)为局中人Ⅱ的赢得矩阵。因此， 双矩阵对策记为 G=(S.S.C,C2 B、 B、 B a () (ci2,ciz) (cicia) (ca.c) (ci.cz) (cin,cn） (c (c2,c2) (c2m,c2) 定义5设G={S,S2,C,C}是一双矩阵对策，若等式 c=minmaxc,c min maxci (4) 成立，则记=C,并称为局中人的赢得值，记2=c子，并称为局中人山的 赢得值，称(@a,阝)为G在纯策略下的解（或Nash平衡点），称a.和B,分别为局中 人山，Ⅱ的最优纯策略。 实际上，定义5也同时给出了纯策略问题的求解方法。因此，对于例1，(1,0)，(1,0) 是Nash平衡点，这里(L,O)表示以概率1取第一个策略，也就是说，坦白是他们的最住策 52混合对问颗 如果不存在使式(4)成立的对策，则需要求混合对策。类似于二人零和对策情况， 需要给出混合对策的最优解。 (1)混合对策问题的基本概念 定义6在对策G={S,S2,C,C2}中，若存在策略对x∈S,y∈S,使得 [x'C≤xC,xeS xC'ysxc'y,Vyes: 则称（，）为G的一个非合作平衡点。记y=C,=C2,则称y,y,分别 为 人， 存在一个非合作平衡点 定理9混合策略（，习）为对策G={S,S2,C,C}的平衡点的充分必要条件是 ∑c,≤C,i=l2,.,m (5) (2)混合对策问题的求解方法 由定义6可知，求解混合对策就是求非合作对策的平衡点，进一步由定理8得到， 求解非合作对策的平衡点，就是求解满足不等式约束(5)的可行点。因此，混合对策

-163- ij m n C c = × ( ) 1 1 为局中人 I 的赢得矩阵， ij m n C c = × ( ) 2 2 为局中人 II 的赢得矩阵。因此， 双矩阵对策记为 { , , , } 1 2 G = S1 S2 C C 表 2 β1 β 2 . β n α1 ( , ) 2 11 1 11 c c ( , ) 2 12 1 12 c c . ( , ) 2 1 1 1n n c c α 2 ( , ) 2 21 1 21 c c ( , ) 2 22 1 22 c c . ( , ) 2 2 1 2n n c c M M M M α m ( , ) 2 1 1 m1 m c c ( , ) 2 2 1 m2 m c c . ( , ) 1 2 mn mn c c 定义5 设 { , , , } 1 2 G = S1 S2 C C 是一双矩阵对策，若等式 1 1 * * min max ij j i i j c = c ， 2 2 * * min max ij i j i j c = c （4） 成立，则记 1 1 * * i j v = c ，并称 1 v 为局中人I的赢得值，记 2 2 * * i j v = c ，并称 2 v 为局中人II的 赢得值，称( * , * ) i j α β 为G 在纯策略下的解（或Nash平衡点），称 * i α 和 * j β 分别为局中 人I，II的最优纯策略。 实际上，定义5也同时给出了纯策略问题的求解方法。因此，对于例1，((1,0),(1,0)) 是Nash平衡点，这里(1,0) 表示以概率1取第一个策略，也就是说，坦白是他们的最佳策 略。 5.2 混合对策问题 如果不存在使式（4）成立的对策，则需要求混合对策。类似于二人零和对策情况， 需要给出混合对策的最优解。 （1）混合对策问题的基本概念 定义6 在对策 { , , , } 1 2 G = S1 S2 C C 中，若存在策略对 * 2 * 1 x ∈ S , y ∈ S ，使得 ⎪⎩ ⎪ ⎨ ⎧ ≤ ∀ ∈ ≤ ∀ ∈ * 2 2 2 * 1 1 1 , , x C y x C y y S x C y x C y x S T T T T 则称(x, y)为G 的一个非合作平衡点。记v x C y T 1 1 = ，v x C y T 2 2 = ，则称 1 2 v , v 分别 为局中人I，II的赢得值。 对于混合对策问题有如下定理。 定理8 每个双矩阵对策至少存在一个非合作平衡点。 定理9 混合策略(x, y)为对策 { , , , } 1 2 G = S1 S2 C C 的平衡点的充分必要条件是 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≤ = ≤ = ∑ ∑ = = c x x C y j n c y x C y i m T i m i ij T n j ij j , 1,2, , , 1,2, , 2 1 2 1 1 1 L L （5） （2）混合对策问题的求解方法 由定义6可知，求解混合对策就是求非合作对策的平衡点，进一步由定理8得到， 求解非合作对策的平衡点，就是求解满足不等式约束（5）的可行点。因此，混合对策