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

对策论( 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 分。显然，这个问题是两人有限零和对策，即矩阵对策。我们可以列出甲、乙两人在一局比赛中的各种局势下的赢输分数。因为这是零和对策，故只需知道甲、乙任何一方在各种局势下的分数，就能够知道对分的情况了。乙两人在各种局势下的得分情况如下表所示

从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