运筹学第08章对策论

1、第八章 对策论(Game Theory)引言 矩阵对策的基本理论 矩阵对策的解法 WinQSB软件应用第一节 引言 对策论（Game Theory）亦称博奕论或竞争论，主要研究对象是具有斗争或竞争性质的现象。一般认为，它是现代数学的一个新分支，也是运筹学中的一个重要学科。凡是具有斗争或竞争性质的行为称为对策行为。 战国时期，在齐国的贵族和大臣中风行赛马，参赛双方把各自的马匹分成上、中、下三等，从每个等级中各选出一匹马进行比赛。当时的齐国国王齐威王也经常参加比赛，他的大臣田忌在与威王的比赛中屡次失败。当时，孙膑还是田忌的家臣，他分析了当时的状况，认为齐国的好马多集中在威王的手中，田忌采用相同等级

2、的马与威王比赛，自然是赢不了威王的；他建议田忌再与威王赛一次，每匹马赌千金。结果，田忌按孙膑的策略，用他的上等马对威王的中等马、用中等马对威王的下等马、用下等马对威王的上等马，获得了两胜一负，最终赢得了千金。 对策论的发展历史并不长，但由于它所研究的现象与政治、经济、科学、文化教育、军事等活动乃至人们的日常生活有着密切的联系，而分析问题和解决问题的方法又有鲜明的特色，所以，受到了人们日益广泛的重视。一、对策行为的基本要素 对策行为有三个基本要素，即局中人、策略和赢得函数。分析对策行为首先必须清楚这三个基本要素。1局中人（Player） 在一局对策中，有权决定自己行动方案的参加者称为局中人，通常

3、用 P 表示局中人的集合。 局中人：利益得失者,不是公证人、马、谋士等，可以是团体、国家等； 聪明的，有理智的； 把那些利益完全一致的参加者们看作一个局中人； 两人,多人,结盟,不结盟2策略（Strategy） 在一局对策中，可供局中人选择的完整的行动方案称为策略。所谓完整的行动方案是指一局对策中自始至终的全局规划，而不是其中某一步或某几步的安排。 把局中人的策略全体，称做这个局中人的策略集合； 各局中人都有六个策略：(上、中、下)；(上、下、中)；(中、上、下)；(中、下、上)，(下、中、上)，(下、上、中)。这个策略全体就是局中人的策略集合。 例如，在齐王与田忌赛马的例子中，如果一开始就要

4、把各人的三匹马排好次序，然后依次出赛。 如果全体局中人的“得失”相加总是等于零时，这个对策就称为零和对策。否则称为“非零和对策”。 从每个局中人的策略集中各取一个策略，组成的策略组，称作“局势”。“得失”是“局势”的函数。 3赢得函数（Score） 每个局中人在一局对策中的得失，通常不仅与其自身采取的策略有关，而且还与其他局中人所采取的策略有关。也就是说，每个局中人的得失是全体局中人所采取的一组策略的函数，这一函数称为局中人的赢得函数。 二、对策的分类 按对策方式合作对策非合作对策完全理性有限理性按对策人数多人对策二人对策二人零和对策二人非零和对策按对策状态静态对策动态对策完全信息动态对策不完

5、全信息动态对策完全信息静态对策不完全信息静态对策第二节 矩阵对策的基本理论 有限二人零和对策，即参加对策的局中人只有两个，而每个局中人都有有限个可供选择的策略。而且在任一局势中，两个局中人的得失之和总等于零（一个局中人的所得即为另一个局中人的所失）。局中人的利益是冲突的，也称为对抗对策。一、矩阵对策的数学模型用甲、乙表示两个局中人，假设甲有 m 个策略，表示为: 乙有 n 个策略，表示为： 当甲选定策略i、乙选定策略j 后，就形成了一个局势(i ,j )，可见这样的局势有 mn 个。对任一局势(i ,j )，甲的赢得值为 aij ，即甲的赢得矩阵:通常将二人有限零和对策的数学模型记为： 为理解

6、二人有限零和对策的数学模型，仍以田忌赛马为例进行说明。 齐威王共有六个策略，分别为：1(上、中、下)、2(上、下、中)、3(中、上、下)、4(中、下、上)、5(下、中、上)、6(下、上、中)。则齐威王的策略集 S1 为： 田忌也有六个策略，分别为：1(上、中、下)、2(上、下、中)、3(中、上、下)、4(中、下、上)、5(下、中、上)、6(下、上、中)。则田忌的策略集 S2 为： 当局中人齐威王、田忌分别采用纯策略i 和j 时，就构成了一个纯局势(i , j )，显然这样的纯局势共有66个。 据齐威王与田忌的赛马规则及马的优劣，可得到齐威王的赢得矩阵为： 【例10-1】甲、乙两名儿童玩猜拳游戏

7、，游戏中双方的策略集均为拳头（代表石头）、手掌（代表布）和两个手指（代表剪刀）。如果双方所选策略相同，算和局，双方均不得分。试建立儿童甲的赢得矩阵。 解：根据题意有下表： 布剪刀石头布剪刀石头 乙 甲01-1-1011-10即儿童甲的赢得矩阵为： 矩阵对策模型给定后，各局中人面临的问题便是如何选取自己最为有利的策略，以谋取最大的赢得或最小的损失。 二、矩阵对策的纯策略 【例10-2】设矩阵对策 ，其中： ， 试求出双方的最优纯策略和对策值。 解：由 A 可以看出，局中人甲的最大赢得是8，要想得到这个赢得，他就得选择纯策略3 。 局中人乙考虑到局中人甲打算选择纯策略 3 的心理，于是他选择 3

8、策略，使局中人甲不单得不到8反而失掉10。 局中人甲当然会猜到局中人乙的这一心理，故想出选择纯策略 4 来对付 ，使局中人乙不单得不到10反而失掉6。 双方都不应冒险，都不存在侥幸心理，而是考虑到对方必然想办法使自己的所得最少这一点，就应该采取理智行为。638各列最大值max-3-10-6各行最小值(min)3 对本例而言，赢得矩阵A的各行最小元素的最大值与各列最大元素的最小值相等，即： “理智行为”就是从最坏处着想，去争取尽可能好的结果。 由于假设两个局中人都是理智的，所以每个局中人都必须考虑到对方会设法使自己的赢得最少，谁都不能存在侥幸心理。 若用数学语言，可表示为： 甲的赢得值： 乙的支

9、付值： 定义1：设G=S1,S2;A为矩阵对策，其中双方的策略集和赢得矩阵分别为 、 、 。若有等式： 成立，则称 为对策G的值，局势（ ）为对策G的解或平衡局势。 和 分别称为局中人甲、乙的最优策略。 定理1：矩阵对策G=S1,S2;A在纯策略意义上有解的充分必要条件是存在着局势( )使得对于一切 i =1,2,m 和j=1,2,n均有下式成立。-3-10-63638-3-10-63638 对于本例而言，可表示为： 定义2：设 f(x,y)为定义在 xA及 yB上的实函数，若存在x*A、y*B，使得一切 xA和 yB满足： 则称(x*,y*)为函数 f(x,y) 的一个鞍点。【例10-3】矩

10、阵对策G=S1,S2;A，其中赢得矩阵 957各列最大值-155各行最小值-45解：于是： 其中 i* =1,3；j* =2,4。 由此例可知，矩阵对策的解可以是不唯一的。当矩阵对策具有不唯一解时，各解之间的关系具有这样的性质： 故(1,2)、(1,4)、(3,2)和(3,4 )四个局势均为对策的解，且：可交换性：若是G的解，则也是G的解。 三、矩阵对策的混合策略 由前面的讨论可知，对于矩阵对策G=S1,S2;A来说，局中人甲有把握的最少赢得是： 局中人乙有把握的最多损失是： 当 v1=v2时，矩阵对策G=S1,S2;A存在纯策略意义上的解。 然而，并非总有 v1=v2，实际问题出现更多的情形

11、是 v10。令 ，则不等式组： 根据定理8，有 于是不等式组（10.28）等价于下式所示的线性规划问题： (P) 同理，令 ，则不等式组： 根据定理8，有 于是不等式组（10.30）等价于下式所示的线性规划问题： (D) 于是： 【例10-10】利用线性规划求解矩阵对策，其中解：构造两个互为对偶的线性规划问题： 1001641u300103161u20000111j0014521u10u3u2u1y3y2y1bYBCB000111cj1-2/30-116/301/3u3101/601/21/611/6y100-1/601/25/60j0-1/31314/302/3u103/16-1/80-3/

12、16101/16y21-1/323/16017/32015/32y11-5/32-1/16021/3200j-7/81/4131/8003/8u109/62-7/623/620105/62y1111/12419/124-17/12400113/124y21-1/124-13/124-21/124000j-7/312/318/311003/31y31利用单纯形法求解第二个线性规划问题，迭代过程见表10-3。则：故： 解：该矩阵不存在鞍点，也不能用超优原则将其缩减，故拟用线性规则方法求解。 从矩阵可见，对局中人甲而言，其最小最大值为-1，因而其对策值有可能是非正的，因此取常数 k2，则赢得矩阵变为： 对局中人甲而言，求解 使：【例】求解如下矩阵对策： 对局中人乙而言，求解 使：用单纯形法求解局中人乙的最优策略，得最终单纯形表如下： yBby1y2y3u1u2u3y16/2510019/25-3/50-2/25y33/25001-3/2511/50-1/25y24/25010-2/25-1/257/25j000-6/25-3/25-4/25原矩阵对策的对策值为： 第五节 WinQSB软件应用 WinQSB软件需要调用子程序：De