管理运筹学-对策论

1、对策论,由“齐王赛马”引入,2,1.对策论的基本概念,三个基本要素； 1.局中人：参与对抗的各方； 2.策略集：局中人选择对付其它局中人的行动方案称为策略。 某局中人的所有可能策略全体称为策略集； 3.局势对策的益损值：各局中人各自使用一个对策就形成一个局势，一个局势决定了个局众人 的对策结果（量化）称为该局势对策的益损值）,3,“齐王赛马”齐王在各局势中的益损值表（单位：千金）,4,齐王的策略集: S1=1, 2, 3, 4, 5, 6 田忌的策略集： S2=1, 2, 3, 4, 5, 6 下列矩阵称齐王的赢得矩阵： 3 1 1 1 -1 1 1 3 1 1 1 -1 A= 1 -1 3

2、1 1 1 -1 1 1 3 1 1 1 1 1 -1 3 1 1 1 -1 1 1 3,5,1.基本概念（续）,二人有限零和对策：（又称矩阵策略） 局中人为2； 每局中人的策略集中策略权目有限； 每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。,6,1.基本概念（续）,记矩阵对策为: G = S1, S2, A 甲的策略集 甲的赢得矩阵 乙的策略集 “齐王赛马”即是一个矩阵策略.,7,2.矩阵对策的最优纯策略,在甲方赢得矩阵中： A=aijm*n i行代表甲方策略 i=1,2m j行代表乙方策略 j=1,2n aij代表甲方取策略i,乙方取策略j,这一局势下甲方的

3、益损值，此时乙方的益损值为-aij（零和性质）。 在讨论各方采用的策略是必须注意一个前提就是对方是理智的。这就是要从最有把握取得的益损值情况考虑。,8,2.矩阵对策的最优纯策略(续),例：有交易双方公司甲和乙，甲有三个策略1，2，3；乙有四个策略1，2，3，4，根据获利情况建立甲方的益损值 赢得矩阵。 -3 0 -2 0 A= 2 3 0 1 -2 -4 -1 3 问：甲公司应采取什么策略比较适合？,9,甲： 采取1至少得益3(损失 3） 2 0 3 -4(损失 4） 乙： 采取1甲最多得益2 （乙最少得益-2） 2 3（乙得益-3） 3 0（乙得益 0） 4 3（乙得益-3）,取大则取2 m

4、ax min aij= 0 i j,取小则取3 min max aij= 0 j i,10,甲采取策略2 不管乙采取如何策略，都至少得益。 乙采取策略3 不管甲采取如何策略， 都至少可以得益。（最多损失0） 分别称甲，乙公司的最优策略，由唯一性又称最优纯策略。 存在前提： max min aij = min max aij = v i j j i 又称（ 2 ，3 ）为对策G=s1,s2,A 的鞍点。值V为G的值。,11,3.矩阵对策的混合策略,设矩阵对策 G =S1,S2,A 当 max min aij min max aij i j j i 时，不存在最优纯策略 求解混合策略。,12,3.

5、矩阵对策的混合策略,例：设一个赢得矩阵如下: min 5 9 5 A = max 6 策略2 8 6 6 i max 8 9 min 8 策略1 j,13,矛盾：甲取2 ，乙取时1，甲实际赢得8比预期多2（乙就少2）这对乙讲是不满意的，考虑这一点，乙采取策略2，若甲分析到这一点，取策略1，则赢得更多为9 此时，甲，乙芳没有一个双方均可接受的平衡局势。 一个思路：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）。-即混合策略,14,求解方法：线性规划法 （其他方法：图解法，迭代法，线性方程法等略） 例： 5 9 设在最坏的情况下， A= 甲赢得的平

6、均值为V. 8 6 （未知） STEP 1 1)设甲使用策略1的概率为X1 X1+X2=1 设甲使用策略2的概率为X2 X1,X20,15,2)无论乙取何策略，甲的平均赢得应不少于V: 对乙取1：5X1+ 8X2V 对乙取2：9X1+ 6X2V 注意 V0,因为A各元素为正。 STEP 2 作变换： X1= X1/V ; X2= X2/V 得到上述关系式变为： X1+ X2=1/V (V愈大愈好）待定 5X1+ 8X21 9X1+ 6X21 X1, X20,16,建立线性模型： min X1+X2 s.t. 5X1+8X21 X1= 1/21 9X1+6X21 X2= 2/21 X1, X20

7、 1/V= X1+X2=1/7 所以：V=7 返回原问题： X1= X1V= 1/3 X2= X2V= 2/3 于是甲的最优混合策略为： 以1/3的概率选1；以2/3的概率选2 最优值V=7.,17,同样可求乙的最优混合策略： 设乙使用策略1的概率为Y1 Y1+Y2=1 设乙使用策略2的概率为Y2 Y1,Y20 设在最坏的情况下，甲赢得的平均值为V. 这也是乙损失的平均值，越小越好 作变换： Y1= Y1/V ; Y2= Y2/V 建立线性模型： max Y1+Y2 s.t. 5Y1+9Y21 Y1= 1/14 8Y1+6Y21 Y2= 1/14 Y1, Y20 1/V= Y1+Y2=1/7

8、所以：V=7,18,返回原问题： Y1= Y1V= 1/2 Y2= Y2V= 1/2 于是乙的最优混合策略为： 以1/2的概率选1；以1/2的概率选2 最优值V=7. 当赢得矩阵中有非正元素时，V0的条件不一定成立，可以作下列变换： 选一正数k，令矩阵中每一元素加上k得到新的正矩阵A，其对应的矩阵对策 G= S1,S2,A与 G = S1,S2,A 解相同，但VG = VG - k,19,再讨论“齐王赛马”,“齐王赛马”的赢得矩阵A有 max min aij1 min max aij3 i j j i 故需求混合策略，由于A中有非正元素，可选k2，令矩阵中每一元素加上k得到新的正矩阵A： 5

9、3 3 3 1 3 3 5 3 3 3 1 A = 3 1 5 3 3 3 1 3 3 5 3 3 3 3 3 1 5 3 3 3 1 3 3 5,20,再讨论“齐王赛马”(续),求甲方(齐王)最优策略的线性规划模型： min X1+X2 +X3 +X4 +X5 +X6 s.t. 5X1+3X2 +3X3 + X4 +3X5 +3X6 1 3X1+5X2 + X3 +3X4 +3X5 +3X6 1 3X1+3X2 +5X3 +3X4 +3X5 + X6 1 3X1+3X2 +3X3 +5X4 + X5 +3X6 1 X1+3X2 +3X3 +3X4 +5X5 +3X6 1 3X1+ X2 +3

10、X3 +3X4 +3X5 +5X6 1 X1，X2，X3，X4，X5，X6 0 可得两组解：(0,1/9,1/9,0,0,1/9)T, (1/18,1/18,1/18,1/18,1/18,1/18)T ,V=3 于是，X(0,1/3,1/3,0,0,1/3)T, X(1/6,1/6,1/6,1/6,1/6,1/6)T V = V-2 = 1 即齐王的最优混合策略值是赢1千金,21,再讨论“齐王赛马”(续),求乙方(田忌)最优策略的线性规划模型： min Y1+Y2 +Y3 +Y4 +Y5 +Y6 s.t. 5Y1+3Y2 +3Y3 +3Y4 + Y5 +3Y6 1 3Y1+5Y2 +3Y3 +

11、3Y4 +3Y5 + Y6 1 3Y1+ Y2 +5Y3 +3Y4 +3Y5 +3Y6 1 Y1+3Y2 +3Y3 +5Y4 +3Y5 +3Y6 1 3Y1+3Y2 +3Y3 + Y4 +5Y5 +3Y6 1 3Y1+3Y2 + Y3 +3Y4 +3Y5 +5Y6 1 Y1，Y2，Y3，Y4，Y5，Y6 0 可得两组解：(1/9,0,0,1/9,1/9,0)T, (1/18,1/18,1/18,1/18,1/18,1/18)T ,V=3 于是，Y(1/3,0,0,1/3,1/3,0)T, Y(1/6,1/6,1/6,1/6,1/6,1/6)T V = V-2 = 1 即田忌的最优混合策略值是输

12、1千金,22,优超原则： 假设矩阵对策 G = S1,S2,A 甲方赢得矩阵 A=aijmn - 若存在两行，s 行的各元素均优于 t 行的元素，即 asjatj j=1,2n 称甲方策略s优超于t - 若存在两列，s 列的各元素均优于 t 列的元素，即 ais ait i=1,2,m 称乙方策略 s优超于t,3.矩阵对策的混合策略(续),23,- 优超原则：当局中人甲方的策略t被其它策略所优超时，可在其赢得矩阵A中划去第t行（同理，当局中人乙方的策略t被其它策略所优超时，可在矩阵A中划去第t列）。 如此得到阶数较小的赢得矩阵A，其对应的矩阵对策 G= S1,S2,A与 G = S1,S2,A

13、 等价，即解相同。,3.矩阵对策的混合策略(续),24,例 设甲方的益损值 赢得矩阵。 3 2 0 3 0 被第3、4行所优超 5 0 2 5 9 被第3行所优超 A= 7 3 9 5 9 4 6 8 7 5.5 6 0 8 8 3 得到 7 3 9 5 9 被第1列所优超 A1= 4 6 8 7 5.5 被第2列所优超 6 0 8 8 3,3.矩阵对策的混合策略(续),25,续例 得到 7 3 9 A2= 4 6 5.5 6 0 3 被第1行所优超 得到 7 3 9 被第1列所优超 A3= 4 6 5.5 7 3 最终得到 A4= 4 6,3.矩阵对策的混合策略(续),26,对A4计算，用线

14、性规划方法得到： （注意：余下的策略为3，4，1，2） 甲： X* = (0，0，1/15，2/15，0)T V=5 X*= (0，0，1/3 ，2/3 ，0)T 乙： Y* = (1/10，1/10，0，0，0)T V=5 Y*= (1/2 ，1/2 ，0，0，0)T 注： 利用有超原则化简赢得矩阵时，有可能将原对策问题的解也划去一些（多解情况）； 线性规划求解时有可能是多解问题。 习题：P343-1，3，4,3.矩阵对策的混合策略(续),决策分析,27,附1：SWOT分析,28,附2：如何安排自己的日程生活呢？,29,附3：谁也不能阻碍你成为一个富人-罗博特.清崎,1. 4 种人对资产(a

15、sset)与负债(liability)的认可是不一样的,2. Viewpoints on education 1) academic 2) professional 3) financial,3. Some suggestions 1) vocabulary related to money 2) team 3) mistakes,30,附4：人的分类与企业剩余的关系*,31,例1：例一：囚徒困境(prisoners dilemma),在这个例子中，纳什均衡就是（坦白，坦白）。囚徒困境反映了一个很深刻的问题，这就是个人理性与集体理性的矛盾，如果两个人都抵赖，各判刑1年，显然比都坦白判刑8年好。

16、但这个帕累托改进办不到，因为它不满足个人理性要求，（抵赖，抵赖）不是纳什均衡。该例子在经济学上的应用：如果两个企业联合起来形成卡特尔，选择垄断利润最大化的产量，每个企业都可得到更多的利润。但卡特尔协定不是一个纳什均衡，因为给定对方遵守协议的情况下，每个企业都想增加生产，结果是，每个企业都只能得到纳什均衡产量的利润，它严格小于卡特尔产量下的利润。这个例子说明，在有些情况下，个人理性与集体理性的冲突对逐个社会来说，也许是件好事，尽管它对该集体的成员来说是件坏事。当然这里的前提条件是集体成员的数量严格小于全体社会成员的数量。,32,公共产品的估计也是一个囚徒困境问题。如果大家都出钱兴办公用事业，所有

17、人的福利都会增加，问题是，如果我出钱你不出钱，我得不偿失，而你出钱我不出钱，我就可以占你的便宜。所以每个人的最优选择都是“不出钱”，这种纳什均衡使得所有人的福利都得不到提高。 经济改革本身也可能是这样。在许多改革中，改革者要付出成本（包括风险），而改革的成果大家享受，结果是，尽管人人都认为改革好，却没有人真正去改革，大家只好在都不满意的体制下继续生活下去。 从囚徒困境中，我们可以引出一个很重要的结论：一种制度安排，要发生效力，必须是一种纳什均衡。否则，这种制度安排便不能成立。,33,例2：智猪博弈（boxer pigs）,纳什均衡是（大猪按，小猪等）。这反映了一个不合理的现象：多劳者不多得。

18、在股票市场，大户是大猪，小户是小猪。 一个村子里有两户人家，一个是富裕户，一个是穷户，要修一条路。富户是大猪，穷户是小猪。大猪修路，小猪搭便车。 改革中，一部分人的好处比另一部分人的好处多，好处多的人是大猪，后者是小猪。大猪推动改革的进程。,34,例3：性别战（battle of sexes）,有两个纳什均衡（足球，足球）、（芭蕾，芭蕾）。究竟实际中发生哪一个，我们不知道，但我们知道这里存在一个先动优势。,例4：斗鸡博弈（chicken game）,也有两个纳什均衡（进，退）和（退，进）。究竟谁进谁退呢？,35,总结一下，公共产品的供给可能是囚徒博弈，也可能是智猪博弈，还可能是斗鸡博弈，这要依据产品而定。 例5：市场进入阻挠（entry deterrence）,在这个博弈中，假定进入之前垄断利润为300，进入之后寡头利润合为100（各得50），进入成本为10。 有两个纳什均衡：（进入，默许）、（不进入，斗争）。 例6：关于制贩联盟的定价问题,36,关于纳什均衡含义的解释 纳什均衡的含义：假设有N个人参与博弈，给定其他人参与博弈的条件，每个人选择自己的最优战略，所有参与人选择的战略一起构成一个战略组合。纳什均衡指的是这样一种战略组合，这种战略组合是由所有参与人的最优战略组成，也就是说，给定