第七章对策论 §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。 康疑犯B 供认 不供认 嫌疑犯A⊥不供认 (0,7) (7,0) 表1中每对数字表示嫌疑犯A、B被判刑的年数。如果两名疑犯均担心对方供认并希 望受到最轻的惩罚,最保险的办法自然是承认制造了伪币。 从这一简单实例中可以看出对策现象中包含有的几个基本要素 2.1对策的基本要素 (i)局中人 在一个对策行为(或一局对策)中,有权决定自己行动方案的对策参加者,称为局 中人。通常用Ⅰ表示局中人的集合.如果有n个局中人,则Ⅰ={1,2,…,n}。一般要求 个对策中至少要有两个局中人。在例1中,局中人是A、B两名疑犯。 (ⅱ)策略集 局对策中,可供局中人选择的一个实际可行的完整的行动方案称为一个策略。参 加对策的每一局中人i,i∈Ⅰ,都有自己的策略集S。一般,每一局中人的策略集中 至少应包括两个策略 -154
-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)赢得函数(支付函数) 在一局对策中,各局中人所选定的策略形成的策略组称为一个局势,即若S是第i 个局中人的一个策略,则n个局中人的策略组 就是一个局势。全体局势的集合S可用各局中人策略集的笛卡尔积表示,即 S=S1×S2×…×S 当局势出现后,对策的结果也就确定了。也就是说,对任一局势,s∈S,局中人 i可以得到一个赢得H1(s)。显然,H,(s)是局势s的函数,称之为第i个局中人的赢 得函数。这样,就得到一个向量赢得函数H(s)=(H1(s)…,Hn(s) 本节我们只讨论有两名局中人的对策问题,其结果可以推广到一般的对策模型中 22零和对策(矩阵对策) 零和对策是一类特殊的对策问题。在这类对策中,只有两名局中人,每个局中人都 只有有限个策略可供选择。在任一纯局势下,两个局中人的赢得之和总是等于零,即双 方的利益是激烈对抗的。 设局中人I、Ⅱ的策略集分别为 S1={a1,…,an},S2={B1,…,Bn 当局中人Ⅰ选定策略α1和局中人Ⅱ选定策略β,后,就形成了一个局势(α1,β,),可见 这样的局势共有m个。对任一局势(a1,B),记局中人I的赢得值为an,并称 a2a22 为局中人Ⅰ的赢得矩阵(或为局中人Ⅱ的支付矩阵)。由于假定对策为零和的,故局中 人Ⅱ的赢得矩阵就是-A。 当局中人Ⅰ、Ⅱ和策略集S1、S2及局中人I的赢得矩阵A确定后,一个零和对策 就给定了,零和对策又可称为矩阵对策并可简记成 G={S1,S2;4}。 例2设有一矩阵对策G={S1S2,4,其中S1={a1,a2,a3} S2={B13B2,B3,B4}, 12-630 A=1421810 60-1016 从A中可以看出,若局中人Ⅰ希望获得最大贏利30,需采取策略a1,但此时若局 中人Ⅱ采取策略B4,局中人I非但得不到30,反而会失去22。为了稳妥,双方都应考 虑到对方有使自己损失最大的动机,在最坏的可能中争取最好的结果,局中人Ⅰ采取策 略a1、a2、a3时,最坏的赢得结果分别为
-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 min{14,2,18.10)}=2 min{-6,0.-10,16}=-10 其中最好的可能为max{-22,2,-10}=2。如果局中人I采取策略∝2,无论局中人Ⅱ 采取什么策略,局中人Ⅰ的赢得均不会少于2 局中人Ⅱ采取各方案的最大损失为max{12,14,-6}=14,max{-6,2,0} max{30.18-10}=30,和max{-2210.1l6}=16。当局中人Ⅱ采取策略B2时,其损 失不会超过2。注意到在赢得矩阵中,2既是所在行中的最小元素又是所在列中的最大 元素。此时,只要对方不改变策略,任一局中人都不可能通过变换策略来增大赢得或减 少损失,称这样的局势为对策的一个稳定点或稳定解 定义1设f(x,y)为一个定义在x∈A及y∈B上的实值函数,如果存在x*∈A, ∈B,使得对一切x∈A和y∈B,有 f(x,y*)≤∫(x*,y*)≤∫(x*,y) 则称(x*,y*)为函数∫的一个鞍点 定义2设G={S12S2A}为矩阵对策,其中S1={a2a2;…,∝m} S2={B1,B2…,Bn},A=(an)mm°若等式 max mind.=min maxa.=d (1) 成立,记VG=a…则称G为对策G的值,称使(1)式成立的纯局势(ax…,B,)为 对策G的鞍点或稳定解,赢得矩阵中与(a,B,)相对应的元素a…称为赢得矩阵的鞍 点,α,与β,分别称为局中人I与Ⅱ的最优纯策略 给定一个对策G,如何判断它是否具有鞍点呢?为了回答这一问题,先引入下面 的极大极小原理。 定理1设G={S,S2;4},记H= max mina,v=-minn max a 则必有 +v≤0。 证明v= maxmin(-an),易见为I的最小赢得,v为Ⅱ的最小赢得,由于G 是零和对策,故+v≤0必成立。 定理2零和对策G具有稳定解的充要条件为4+v=0。 证明:(充分性)由和v的定义可知,存在一行例如P行,为p行中的最小元 素,且存在一列例如q列,一v为q列中的最大元素。故有 ap≥且ap≤-V 又因+v=0,所以=-V,从而得出am=,am为赢得矩阵的鞍点,(an,B) 为G的稳定解 (必要性)若G具有稳定解(ap,B),则ap为赢得矩阵的鞍点。故有 A=maxminay2minap=apg v= minmaxa, s max aig=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
从而可得+v≥0,但根据定理1,+v≤0必成立,故必有+v=0。 上述定理给出了对策问题有稳定解(简称为解)的充要条件。当对策问题有解时, 其解可以不唯一,当解不唯一时,解之间的关系具有下面两条性质: 性质1无差别性。即若(a1,B1)与(a2,Bb)是对策G的两个解,则必有 性质2可交换性。即若(n,B1)和(an2B2)是对策G的两个解,则(an1,月2)和 (a,B1)也是解。 §3零和对策的混合策略 具有稳定解的零和问题是一类特别简单的对策问题,它所对应的赢得矩阵存在鞍 点,任一局中人都不可能通过自己单方面的努力来改进结果。然而,在实际遇到的零和 对策中更典型的是μ+ν≠0的情况。由于贏得矩阵中不存在鞍点,此时在只使用纯策 略的范围内,对策问题无解。下面我们引进零和对策的混合策略 设局中人Ⅰ用概率x选用策略∝,局中人Ⅱ用概率y选用策略β ∑x=∑y=1,记x=(x1…xm),y=(n,…,y),则局中人的期望赢得为 E(x, y)=x' Ay 策略 B1,…,Bn 概率 分别称S1与S2为局中人Ⅰ和Ⅱ的混合策略。 下面简单地记 S={(x,…,xn)1x≥0,=1…,m,∑x=1 S={0…yn)1y≥0,j=1…,n∑y=1} 定义4若存在m维概率向量x和n维概率向量y,使得对一切m维概率向量x和 n维概率向量y有 x Ay= max x' Ay= min x Ay 则称(x,y)为混合策略对策问题的鞍点 定理3设x∈S1,j∈S2,则(x,y)为G={S1,S2A的解的充要条件是 ∑a≤x行,1=12,…m a.x.≥x 定理4任意混合策略对策问题必存在鞍点,即必存在概率向量x和,使得:
-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 ，使得：
x ay= max min x Ay= min max xAy 使用纯策略的对策问题(具有稳定解的对策问题)可以看成使用混合策略的对策问 题的特殊情况,相当于以概率1选取其中某一策略,以概率0选取其余策略 例3A、B为作战双方,A方拟派两架轰炸机Ⅰ和Ⅱ去轰炸B方的指挥部,轰 炸机Ⅰ在前面飞行,Ⅱ随后。两架轰炸机中只有一架带有炸弹,而另一架仅为护航。轰 炸机飞至B方上空,受到B方战斗机的阻击。若战斗机阻击后面的轰炸机Ⅱ,它仅受 Ⅱ的射击,被击中的概率为0.3(I来不及返回攻击它)。若战斗机阻击I,它将同时受 到两架轰炸机的射击,被击中的概率为0.7。一旦战斗机未被击中,它将以06的概率 击毁其选中的轰炸机。请为A、B双方各选择一个最优策略,即:对于A方应选择哪 一架轰炸机装载炸弹?对于B方战斗机应阻击哪一架轰炸机? 解双方可选择的策略集分别是 SA={α13aα2},∝1:轰炸机I装炸弹,Ⅱ护航 α2:轰炸机Ⅱ装炸弹,I护航 SB={B1,B2},B1:阻击轰炸机 B2:阻击轰炸机Ⅱ 赢得矩阵R=(an)2x2,4为A方采取策略a而B方采取策略B时,轰炸机轰炸 B方指挥部的概率,由题意可计算出: a1=0.7+0.3(1-0.6)=0.82 a2=0.3+0.7(1-0.6)=0.58 即赢得矩阵 0.821 R 10.58 易求得H= max mind=0.82,V=- min max d=-1。由于H+v≠0,矩阵 R不存在鞍点,应当求最佳混合策略。 现设A以概率x1取策略α1、以概率x2取策略α2;B以概率η取策略β、以概 率y2取策略B2 先从B方来考虑问题。B采用β1时,A方轰炸机攻击指挥部的概率期望值为 E(B1)=0.82x+x2,而B采用B2时,A方轰炸机攻击指挥部的概率的期望值为 E(B2)=x1+0.58x2。若E(B1)≠E(B2),不妨设E(B1)<E(B2),则B方必采用B1 以减少指挥部被轰炸的概率。故对A方选取的最佳概率x1和x2’必满足: 0.82x,+ 0.58 a1x1+a21x2=a12x1+a2x2 x1+x2
-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
由此解得x1=0.7,x2=0.3。 同样,可从A方考虑问题,得 0.82y1+y2=y1+0.58y2 Jav+a12y2=a213+a222 y1+y2 并解得y=0.7,y2=0.3。B方指挥部被轰炸的概率的期望值VG=0.874。 记零和对策G的解集为T(G),下面三个定理是关于对策解集性质的主要结果: 定理5设有两个零和对策 G1={S,S2;41},G2={S12S2;A2} 其中A={an},A2={an+D},L为任一常数。则 i)VG=VG+L (i)T(G1)=7(G2) 定理6设有两个零和对策 G1={S1,S2,A} {S2S2;a4 其中a>0为任一常数。则 (i)VG,=aVo (i)T(G1)=7(G2) 定理7设G={S,S2A}为一零和对策,且A=-A为反对称矩阵(亦称这种对 策为对称对策)。则 (i)T(G)=72(G 其中T(G)和T2(G为局中人Ⅰ和Ⅱ的最优策略集 §4零和对策的线性规划解法 当m>2且n>2时,通常采用线性规划方法求解零和对策问题。 局中人Ⅰ选择混合策略x的目的是使得 xAy=max Ay= max minx'ACLye) =max min ∑Ey 其中e为只有第j个分量为1而其余分量均为零的单位向量,E=xAe。记
-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,m∑E在y=1,y=0≠)时达到最 小值u,故x应为线性规划问题 max ll n(即E,≥Ek) 的解 同理,应为线性规划 mIn v diy y,=1 (3) 0 J 的解。由线性规划知识,(2)与(3)互为对偶线性规划,它们具有相同的最优目标函 数值。 不妨设u>0,作变换 则线性规划问题(2)化为: mIr x1≥1,j= x1≥0 同理,作变换 y 则线性规划问题(3)化为:
-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）化为：
any,≤1,i=1 s t.j= y≥0,j=12,… 例4在一场敌对的军事行动中,甲方拥有三种进攻性武器A1,A2,A3,可分别用 于摧毁乙方工事;而乙方有三种防御性武器B1,B2,B3来对付甲方。据平时演习得到的 数据,各种武器间对抗时,相互取胜的可能如下: A1对B A 对B 1;A1对B311:2 A2对B13:7;A2对B23:2:A2对B1:3; A3对B13:1;A3对B21:4;A3对B32:1 解先分别列出甲、乙双方的赢得的可能性矩阵,将甲方矩阵减去乙方矩阵的对应 元素,得零和对策时甲方的赢得矩阵如下: 1/31/2-1/3 A=-2/51/5-1/2 1/2-3/51/3 编写程序如下 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的数 z0,u]=1 inprog(ones(3,1),-a",-ones(3,1),[],[], zeros(3,1)); x=xO/u, u=l/u-b [y0,v]=1 inprog(-ones(3,1),a,ones(3,1),[],[], zeros(3,1)) y=y0/(-v),v=1/(-v)-b 解得x=(0.5283,0,04717),j=(0,03774,0626),u=-00189,故乙 方有利。 下面我们使用式(2)和(3),利用 LINGO编程求例4的解。 LINGO程序如下 sets player1/1.3/: x player2/1.3/: y: game(player, player2): c ndset data ctr1=?;!ctri取1求局中人1的策略,ctrl取0求局中人2的策略; c=0.33333330.5-0.3333333 0.40.2-0.5 0.5-0.60.3333333 enddata max=u*ctrl-v*(l-ctrl @for(player2 (3): Gsum(playerl (i:c(1,3)*x(1))>u)i
-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);
@for(player(i): @sum(player2():c(i, j)*y(3))u)i @sum(player: x)=1 @sum(player2: y)=l end §5二人非常数和对策 所谓常数和对策是指局中人I和局中人Ⅱ所赢得的值之和为一常数。显然,二人零 和对策是二人常数和对策的特例,即常数为零。 对于二人常数和对策,有纯策略对策和混合策略对策,其求解方法与二人零和对 策是相同的 二人非常数和对策也称为双矩阵对策。也有纯策略对策和混合策略对策两种策略。 5.1纯策略问题 例1给出了典型的二人非常数和对策,每人的赢得矩阵是不相同的,因此称为双矩 阵对策。 问题分析 这是一个二人非常数和对策问题。从表面上看,两犯罪嫌疑人拒不供认,只能被 判18个月徒刑,结果是最好的。但仔细分析,却无法做到这一点。因为犯罪嫌疑人A如 果采用不供认策略,他可能被判刑的刑期为18个月或7年,而犯罪嫌疑人B可能判的刑 期为0或18个月。而A选择供认,他被判的刑期为0或3年,此时,犯罪嫌疑人B可能判 的刑期为3年或7年。因此,犯罪嫌疑人A一定选择供认。基于同样的道理,犯罪嫌疑 人B也只能选择供认。 选择供认是他们最好的选择,各自被判3年。 按照上面的论述,对于一般纯策略问题,局中人I、Ⅱ的赢得矩阵如表2所示。其 中局中人I有m个策略α1…,∝m,局中人Ⅱ有n个策略B,…,Bn,分别记为 S1={a1…,m},S2={B1,…,Bn}
-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)mn为局中人1的赢得矩阵,C2=(c2)mn为局中人Ⅱ的赢得矩阵。因此 双矩阵对策记为 {S1,S2,C,C2} 表2 B2 B (c12c2) 定义5设G={S1,S2,C,C2}是一双矩阵对策,若等式 ii-minmaxc,c4 min max c2 (4) 成立,则记v=c,并称n1为局中人的赢得值,记v2=C,并称"2为局中人Ⅱ的 赢得值,称(a,,β.)为G在纯策略下的解(或Nash平衡点),称a,和B.分别为局中 人L,Ⅱ的最优纯策略。 实际上,定义5也同时给出了纯策略问题的求解方法。因此,对于例1,(1,0),(1,0) 是Nash平衡点,这里(1,0)表示以概率l取第一个策略,也就是说,坦白是他们的最佳策 略。 52混合对策问题 如果不存在使式(4)成立的对策,则需要求混合对策。类似于二人零和对策情况, 需要给出混合对策的最优解。 (1)混合对策问题的基本概念 定义6在对策G={S1,S2C",C2}中,若存在策略对x∈S1,y∈S2,使得 xCJ≤xC"y,vx∈S xCy≤xC2j,v∈S2 则称(x,y为G的一个非合作平衡点。记v1=xCp,n2=xC2J,则称v1,v2分别 为局中人I,Ⅱ的贏得值。 对于混合对策问题有如下定理 定理8每个双矩阵对策至少存在一个非合作平衡点。 定理9混合策略(xy)为对策G={S1,S2C,C2}的平衡点的充分必要条件是 %5≤xCy,1=12,…,m (5) ≤xC 2元 (2)混合对策问题的求解方法 由定义6可知,求解混合对策就是求非合作对策的平衡点,进一步由定理8得到 求解非合作对策的平衡点,就是求解满足不等式约束(5)的可行点。因此,混合对策 163
-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）的可行点。因此，混合对策