运筹学课件第13章 对策论.ppt

1、第十三章博弈论，关文忠，重庆三峡大学，教学目标与要求，教学目标 1。理解以下基本概念：矩阵游戏，矩阵游戏的三个要素，最优纯策略和最优混合策略，鞍点和游戏值2。算法要求：(1)将利用“超优原则”和“最大最小”原则寻找矩阵游戏的最优纯策略(本章主要内容)，13.1博弈论的基本概念13.1.1博弈模型的基本要素13.1.2博弈问题的分类13.2矩阵游戏的纯策略13.2.1优势和优势原则13.2.2最大和最小原则13.3矩阵游戏的混合策略13.3.1混合策略的概念13.3.2图解法13.34.1纯策略纳什均衡的评分方法13.4.2混合策略纳什均衡的线性规划方法13.4应用实例案例13-1市场竞争策略案

2、例13-2竞争项目确定本章概要，13.1.1博弈模型的基本要素，1参与者是指参与竞争的各方，每一方都必须具有独立的决策能力和承担风险的能力。(例如，王琦田吉：)2在对策问题中，局中玩家为应对其他玩家的行为而采取的方案和手段被称为局中玩家的策略。3.当人们采取不同的策略和对策时，各方总是有得有失，统称为“回报”或“收获”。，13.1.2游戏问题的分类，13.1.2游戏问题的分类，13.2矩阵游戏的纯策略。为了找到博弈模型的解，我们首先需要对双方的博弈条件做出如下假设。(1)对策双方的行为都是理性的，在策略的选择上没有运气。(2)玩家选择策略的目标是获得最多或损失最少。(3)玩家同时选择自己的行动

3、策略，他们不知道对方选择哪种策略。(4)对策中的相关规定和要求为局内人员所知。13.2.1超优原则，示例13.2，第3行优于第2行，第1行优于第5行，第1列优于第5列，第4列优于第2列，第1行优于第2行和第3行，示例13.3A和B都有三种广告策略。企业A的市场份额增长百分比如下表A所示，13.2.2最大和最小的原则，例13.4，13.3.1混合策略的概念，例13.5猜硬币游戏：A和B玩一个猜硬币游戏，A手里拿着一枚硬币，把它盖在桌子上，这样孩子B就能猜出它是面朝上还是面朝上。如果你猜对了，给B 1元钱，猜错了，给A 1元钱。猜硬币游戏是一个矩阵游戏。儿童甲的策略是积极的(1)和消极的(2)，而

4、儿童乙的策略是积极的(1)和消极的(2)。，13.3.1混合策略的概念，让A从前面出来的概率为X(1)，从后面出来的概率为1-X(2)；猜测正面(1)的概率y和背面(2)的概率1-y。那么B的两个策略的期望值分别是33，360。当x0.5时，理性的孩子B会选择猜测正；(3)当x=0.5时，不管孩子B采取什么策略，平均赢率都为零。B的策略，和A的策略一样，最好的混合策略，13.3.1混合策略的概念，因为A和B都是理性的，所以，混合扩张：有矩阵游戏，混合扩张，和13.3.1混合策略的概念。当甲采用混合策略X，乙采用混合策略Y时，(X，Y)称为一。13.3.2图解法和求解矩阵对策的图解法一般适用于以

5、或赢得矩阵的对策问题，但不适用于金额较大的对策问题。下面的例子说明了这种方法。如果A的混合策略是x，(1-x)，x0，1，那么当B分别使用1，2和3时，A赢3360。步骤： (1)画出X数轴，标记X值范围0，1 (2)x取0和1，确定三条直线的端点，画出三条直线(3)对应的策略是最佳游戏值为V*=49/11，例13.7求解矩阵游戏，其中，13.3.2图解法，从图中还可以看出，玩家B的最佳混合策略是23的组合，所以1的概率为0。假设2和3的概率是y(1-y)。通过效率矩阵333。因此，取最大损失(粗线)，B将在最大损失中找出最小的，即B的最优混合策略为：y分别为0和1，图如下：13.3.3线性规

6、划法，B从利己主义出发，采用策略组合y1，yn，使其期望损失最小(即A赢得最小)。a将使用特定的策略组合X1。使最小获胜概率组合尽可能大。因此，对于：13.3.3线性规划方法，B将使用某个策略组合y1，yn，使最大损失概率组合尽可能小。因此，有：个。同样，当A采用策略组合x1、xm时，它也是自利的，会使其期望赢得最多(即B的两人零和博弈可以表示为一对对偶规划：例13.7，求解一对对偶模型，得到最优混合情形：13.4纳什均衡，13.4纳什均衡，表示为获胜矩阵3360。如果在某些情况下没有参与者可以单独行动来增加收入，那么这种策略组合。纳什均衡，也称为非合作均衡，是由诺贝尔经济学奖得主、普林斯顿大

7、学的约翰纳西提出的。纳什均衡描述了一种非合作博弈均衡。现实中，不合作的情况比合作的情况更常见。因此，“纳什均衡”是冯诺伊曼和摩根斯坦合作博弈理论的重大发展，甚至是一场革命。纳什均衡也分为纯策略和混合策略。纯策略可以采用“交叉法”；混合策略可以采用线性规划方法。仍然以囚徒困境为例，说明了在纯策略下如何得到纳什均衡。(1)当李四选择坦白时，张三也选择坦白并入狱5年，否则将入狱10年(一)；(2)当李四选择否认时，张三也选择了坦白并坐3个月牢，否则他将坐1年牢(乙)；(3)当张三选择坦白时，李四也选择坦白，坐5年牢，否则坐10年牢(丙)；(4)当张三选择了抵赖，李四也选择了坦白并入狱3个月，否则他将

8、入狱1年(丁)。可以看出，无论一方采取什么策略，对方的最佳策略都是坦白，所以坦白是平衡点。任何偏离这个平衡点的一方都会遭受更多的损失。13.4.1纯策略纳什均衡的打分法，13.4.2混合策略纳什均衡的LP法，因为纳什均衡所解决的问题不是两人零和博弈，博弈双方的获胜矩阵不是同一个矩阵，而且其LP模型也不是一对对偶问题。假设甲、乙双方的获胜矩阵分别为甲、乙，混合策略概率分别为：对于收入等获胜价值，最大利润的maxV(即min1/V)模型如下。对于成本等损失值，具有最小损失的米女(即最大1/V)模型如下。示例13.8获得下表的纳什均衡(收入值)。求解B的收入矩阵，A的第3行和第4行的收入值不大于第1

9、行，B的第3行和第4行的收入值不大于第1列。删除收入矩阵的简化和使用概率如下：A、B收入矩阵的4个元素，建立A、B的线性规划模型，求解如下：案例13-1市场竞争策略，案例13-2竞争项目的确定，求解这是在A的收入矩阵中，第二行的收入值不小于第一行和第三行的收入值，所以是一个纯粹的战略问题，即李参加仰泳比赛。由于A的理性，他会让李参加仰泳比赛，而当B对付A的最佳策略时，王在三个项目的收入分别是15、13和15。由此可见，王参加仰泳和蛙泳的费用是一样的，概率各为0.5。决策建议A队李参加仰泳比赛；乙队赢得了仰泳或蛙泳比赛。甲队得了12分，乙队得了15分。本章总结了博弈论是一种研究竞争现象并为参与者提供对策的数学理论。无论什么样的对策，一个对策现象的共同特征是它有三个基本要素：游戏中的玩家、策略设置和损益值。本章主要讨论矩阵博弈，也称为两人有限零和博弈，是指在任何一对策略组合下，两个玩家和每个玩家的策略数量是有限的，并且两个玩家的损益值之和总是零的博弈。一般来说，矩阵对策表示为G=S1，S2，A。在求解矩阵对策时，我们可以采取以下步骤：首先，我们用严格的劣策略重复淘汰法简化获胜矩阵。判断游戏是否有鞍点，如果有，可以用“最大-最小”原则来解决。如果没有鞍点，就有一个最优混合策略。如果简化矩阵为m2或2n阶，可用“图解法”