《数学建模》算法全收录（算法大全）：第07章对策论.pdf

第七章对策论 §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 。一般，每一局中人的策略集中至少应包括两个策略

-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 时，最坏的赢得结果分别为

-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

-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 ，使得：

-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

《数学建模》算法全收录（算法大全）：第07章 对策论

《数学建模》算法全收录（算法大全）：第07章对策论