运筹学讲稿（对策论(Theory of Games)）

对策论( Theory of games) 对策论也称博弈论,是运筹学的一个重要分支。1928年冯·诺意曼(J. von Neumann)等人由 于经济问题的启发,研究了一类具有某种特性的博弈问题,这是对策论的最早期的工作。在我国古 代的战国时期,“齐王与田忌赛马”就是一个非常典型的对策论的例子。对策论所研究的主要对象 是带有斗争性质(或至少含有斗争成分)的现象。由于对策论研究的对象与政治、军事、工业、农 业、交通、运输等领域有密切关系,处理问题的方法又有着明显的特色,所以越来越受到人们的注 意 日常生活中,经常看到一些具有相互之间斗争或竞争性质的行为,例如下棋、打牌、体育比赛 等,还如战争活动中的双方,都力图选取对自己最为有利的策略,千方百计去战胜对手,在政治方 面,国际间的谈判,各种政治力量之间的斗争。各国际集团之间的斗争等无一不具有斗争的性质 经济生活中,各国之间、各公司之间的各种经济谈判,企业为争夺市场而进行的竞争等,举不胜举 具有竞争或对抗性质的行为,称为对策行为。在这类行为中,参加斗争或竞争的各方各自具有 不同的目标和利益,为了达到各自的目标和利益各方必须考虑对手的各种可能的行动方案,并力图 选取对自己最为有利或最为合理的方案,对策论就是研究对策行为中斗争各方是否存在着最合理的 行动方案,以及如何找到这个合理的行动方案的数学理论和方法 在我国古代,“齐王赛马”就是一个典型的对策论研究的例子。 战国时期,齐王有一天提出要与大将田忌赛马。双方约定:从各自的上中下三个等级的马中选 一匹参赛。每匹马均只能参赛一次:每次比赛双方各出一匹马,负者要付给胜者千金。已经知道 在同等级的马中,田忌的马不如齐王的马,而如果田忌的马比齐王的马高一等级,则田忌的马可取 胜。当时,田忌手下的一个谋士给田忌出了个主意:每次比赛时先让齐王牵出他要参赛的马,然后 用下马对齐王的上马,用中马对齐王的下马,用上马对齐王的中马。比赛结果,田忌,二胜一负 可得千金,由此看来,两人各采取什么样的出马次序,对胜负是至关重要的。 还如日常生活中,儿童或喝酒中不会猜拳的用“石头一剪子一布”游戏也是带有竞争性质的现 象,大家都知道游戏的规定:第一,每人每局比赛中,只能在石头、剪子、布三种出法中选一种: 第二,在一局比赛中,石头对剪子认为石头赢,剪子对布认为剪子赢,布对石头认为布方赢,如果 双方都是同一种,则认为没有输赢。这样一局比赛中,各方是赢是输,不仅与自己所采取的发法(亦 称策略)有关,而且与对方所采取的出法有关,下面介绍对策论中的矩阵对策 §1对策问题的三个基本要求 以下称具有对策行为的模型为对策模型或对策。对策模型的种类可以千差万别,但本质上都必 须包括如下三个基本要素 (1)局中人 在一个对策行为(或一局对策)中,有权决定自己行动方案的对策参加者称为局中人,通常用 I表示局中人的集合,如果有n个局中人,则I={1.2…m},一般要求一个对策中至少要有二个局 中人,如在“齐王赛马”例子中,局中人是齐王与田忌 当然,对策中关于局中人的概念是具有广义性的,局中人除了可以理解为个人外,还可以理解 为某一集体

1 对策论(Theory of Games) 第 1、2 讲 对策论也称博弈论，是运筹学的一个重要分支。1928 年冯·诺意曼（J.von Neumann）等人由 于经济问题的启发，研究了一类具有某种特性的博弈问题，这是对策论的最早期的工作。在我国古 代的战国时期，“齐王与田忌赛马”就是一个非常典型的对策论的例子。对策论所研究的主要对象 是带有斗争性质（或至少含有斗争成分）的现象。由于对策论研究的对象与政治、军事、工业、农 业、交通、运输等领域有密切关系，处理问题的方法又有着明显的特色，所以越来越受到人们的注 意。 日常生活中，经常看到一些具有相互之间斗争或竞争性质的行为，例如下棋、打牌、体育比赛 等，还如战争活动中的双方，都力图选取对自己最为有利的策略，千方百计去战胜对手，在政治方 面，国际间的谈判，各种政治力量之间的斗争。各国际集团之间的斗争等无一不具有斗争的性质。 经济生活中，各国之间、各公司之间的各种经济谈判，企业为争夺市场而进行的竞争等，举不胜举。 具有竞争或对抗性质的行为，称为对策行为。在这类行为中，参加斗争或竞争的各方各自具有 不同的目标和利益，为了达到各自的目标和利益各方必须考虑对手的各种可能的行动方案，并力图 选取对自己最为有利或最为合理的方案，对策论就是研究对策行为中斗争各方是否存在着最合理的 行动方案，以及如何找到这个合理的行动方案的数学理论和方法。 在我国古代，“齐王赛马”就是一个典型的对策论研究的例子。 战国时期，齐王有一天提出要与大将田忌赛马。双方约定：从各自的上中下三个等级的马中选 一匹参赛。每匹马均只能参赛一次；每次比赛双方各出一匹马，负者要付给胜者千金。已经知道， 在同等级的马中，田忌的马不如齐王的马，而如果田忌的马比齐王的马高一等级，则田忌的马可取 胜。当时，田忌手下的一个谋士给田忌出了个主意：每次比赛时先让齐王牵出他要参赛的马，然后 用下马对齐王的上马，用中马对齐王的下马，用上马对齐王的中马。比赛结果，田忌，二胜一负， 可得千金，由此看来，两人各采取什么样的出马次序，对胜负是至关重要的。 还如日常生活中，儿童或喝酒中不会猜拳的用“石头—剪子—布”游戏也是带有竞争性质的现 象，大家都知道游戏的规定：第一，每人每局比赛中，只能在石头、剪子、布三种出法中选一种； 第二，在一局比赛中，石头对剪子认为石头赢，剪子对布认为剪子赢，布对石头认为布方赢，如果 双方都是同一种，则认为没有输赢。这样一局比赛中，各方是赢是输，不仅与自己所采取的发法（亦 称策略）有关，而且与对方所采取的出法有关，下面介绍对策论中的矩阵对策。 §1 对策问题的三个基本要求 以下称具有对策行为的模型为对策模型或对策。对策模型的种类可以千差万别，但本质上都必 须包括如下三个基本要素： (1)局中人 在一个对策行为（或一局对策）中，有权决定自己行动方案的对策参加者称为局中人，通常用 I 表示局中人的集合，如果有 n 个局中人，则 I={1.2……n}，一般要求一个对策中至少要有二个局 中人，如在“齐王赛马”例子中，局中人是齐王与田忌。 当然，对策中关于局中人的概念是具有广义性的，局中人除了可以理解为个人外，还可以理解 为某一集体

需要补充的一点是,在对策中总是假定每一个局中人都是理智的,聪明的决策者或竞争者。 即对任一局中人来讲,不存在利用其它局中人决策的失误,来扩大自身利益的可能性或相反。 (2)策略集 局对策中,可供局中人选择的一个实际可行的完整的行动方案称为一个策略,参加对策的每 局中人,i∈I都有自己的策略集S;’一般,每一局中人的策略集中至少应包括两个策略 在“齐王赛马”例子中,如用(上、中、下)表示以上马、中马、下马依次参赛次序,这是 个完整的行动方案,即为一个策略。可见,局中人齐王与田忌各自都有六个策略:(上、中、下) (上、下、中)、(中、上、下)、(中、下、上)、(下、中、上)、(下、上、中) (3)赢得函数(支付函数) 在一局对策中,当局势给定以后,就用一个数来表示得失(或输赢),显然,这种“得失”或“输 赢”是局势的函数,称为支付函数。 例如,S;是i个局中人的一个策略,则n个局中人的策略组 是一个局势,全体局势的集合S可用各局人策略集的笛卡尔积表示,即 S=s1×s2×…×sa 当局势出现后,对策结果也就确定了,即对任一局势s∈S,局中人I可能得到一个赢得H(s) 显然H(s)是局势s的函数,称为第Ⅰ个局中人的赢得函数(支付函数) 齐王赛马中,局中人集体I={1.2} 齐王的策略集用S1={a,a2a3.a4as.ad 田忌的策略集用S2={B.B2B3.B4B5Bd表示 这样齐王的任一策略α:和田忌的任一策略β,就决定了一个局势S,如果a=(上、中、下) β1=(上、中、下)则在局势S1下齐王的赢得值为H1(S1)=3 田忌的赢得值为H2(S1)=-3如此等等 般当这三个基本因素确定后,一个对策模型也就给定了,对策论的模型很多,如矩阵对策 连续对策、微分对策、阵地对策、随机对策等 在众多对策模型中占有重要地位的是二人有限零和对策对策,又称矩阵对策。矩阵对策是到目 前为止在理论硏究和求解方法方面比较完善的一类对策,而且这类对策的研究思想和理论结果又是 研究其它类型对策模型的基础,由于学时的限制,我们只能主要介绍矩阵对策的基本理论和方法。 §2矩阵对策 我们来看几个矩阵对策的例子 例1、我们称“石头一剪子一布”游戏是一个对策问题,设参加游戏的是甲、乙两人,他们的 策略集合都是{石头、剪子、布},也就是说他们在每一局比赛中都只能采取各自策略集合中的一个 策略,如果我们再规定,赢得的一方得一分,输的那方得-1分。显然,这个问题是两人有限零和对 策,即矩阵对策 我们可以列出甲、乙两人在一局比赛中的各种局势下的贏输分数。因为这是零和对策,故只 知道甲、乙任何一方在各种局势下的分数,就能够知道对分的情况了。 乙两人在各种局势下的得分情况如下表所示 2

2 需要补充的一点是，在对策中总是假定每一个局中人都是理智的，聪明的决策者或竞争者。 即对任一局中人来讲，不存在利用其它局中人决策的失误，来扩大自身利益的可能性或相反。 (2)策略集 一局对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个策略，参加对策的每 局中人，i∈I 都有自己的策略集 i S ，一般，每一局中人的策略集中至少应包括两个策略。 在“齐王赛马”例子中，如用（上、中、下）表示以上马、中马、下马依次参赛次序，这是一 个完整的行动方案，即为一个策略。可见，局中人齐王与田忌各自都有六个策略：（上、中、下）、 （上、下、中）、（中、上、下）、（中、下、上）、（下、中、上）、（下、上、中）。 (3)赢得函数（支付函数） 在一局对策中，当局势给定以后，就用一个数来表示得失（或输赢），显然，这种“得失”或“输 赢”是局势的函数，称为支付函数。 例如，Si 是 i 个局中人的一个策略，则 n 个局中人的策略组 S = （s1，s2 …sn） 是一个局势，全体局势的集合 S 可用各局人策略集的笛卡尔积表示，即 S = s1×s2×…×sn 当局势出现后，对策结果也就确定了，即对任一局势 s∈S，局中人 I 可能得到一个赢得 H（s）。 显然 Hi(s)是局势 s 的函数，称为第 I 个局中人的赢得函数（支付函数） 齐王赛马中，局中人集体 I={1.2} 齐王的策略集用 S1 = {α1,α2,α3,α4,α5,α6} 田忌的策略集用 S2 = {β1,β2,β3,β4,β5,β6}表示 这样齐王的任一策略αi 和田忌的任一策略βj，就决定了一个局势 Sij，如果α1=（上、中、下）、 β1 =（上、中、下）则在局势 S11 下齐王的赢得值为 H1（S11）=3。 田忌的赢得值为 H2（S11）=-3 如此等等 一般当这三个基本因素确定后，一个对策模型也就给定了，对策论的模型很多，如矩阵对策、 连续对策、微分对策、阵地对策、随机对策等。 在众多对策模型中占有重要地位的是二人有限零和对策对策，又称矩阵对策。矩阵对策是到目 前为止在理论研究和求解方法方面比较完善的一类对策，而且这类对策的研究思想和理论结果又是 研究其它类型对策模型的基础，由于学时的限制，我们只能主要介绍矩阵对策的基本理论和方法。 §2 矩阵对策 我们来看几个矩阵对策的例子。 例 1、我们称“石头—剪子—布”游戏是一个对策问题，设参加游戏的是甲、乙两人，他们的 策略集合都是{石头、剪子、布}，也就是说他们在每一局比赛中都只能采取各自策略集合中的一个 策略，如果我们再规定，赢得的一方得一分，输的那方得-1 分。显然，这个问题是两人有限零和对 策，即矩阵对策。 我们可以列出甲、乙两人在一局比赛中的各种局势下的赢输分数。因为这是零和对策，故只需 知道甲、乙任何一方在各种局势下的分数，就能够知道对分的情况了。 乙两人在各种局势下的得分情况如下表所示

乙的策略 石头 剪子 甲的得分 甲的策 剪子 0 如把表中数字用矩阵形式表示,则有 01 A=-10 1-1 我们称A为甲的应得矩阵 例2、(齐王赛马) 战国时期,齐王要与大将田忌赛马,双方约定: 从自己的上、中、下三个等级的马中各选出一匹进行比赛。每次比赛输者要付给赢者千金。就 同等级的马而言,齐王的马都比田忌的强,他们俩人的策略集合都是,{(上、中、下)、(上、下、 中)、(中、上、下)、(中、下、上)、(下、上、中)、(下、中、上)}并且可以知道,在每一局比赛 结束时,齐王和田忌任何一方赢得的千金数恰是对方输丢的千金数。可见这是两人有限零的对策。 即矩阵对策 齐王得千金数 田忌策略 (中 (中 (下、 (下 齐王策略 中、下 下、中 、上中 (上、中、下) (上、下、中) a3(中、上、下) (中、下、上) (下、中、上) 下表列出齐王在各种局势下赢得千金的数值,(表中-1表齐王输一千金)。 (矩阵)

3 如把表中数字用矩阵形式表示，则有 0 1 -1 A = -1 0 1 1 -1 0 我们称 A 为甲的应得矩阵. 例 2、（齐王赛马） 战国时期，齐王要与大将田忌赛马，双方约定： 从自己的上、中、下三个等级的马中各选出一匹进行比赛。每次比赛输者要付给赢者千金。就 同等级的马而言，齐王的马都比田忌的强，他们俩人的策略集合都是，{（上、中、下）、（上、下、 中）、（中、上、下）、（中、下、上）、（下、上、中）、（下、中、上）}并且可以知道，在每一局比赛 结束时，齐王和田忌任何一方赢得的千金数恰是对方输丢的千金数。可见这是两人有限零的对策。 即矩阵对策。 下表列出齐王在各种局势下赢得千金的数值，（表中-1 表齐王输一千金）。 （矩阵） 乙的策略 甲的得分 甲的策略 石头 剪子 布 石头 剪子 布 0 -1 1 1 0 -1 -1 1 0 齐王得千金数 田忌策略 齐王策略 β1 (上、 中、下) β2 (上、 下、中) β3 (中、 上、下) β4 (中、 下、上) β5 (下、 中、上) β6 ( 下 、上、中) α1（上、中、下） α2（上、下、中） α3（中、上、下） α4（中、下、上） α5（下、中、上） α6（下、上、中） 3 1 1 -1 1 1 1 3 -1 1 1 1 1 1 3 1 -1 1 1 1 1 3 1 -1 1 -1 1 1 3 1 -1 1 1 1 1 3

1311-1 11131 称作齐王的赢得矩阵 11 般情况,设两个局中人分别记为I、I,局中人I有m个策略a,a2…,an;局中人II有 n个策略β1,β2,…β。。用S1表示局中人Ⅰ的策略集合,S2表示局中人II的策略集合,即 S1={ S2={B1,β 为了与后面的概念区分开来,称α;为Ⅰ的纯策略,β;为ⅡI的纯策略,对于纯策略构成布局势 a,β;)称为纯局势。 局中人I的赢得矩阵记为 A A中的元素a表示在纯局势(a;,B1)下局中人I得分,也表示在同一局势下,局中人II得分 为 我们把矩阵对策记为 G={I,Ⅱ;s1,s2;A}或G={s,s2;A} 矩阵对策模型给定后,各局中人面临的问题是: 如何选择对自己最为有利的纯策略,以谋取最大的赢得(或最少损失),这就是所谓矩阵对策的 最优纯策略。 (一)矩阵对策的最优纯策略。 我们用一个例子来说明最优纯策略的概念。 例3、设有一矩阵对策G={s,s;A},其中S1={an,a2,a3,a,S2={B1,B2,Ba B B2 P3 324a

4 3 1 1 1 1 -1 1 3 1 1 -1 1 A= 1 -1 3 1 1 1 -1 1 1 3 1 1 称作齐王的赢得矩阵 1 1 -1 1 3 1 1 1 1 -1 1 3 一般情况，设两个局中人分别记为 I、II，局中人 I 有 m 个策略α1，α2…，αm；局中人 II 有 n 个策略β1，β2，…βn。用 S1 表示局中人 I 的策略集合，S2表示局中人 II 的策略集合，即 S1 = {α1，α2…，αm} S2 = {β1，β2，…βn} 为了与后面的概念区分开来，称αi 为 I 的纯策略，βj 为 II 的纯策略，对于纯策略构成布局势 （αi，βj）称为纯局势。 局中人 I 的赢得矩阵记为 11 a 12 a ... j a1 ... n a1 21 a 22 a … j a2 … a2n …………………… A = i1 a i2 a … ij a … in a …………………… am1 m2 a … mj a … amn A 中的元素αij表示在纯局势（αi，βj）下局中人 I 得分，也表示在同一局势下，局中人 II得分 为-αij。 我们把矩阵对策记为 G = {I，Ⅱ；s1，s2；A}或 G = {s1，s2；A} 矩阵对策模型给定后，各局中人面临的问题是： 如何选择对自己最为有利的纯策略，以谋取最大的赢得（或最少损失），这就是所谓矩阵对策的 最优纯策略。 第 3、4 讲 (一)矩阵对策的最优纯策略。 我们用一个例子来说明最优纯策略的概念。 例 3、设有一矩阵对策 G = {s1，s2；A},其中 S1 = {α1，α2，α3，α4}， S2 = {β1，β2，β3} 1  2  3 -6 1 -8 1 3 2 4  2 A = 9 -1 -10  3 -3 0 6  4

从A可看出,局中人Ⅰ的最大贏得是9,要想得到这个赢得,他就得选择纯策略α3。由于,假 定局中人I也是理智的,他考虑到了局中人I打算出a3的心理于是侵准备以β3对付之。使局中人 不但得不到9,反而失掉10,局中人Ⅰ当然也会猜到局中人II的这一心理,故想出a4来对付,使 局中人II得不到10而失掉6…,所以,如果双方都不想冒险,都不存在侥幸心理,而是考虑到 对方必然会设法使自己的所得最少这一点,就应该从各自可能出现的最不利的情形中选择一种最为 有利的情形作为决策的依据,这就是所谓“理智行为”,也是对策双方实际上都能接受的一种隐妥方 例3中,局中人I分析出纯策略α1,a2,α3,a4可能带来的最少赢得(矩阵A中每行的最小 元素)分别为 max{8,2,-10,-3}=2 在这些最少赢得(最不利的情形)中最好的结果(最有利的情形)是嬴得为2。因此,局中人I 只要以α2参加对策,无论局中人ⅡI取什么样的纯策略,都能保证局中人I的收入不会少于2,而出 其它纯策略,其收入都有可能小于2,甚至输给对方。因此,对局中人ⅠI来说,各纯策略β1,β2 β可能带来的对其最不利的结果(矩阵A中每列中最大元素)分别为 min 在这些最不利的结果中,最好的结果(输得最少)也是2,即局中人ⅠI只要选择纯策略β(无 论局中人Ⅰ采取什么纯策略,都能保持自己的支付不会多于2,而采取其它任何策略,都有可能使 自己的所失多于2。上面的分析表明,局中人Ⅰ、II的“理智行为”分别是,选择纯策略a2和β2, 这时局中人I的贏得值和局中人Ⅱ的所失值的绝对值相等(都是2),局中人Ⅰ是按最大最小原则 局中人II是按最小最大原则选择各自的纯策略,这对双方来说都是一种最为稳妥的行为,因此,a 2,β2分别为局中人Ⅰ、II的最优纯策略。 于是我们引出矩阵对策解的概念: 定义1设G={s,s;A}为矩阵对策,其中S1={a1,a },S2={B1,B2,…Bn} A={an}m×n若等式 max(mn ai )=min(max a 成立,记G=a,则称Ⅴ为对策G的值,上式称为成立的纯局势(aμ,βy)为G在纯策略下的 解(或平衡局势)。α,βμ分别称为局中人Ⅰ、II的最优纯策略。 由定义1可知,在矩阵对策中两个局中人都采取最优纯策略(如果最优纯策略存在)才是理智 的行动 例3中,对策解为(a2,β2),对策值为Va=2。 例4,求解矩阵对策G={s,s2;A},其中 4

5 从 A 可看出，局中人 I 的最大赢得是 9，要想得到这个赢得，他就得选择纯策略α3。由于，假 定局中人 II 也是理智的，他考虑到了局中人 I 打算出α3 的心理于是侵准备以β3 对付之。使局中人 不但得不到 9，反而失掉 10，局中人 I 当然也会猜到局中人 II 的这一心理，故想出α4 来对付，使 局中人 II 得不到 10 而失掉 6……，所以，如果双方都不想冒险，都不存在侥幸心理，而是考虑到 对方必然会设法使自己的所得最少这一点，就应该从各自可能出现的最不利的情形中选择一种最为 有利的情形作为决策的依据，这就是所谓“理智行为”，也是对策双方实际上都能接受的一种隐妥方 法。 例 3 中，局中人 I 分析出纯策略α1，α2，α3，α4 可能带来的最少赢得（矩阵 A 中每行的最小 元素）分别为： -8，②，-10，-3 max {-8，2，-10，-3}=2 在这些最少赢得（最不利的情形）中最好的结果（最有利的情形）是赢得为 2。因此，局中人 I 只要以α2 参加对策，无论局中人 II 取什么样的纯策略，都能保证局中人 I 的收入不会少于 2，而出 其它纯策略，其收入都有可能小于 2，甚至输给对方。因此，对局中人 II 来说，各纯策略β1，β2， β3 可能带来的对其最不利的结果（矩阵 A 中每列中最大元素）分别为： 9，②，6 min {9，2，6}=2 在这些最不利的结果中，最好的结果（输得最少）也是 2，即局中人 II 只要选择纯策略β2（无 论局中人 I 采取什么纯策略，都能保持自己的支付不会多于 2，而采取其它任何策略，都有可能使 自己的所失多于 2。上面的分析表明，局中人 I、II 的“理智行为”分别是，选择纯策略α2 和β2， 这时局中人 I 的赢得值和局中人 II 的所失值的绝对值相等（都是 2），局中人 I 是按最大最小原则。 局中人 II 是按最小最大原则选择各自的纯策略，这对双方来说都是一种最为稳妥的行为，因此，α 2，β2 分别为局中人 I、II 的最优纯策略。 于是我们引出矩阵对策解的概念： 定义 1 设 G = {s1，s2；A}为矩阵对策,其中 S1 = {α1，α2，…αm}，S2 = {β1，β2，…βn}。 A={aij}m×n 若等式 i max (min ) min(max ) aij = aij i j j i 成立,记 VG = ai*j*，则称 V 为对策 G 的值,上式称为成立的纯局势(αi*，βj*)为 G 在纯策略下的 解（或平衡局势）。αi*，βj*分别称为局中人 I、II 的最优纯策略。 由定义 1 可知，在矩阵对策中两个局中人都采取最优纯策略（如果最优纯策略存在）才是理智 的行动。 例 3 中，对策解为（α2，β2），对策值为 VG =2。 例 4，求解矩阵对策 G = {s1，s2；A}，其中 -7 1 -8 3 2 4 A= 16 -1 -3 -3 0 5

解:根据矩阵A有 min ai 1 -3 max a 于是 max( min a)=min( max a)=2 由定义1 VG=2,G的解为(a2,β2),a2,B2分别是局中人I和II的最优纯策略。 从例4可以看出,矩阵A的元素a2既是所在行的最小元素,又是所在列的最大元素,即 a2≤a22≤a2y i=1,2,3,4;j=1,2,3 将这一事实推广到一般矩阵对策,可得如下定理: 定理1矩阵对策G={s、s2;A}在纯策略意义下有解的充要条件是:存在纯局势 (a,b,),使得对一切i=1,2,…,m,j=1,2,…n均有 ≤a,,≤a 证(略) 为了便于对更为广泛的对策情况进行分析,现引进关于二元函数鞍点的概念: 定义2设f(x,y)为一个定义在x∈A及y∈B上的实值函数,如果存在x*∈A,y*∈B,使 得对一切,x∈A和y∈B,有 f(x,y*)≤∫(x*,y*)≤∫(x*,y) 则称(x*,y*)为函数S的一个鞍点 注1.由定义2及定理1可知,矩阵对策G在纯策略意义下有解,且VG=a;r的充要条件是:ar 是矩阵A的一个鞍点。在对策论中,矩阵A的鞍点也称为对策的鞍点。 定理1中或a,≤a≤a;的直观解释是: 如果a…既是矩阵A=(an)mxn中的第i'行的最小值。又是A中第j列的最大值,则a…是对 策的值,且(α,β)就是对策的解,其对策意义是:一个平衡局势(a,β,)应具有这样的 性质,当局中人Ⅰ选取了纯策略α后,局中人Ⅱ为了使其所失最小,只有选择纯策略β,否则就 可能丢的更多:;反之,当局中人Ⅱ选取了纯策略β;后,局中人Ⅰ为了得到最大的赢得也只能选取纯 策略a;。否则就会赢得更少,双方的竞争在局势(a,βj)下达到了一个平衡状态。 例5,设有矩阵对策G={s,sz;A},其中S1={a1,a2,as,al,S2={B,β2,B3,β4}, 贏得矩阵为

6 解：根据矩阵 A 有 于是 max(min aij) = min(max aij) = 2 i j j i 由定义 1 VG =2，G 的解为（α2，β2），α2，β2 分别是局中人 I 和 II 的最优纯策略。 从例 4 可以看出，矩阵 A 的元素 a22 既是所在行的最小元素，又是所在列的最大元素，即 ai2  a22  a2 j i=1,2,3,4； j=1,2,3 将这一事实推广到一般矩阵对策，可得如下定理： 定理 1 矩阵对策 G = {s1、s2；A}在纯策略意义下有解的充要条件是：存在纯局势 ( * , * ) i j a b ，使得对一切 i=1,2,…,m,j=1,2,…,n 均有 ij i j i j a *  a * *  a * 证（略） 为了便于对更为广泛的对策情况进行分析，现引进关于二元函数鞍点的概念： 定义 2 设 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*）为函数 S 的一个鞍点 注 1.由定义 2 及定理 1 可知，矩阵对策 G 在纯策略意义下有解，且 VG =ai*j*的充要条件是：ai*j* 是矩阵 A 的一个鞍点。在对策论中，矩阵 A 的鞍点也称为对策的鞍点。 定理 1 中或 ij i l i j a *  a * *  a * 的直观解释是： 如果 ai*j*既是矩阵 A = aij mn ( ) 中的第 i *行的最小值。又是 A 中第 j *列的最大值，则 ai*j*是对 策的值，且（αi*，βj*）就是对策的解，其对策意义是：一个平衡局势（αi*，βj*）应具有这样的 性质，当局中人 I 选取了纯策略αi*后，局中人Ⅱ为了使其所失最小，只有选择纯策略βj*，否则就 可能丢的更多；反之，当局中人Ⅱ选取了纯策略βj*后，局中人 I 为了得到最大的赢得也只能选取纯 策略αi*。否则就会赢得更少，双方的竞争在局势（αi*，βj*）下达到了一个平衡状态。 例 5，设有矩阵对策 G={s1，s2；A}，其中 1 S ={α1，α2，α3，α4}， 2 S ={β1，β2，β3，β4}， 赢得矩阵为 β1 β2 β3 min aij α1 α2 α3 α4 -7 3 16 -3 1 2 -1 0 -8 4 -3 5 -8 2 -3 -3 max ij a 16 2 5

6565 A142-1 0262 解:直接在A提供的赢得表上计算,有 B, B2 B3 P4 min 42-1-1 5 于是max( mina)=min(maxa1)=a=5 其中i’=1,3 j=2,4 故(a1,β2),(aβ,(a3,β2),(a3,β)四个局势都是对策的解,且VG=5 由此例可知,一般矩阵对策的解可以是不唯一的,当解不唯一时,解之间的关系具有下面两条 性质: 性质1无差别性,即若(aa,βn)和(a,βg)是对策G的两个解,则(aa,βn)和 (a,βg)也是解。 性质2可交换性,即若(α,βn)和(a2,βg)是对策G的两个解,则(a,βg)和 a2,βn)也是解。 证明留给读者。这两条性质表明,矩阵对策的值是唯一的 证明留给读者,这两条性质表明,矩阵对策的值是唯一的 下面举一个实际应用的例子 例6.某单位采购员在秋天要决定冬季取暖用煤的贮量问题,已知在正常的冬季气温条件要耗 煤15吨,在较暖与较冷的气温条件要消耗10吨和20吨,假定冬季时的煤价随天气寒冷程度而有所 变化,在较暖、正常、较冷的气候条件下每吨煤价分别为10元、15元和20元,又设秋季时煤价为 每吨10元,在没有关于当年冬季准确的气象预报的条件下,秋季贮煤多少吨,能使单位的支出最少? 解:这一贮量问题,可以看成是一个对策问题,把采购员当作局中人,他有三个策略,在秋天 时买10吨、15吨与20吨,分别论为a1、a2、a3 把大自然看作局中人II(可以当作理智的局中人来处理),大自然(冬季气温)有三种策略 出现较暖的、正常的、与较冷的各季,分别记为B1、β2、B3 现在把该单位冬季取暖用煤实际费用(即秋季时的购煤费用与冬季不够时再补购的费用总和, 作为局中人I的赢得,赢得矩阵如下

7 6 5 6 5 A = 1 4 2 -1 8 5 7 5 0 2 6 2 解：直接在 A 提供的赢得表上计算，有 1  2  3  4 min 1 6 5 6 5 * 5  2 1 4 2 -1 -1  3 8 5 7 5 * 5  4 0 2 6 2 0 max 8 * 5 7 * 5 于是 max(minaij)=min(maxail)=ai*j*=5 I j j i 其中 i * =1，3 j * =2，4 故 (α1，β2)，(α1，β4)，(α3，β2)，(α3，β4)四个局势都是对策的解，且 VG =5 由此例可知，一般矩阵对策的解可以是不唯一的，当解不唯一时，解之间的关系具有下面两条 性质： 性质 1 无差别性，即若（αi1，βj1）和（αi2，βj2）是对策 G 的两个解，则（αi1，βj2）和 （αi2，βj2）也是解。 性质 2 可交换性，即若（αi1，βj1）和（αi2，βj2）是对策 G 的两个解，则（αi1，βj2）和 （αi2，βj1）也是解。 证明留给读者。这两条性质表明，矩阵对策的值是唯一的 证明留给读者，这两条性质表明，矩阵对策的值是唯一的 下面举一个实际应用的例子 例 6. 某单位采购员在秋天要决定冬季取暖用煤的贮量问题，已知在正常的冬季气温条件要耗 煤 15 吨，在较暖与较冷的气温条件要消耗 10 吨和 20 吨，假定冬季时的煤价随天气寒冷程度而有所 变化，在较暖、正常、较冷的气候条件下每吨煤价分别为 10 元、15 元和 20 元，又设秋季时煤价为 每吨 10 元，在没有关于当年冬季准确的气象预报的条件下，秋季贮煤多少吨，能使单位的支出最少？ 解：这一贮量问题，可以看成是一个对策问题，把采购员当作局中人，他有三个策略，在秋天 时买 10 吨、15 吨与 20 吨，分别论为α1、α2、α3。 把大自然看作局中人 II（可以当作理智的局中人来处理），大自然（冬季气温）有三种策略， 出现较暖的、正常的、与较冷的各季，分别记为β1、β2、β3。 现在把该单位冬季取暖用煤实际费用（即秋季时的购煤费用与冬季不够时再补购的费用总和， 作为局中人 I 的赢得，赢得矩阵如下

B1(较暖)B2(正常)B3(较冷)min 175 300 a2(15顿)-150 a3(20顿)-200 200 200 max 200 max(min ai)=min(max a)=a33=-200 故对策解为(a3,β3),即秋季贮煤20吨合理,现在,我们会问,是否对于每一个决策G在纯 策略中都有解呢?上面所举的例3、4、5、6都是有解的,但也有在纯策略中没有解的对策,如例1 的“石头一剪子一布”对策,就没有解,因为从甲的贏得矩阵A中,我们可以算出。 mIn max max (mina;i)=-1+ min(maxair=l 所以“石头一剪子一布”游戏的对策问题中,在纯策略中无解 再如例2的,齐王赛马的对策。可以算出 B1 B2 B3 B4 Bs B min 1 3 max max(min a;i)=-1* min (max a;i )=3 故知在齐王赛马的对策中,双方都没有最优纯策略。 那么在纯策略意义下,没有解的对策问题,局中人又应如何选取策略参加对策呢?下讲我们来 解决这一问题。 第5、6讲 (二)矩阵对策的混合策略 由上节(讲)讨论可知,对矩阵对策G={s,s2;A}来说,局中人I有把握的至少赢得是

8 1 (较暖)  2 (正常)  3 (较冷) min 1 (10 顿) -100 -175 -300 -300 α2(15 顿) -150 -225 -225 -250 α3(20 顿) -200 -200 -200 -200 max -100 -150 -200 max(min aij) = min(max aij) = a33 = −200 i j j i 故对策解为（α3，β3），即秋季贮煤 20 吨合理，现在，我们会问，是否对于每一个决策 G 在纯 策略中都有解呢？上面所举的例 3、4、5、6 都是有解的，但也有在纯策略中没有解的对策，如例 1 的“石头—剪子—布”对策，就没有解，因为从甲的赢得矩阵 A 中，我们可以算出。 β1 β2 β3 min α1 0 1 -1 -1 α2 -1 0 1 -1 α3 1 -1 0 -1 max 1 1 1 max (minaij)= -1  min(maxaij)=1 i j j i 所以“石头—剪子—布”游戏的对策问题中，在纯策略中无解。 再如例 2 的，齐王赛马的对策。可以算出 β1 β2 β3 β4 β5 β6 min α1 3 1 1 1 1 -1 -1 α2 1 3 1 1 -1 1 -1 α3 1 -1 3 1 1 1 -1 α4 -1 1 1 3 1 1 -1 α5 1 1 -1 1 3 1 -1 α6 1 1 1 -1 1 3 -1 max 3 3 3 3 3 3 max(min aij)= -1  min (max aij)=3 i j j i 故知在齐王赛马的对策中，双方都没有最优纯策略。 那么在纯策略意义下，没有解的对策问题，局中人又应如何选取策略参加对策呢？下讲我们来 解决这一问题。 第 5、6 讲 (二)矩阵对策的混合策略 由上节(讲)讨论可知，对矩阵对策 G={s1，s2；A}来说，局中人 I 有把握的至少赢得是

=max (min a 局中人ⅠI有把握的至多损失是 V,=min( max ai j) 般,局中人I赢得不会多于局中人II的所失值,即总有V≤V2,当V1=V2时,矩阵对策G存在 纯策略意义下的解,且V=V1-V2。然而,一般情况不总是如此,实际中出现的复杂情况是V4=a2=V1 于是,当双方各根据最不利情形中选最有利结果的原则,选择纯策略时,应分别选取a2和β1此 时局中人Ⅰ将赢得5,比预期赢得v1=4还多,原因就在于局中人II选择了β1,使他的对手多得了 原来不该得的赢得,故β1对局中人II来说并不是最优的,因而也会考虑B2,局中人I亦会采取相 应的办法,改出α以使贏得为6,而局中人II又可能仍取策略β1来对付局中人Ⅰ的策略α1,这样, 局中人I出a1或α2的可能性及局中人ⅡI出β1或β2的可能性都不能排除,对两个局中人来说,不 存在一个双方均可接受的平衡局势,或者说当v<v2时,矩阵对策G不存在纯策略意义下的解,在这 种情况下,一个比较自然且合乎实际的想法是:既然各局中人没有最优纯策略可出,是否可以给出 一个选取不同策略的概率分布,如在例7中,局中人I可以制定如下一种策略:分别以概率1/4和 3/4选取纯策略α1和α2,这种策略是局中人I的策略集{a1,a2}上的一个概率分布,称之为混合 策略,同样,局中人∏Ⅰ也可制定这样一种混合策略:分别以概率1/2,1/2选取纯策略β,βz下 面给出矩阵对策混合策略的严格定义: 定义3设有矩阵对策G={s,sa;A},其中S1={a,a2,…an},S2={B1,β2,…Ba},A (a;)m×n,则我们把纯策略集合对应的概率问量 ≥0i=1,2, ∑ j=1,2,…,n:∑y

9 V1 =max(min aij) i j 局中人 II 有把握的至多损失是 V2 =min( max aij) j i 一般，局中人 I 赢得不会多于局中人 II 的所失值，即总有 V1≤V2，当 V1=V2 时，矩阵对策 G 存在 纯策略意义下的解，且 VG =V1-V2。然而，一般情况不总是如此，实际中出现的复杂情况是 V14= 22 a =V1 于是，当双方各根据最不利情形中选最有利结果的原则，选择纯策略时，应分别选取α2 和β1 此 时局中人 I 将赢得 5，比预期赢得 v1=4 还多，原因就在于局中人 II 选择了β1，使他的对手多得了 原来不该得的赢得，故β1 对局中人 II 来说并不是最优的，因而也会考虑β2，局中人 I 亦会采取相 应的办法，改出α1 以使赢得为 6，而局中人 II 又可能仍取策略β1 来对付局中人 I 的策略α1，这样， 局中人 I 出α1 或α2 的可能性及局中人 II 出β1 或β2 的可能性都不能排除，对两个局中人来说，不 存在一个双方均可接受的平衡局势，或者说当 v1<v2 时，矩阵对策 G 不存在纯策略意义下的解，在这 种情况下，一个比较自然且合乎实际的想法是：既然各局中人没有最优纯策略可出，是否可以给出 一个选取不同策略的概率分布，如在例 7 中，局中人 I 可以制定如下一种策略：分别以概率 1/4 和 3/4 选取纯策略α1 和α2，这种策略是局中人 I 的策略集{α1，α2}上的一个概率分布，称之为混合 策略，同样，局中人 II 也可制定这样一种混合策略：分别以概率 1/2,1/2 选取纯策略β1，β2，下 面给出矩阵对策混合策略的严格定义： 定义 3 设有矩阵对策 G = {s1，s2；A},其中 1 S ={α1，α2，…αn}， 2 S ={β1，β2，…βn}，A = （aij）m  n，则我们把纯策略集合对应的概率问量 X = （x1,x2 ,…,xM） T xi≥0 i=1,2,…,m; = m i X i 1 与 Y = （y1,y2,…yn） T yj≥0 j=1,2,…,n; = n j Yj 1

分别称作局中人Ⅰ、II的混合策略。(x,y)称一个混合局势。 个混合策略X=(x1,x2…xn)可设想成两个当局人多次重复进行对策G时,局中人I分别 采取纯策略q1,a2…a,的频率。 纯策略也可以看成是混合策略的特殊情况。例如局中人取纯策略α,则对应于局中人Ⅰ的混合 策略为(0,…,1,0…0)所以有时把混合策略简称为策略,(只进行一次对策,混合对策x=(x,x )可设想成局中人I对各纯策略的偏爱程度)。 如果局中人I选取的策略为X=(X12X2,…,Xn)「局中人I选取的策略为 Y=(H1,2…Fn) 由于两个局中人分别选取纯策略α,β;的事这件可以看成是相互独立的(随机事件),所以局 势(α;,β)出现的概率是x;y,从而局中人I赢得an的概率是x,βj,于是数学期望。 E(XY=2∑aXy 就是局中人I的赢得值 记S={X=(x1,X2,…,Xm),x201=12…,m∑X=1 S={Y=(,2…yn),y≥0,j=12,…,n∑y=1 E=E(x,y)|X∈S,Y∈S2 则称G'={S},S2;E 为G的混合扩充 设两个局中人仍象前面一样地进行有理智的对策,当局中人Ⅰ采取混合策略X时。他只能希望 获得(最不利的情形) min E(x, y) 因此局中人应选取x∈S',使上式取极大值(最不利当中的最有利情形),即局中人I可保证取 赢利的期望值不少于 max( min E (x, y)) ∈ 同理,局中人Ⅱ可保证自己所失期望值至多是 V2=min(maxE(x, y)) y∈s2x∈s1 注意到上二式v1、V2表达式是有意义的,且是s、s上的连续函数,仍然有v≤v2事实上 it max(minE (x, y))=E(x, y) x∈sy∈s2 min maxE(x, y)=E(x, y)

10 分别称作局中人 I、II 的混合策略。（x,y）称一个混合局势。 一个混合策略 X = （x1，x2…xm） T 可设想成两个当局人多次重复进行对策 G 时，局中人 I 分别 采取纯策略α1，α2…αm 的频率。 纯策略也可以看成是混合策略的特殊情况。例如局中人取纯策略αi，则对应于局中人 I 的混合 策略为（0,…0, 1,0…0）T 所以有时把混合策略简称为策略,(只进行一次对策,混合对策 x=（x1,x2,… xm）T 可设想成局中人 I 对各纯策略的偏爱程度)。 如果局中人 I 选 取 的 策 略 为 ( , , , ) X = X1 X2  X m T 局中人 II 选 取 的 策 略 为 T Y Y Y Yn ( , , , ) = 1 2  由于两个局中人分别选取纯策略αi，βj 的事这件可以看成是相互独立的（随机事件），所以局 势（αi，βj）出现的概率是 xiyj，从而局中人 I 赢得 aij 的概率是 xi，βj，于是数学期望。 E （X,Y） j m i n j ij i a X y = = = 1 1 就是局中人 I 的赢得值 记       = =  =  = = m i i T m i S X X X X X i m X 1 1 2 * 1 ( , ,, ) , 0, 1,2,, ; 1        = =  =  = = n j j j T S Y Y Y Yn Y j n Y 1 1 2 * 2 ( , ,, ) , 0, 1,2,, ; 1 E = {E（x,y）|X∈ * 1 S ，Y∈ * 2 S } 则称 * G ={ * 1 S ， * 2 S ； E } 为 G 的混合扩充 设两个局中人仍象前面一样地进行有理智的对策，当局中人 I 采取混合策略 X 时。他只能希望 获得（最不利的情形）。 min E (x,y) 因此局中人应选取 x∈S1 * ,使上式取极大值（最不利当中的最有利情形），即局中人 I 可保证取 赢利的期望值不少于 V1 = max ( min E (x,y) ) y∈s2 * x∈s1 * 同理，局中人Ⅱ可保证自己所失期望值至多是 V2 = min (maxE(x,y)) y∈s2 * x∈s1 * 注意到上二式 v1、v2 表达式是有意义的，且是 s1 *、s2 *上的连续函数，仍然有 v1≤v2 事实上 设 max(minE (x,y))= E (x,y* ) x∈s1 * y∈s2 * min max E (x,y)= E (x* ,y)