《博弈论 microsoft word 文档.doc》由会员分享，可在线阅读，更多相关《博弈论 microsoft word 文档.doc（17页珍藏版）》请在金锄头文库上搜索。
1、对策论(Theory of Games)第1、2讲对策论也称博弈论，是运筹学的一个重要分支。1928年冯诺意曼（J.von Neumann）等人由于经济问题的启发，研究了一类具有某种特性的博弈问题，这是对策论的最早期的工作。在我国古代的战国时期，“齐王与田忌赛马”就是一个非常典型的对策论的例子。对策论所研究的主要对象是带有斗争性质（或至少含有斗争成分）的现象。由于对策论研究的对象与政治、军事、工业、农业、交通、运输等领域有密切关系，处理问题的方法又有着明显的特色，所以越来越受到人们的注意。日常生活中，经常看到一些具有相互之间斗争或竞争性质的行为，例如下棋、打牌、体育比赛等，还如战争活动中的双方
2、，都力图选取对自己最为有利的策略，千方百计去战胜对手，在政治方面，国际间的谈判，各种政治力量之间的斗争。各国际集团之间的斗争等无一不具有斗争的性质。经济生活中，各国之间、各公司之间的各种经济谈判，企业为争夺市场而进行的竞争等，举不胜举。具有竞争或对抗性质的行为，称为对策行为。在这类行为中，参加斗争或竞争的各方各自具有不同的目标和利益，为了达到各自的目标和利益各方必须考虑对手的各种可能的行动方案，并力图选取对自己最为有利或最为合理的方案，对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。在我国古代，“齐王赛马”就是一个典型的对策论研究的例
3、子。战国时期，齐王有一天提出要与大将田忌赛马。双方约定：从各自的上中下三个等级的马中选一匹参赛。每匹马均只能参赛一次；每次比赛双方各出一匹马，负者要付给胜者千金。已经知道，在同等级的马中，田忌的马不如齐王的马，而如果田忌的马比齐王的马高一等级，则田忌的马可取胜。当时，田忌手下的一个谋士给田忌出了个主意：每次比赛时先让齐王牵出他要参赛的马，然后用下马对齐王的上马，用中马对齐王的下马，用上马对齐王的中马。比赛结果，田忌，二胜一负，可得千金，由此看来，两人各采取什么样的出马次序，对胜负是至关重要的。还如日常生活中，儿童或喝酒中不会猜拳的用“石头剪子布”游戏也是带有竞争性质的现象，大家都知道游戏的规定
4、：第一，每人每局比赛中，只能在石头、剪子、布三种出法中选一种；第二，在一局比赛中，石头对剪子认为石头赢，剪子对布认为剪子赢，布对石头认为布方赢，如果双方都是同一种，则认为没有输赢。这样一局比赛中，各方是赢是输，不仅与自己所采取的发法（亦称策略）有关，而且与对方所采取的出法有关，下面介绍对策论中的矩阵对策。1对策问题的三个基本要求以下称具有对策行为的模型为对策模型或对策。对策模型的种类可以千差万别，但本质上都必须包括如下三个基本要素：(1)局中人在一个对策行为（或一局对策）中，有权决定自己行动方案的对策参加者称为局中人，通常用I表示局中人的集合，如果有n个局中人，则I=1.2n，一般要求一个对策
5、中至少要有二个局中人，如在“齐王赛马”例子中，局中人是齐王与田忌。当然，对策中关于局中人的概念是具有广义性的，局中人除了可以理解为个人外，还可以理解为某一集体。需要补充的一点是，在对策中总是假定每一个局中人都是理智的，聪明的决策者或竞争者。即对任一局中人来讲，不存在利用其它局中人决策的失误，来扩大自身利益的可能性或相反。(2)策略集一局对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个策略，参加对策的每局中人，iI都有自己的策略集，一般，每一局中人的策略集中至少应包括两个策略。在“齐王赛马”例子中，如用（上、中、下）表示以上马、中马、下马依次参赛次序，这是一个完整的行动方案，即为一个
6、策略。可见，局中人齐王与田忌各自都有六个策略：（上、中、下）、（上、下、中）、（中、上、下）、（中、下、上）、（下、中、上）、（下、上、中）。(3)赢得函数（支付函数）在一局对策中，当局势给定以后，就用一个数来表示得失（或输赢），显然，这种“得失”或“输赢”是局势的函数，称为支付函数。例如，Si是i个局中人的一个策略，则n个局中人的策略组（s1，s2 sn）是一个局势，全体局势的集合S可用各局人策略集的笛卡尔积表示，即s1s2sn当局势出现后，对策结果也就确定了，即对任一局势sS，局中人I可能得到一个赢得H（s）。显然Hi(s)是局势s的函数，称为第I个局中人的赢得函数（支付函数）齐王赛马中，
7、局中人集体I=1.2齐王的策略集用1,2,3,4,5,6田忌的策略集用1,2,3,4,5,6表示这样齐王的任一策略i 和田忌的任一策略j，就决定了一个局势Sij，如果1=（上、中、下）、1 =（上、中、下）则在局势S11下齐王的赢得值为H1（S11）=3。田忌的赢得值为H2（S11）=-3 如此等等一般当这三个基本因素确定后，一个对策模型也就给定了，对策论的模型很多，如矩阵对策、连续对策、微分对策、阵地对策、随机对策等。在众多对策模型中占有重要地位的是二人有限零和对策对策，又称矩阵对策。矩阵对策是到目前为止在理论研究和求解方法方面比较完善的一类对策，而且这类对策的研究思想和理论结果又是研究其它
8、类型对策模型的基础，由于学时的限制，我们只能主要介绍矩阵对策的基本理论和方法。2 矩阵对策我们来看几个矩阵对策的例子。例1、我们称“石头剪子布”游戏是一个对策问题，设参加游戏的是甲、乙两人，他们的策略集合都是石头、剪子、布，也就是说他们在每一局比赛中都只能采取各自策略集合中的一个策略，如果我们再规定，赢得的一方得一分，输的那方得-1分。显然，这个问题是两人有限零和对策，即矩阵对策。我们可以列出甲、乙两人在一局比赛中的各种局势下的赢输分数。因为这是零和对策，故只需知道甲、乙任何一方在各种局势下的分数，就能够知道对分的情况了。乙两人在各种局势下的得分情况如下表所示 乙的策略 甲的得分甲的策略石头剪
9、子布石头剪子布0-1 110-1-110如把表中数字用矩阵形式表示，则有 0 1 -1 -1 0 1 1 -1 0我们称为甲的应得矩阵.例2、（齐王赛马）战国时期，齐王要与大将田忌赛马，双方约定：从自己的上、中、下三个等级的马中各选出一匹进行比赛。每次比赛输者要付给赢者千金。就同等级的马而言，齐王的马都比田忌的强，他们俩人的策略集合都是，（上、中、下）、（上、下、中）、（中、上、下）、（中、下、上）、（下、上、中）、（下、中、上）并且可以知道，在每一局比赛结束时，齐王和田忌任何一方赢得的千金数恰是对方输丢的千金数。可见这是两人有限零的对策。即矩阵对策。下表列出齐王在各种局势下赢得千金的数值，（
10、表中-1表齐王输一千金）。齐王得千金数 田忌策略 齐王策略1(上、中、下)2(上、下、中)3(中、上、下)4(中、下、上)5(下、中、上)6(下、上、中)1（上、中、下）2（上、下、中）3（中、上、下）4（中、下、上）5（下、中、上）6（下、上、中）311-11113-11111131-1111131-11-11131-111113（矩阵） 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；局中
11、人II有n个策略1，2，n。用S1表示局中人I的策略集合，S2表示局中人II的策略集合，即1，2，m1，2，n为了与后面的概念区分开来，称i为I的纯策略，j为II的纯策略，对于纯策略构成布局势（i，j）称为纯局势。局中人I的赢得矩阵记为 . . 中的元素ij表示在纯局势（i，j）下局中人I得分，也表示在同一局势下，局中人II得分为-ij。我们把矩阵对策记为I，；s1，s2；A或s1，s2；A矩阵对策模型给定后，各局中人面临的问题是：如何选择对自己最为有利的纯策略，以谋取最大的赢得（或最少损失），这就是所谓矩阵对策的最优纯策略。第3、4讲(一)矩阵对策的最优纯策略。我们用一个例子来说明最优纯策略
12、的概念。例3、设有一矩阵对策s1，s2；A,其中1，2，3，4，1，2，3 -6 1 -8 3 2 4 9 -1 -10 -3 0 6 从可看出，局中人I的最大赢得是9，要想得到这个赢得，他就得选择纯策略3。由于，假定局中人II也是理智的，他考虑到了局中人I打算出3的心理于是侵准备以3对付之。使局中人不但得不到9，反而失掉10，局中人I当然也会猜到局中人II的这一心理，故想出4来对付，使局中人II得不到10而失掉6，所以，如果双方都不想冒险，都不存在侥幸心理，而是考虑到对方必然会设法使自己的所得最少这一点，就应该从各自可能出现的最不利的情形中选择一种最为有利的情形作为决策的依据，这就是所谓“理
13、智行为”，也是对策双方实际上都能接受的一种隐妥方法。例3中，局中人I分析出纯策略1，2，3，4可能带来的最少赢得（矩阵A中每行的最小元素）分别为：-8，-10，-3 -8，2，-10，-3=2在这些最少赢得（最不利的情形）中最好的结果（最有利的情形）是赢得为2。因此，局中人I只要以2参加对策，无论局中人II取什么样的纯策略，都能保证局中人I的收入不会少于2，而出其它纯策略，其收入都有可能小于2，甚至输给对方。因此，对局中人II来说，各纯策略1，2，3可能带来的对其最不利的结果（矩阵A中每列中最大元素）分别为：9，6 9，2，6=2在这些最不利的结果中，最好的结果（输得最少）也是2，即局中人II只要选择纯策略2（无论局中人I采取什么纯策略，都能保持自己的支付不会多于2，而采取其它任何策略，都有可能使自己的所失多于2。上面的分析表明，局中人I、II的“理智行为”分别是，选择纯策略2和2，这时局中人I的赢得值和局中人II的所失值的绝对值相等（都是2），局中
