第五章博弈论的思想方法及其应用

《第五章博弈论的思想方法及其应用》由会员分享，可在线阅读，更多相关《第五章博弈论的思想方法及其应用（158页珍藏版）》请在金锄头文库上搜索。

1、 对策论（博弈论） Operational Research要想在现代社会做一个有文化的人 ，你必须对博弈论有一个大致了解 .诺贝尔经济学奖获得者Paul Samuelsonv博弈论（The Games Theory)是运筹学学科的一个 重要分支。具有竞争或对抗性质的行为称为博弈行 为，在这类行为中，参与斗争或竞争的各方各自具 有不同的目标和利益，为了达到各自的目的，各方 必须考虑对手的各种可能的行动方案，并力图选取 对自己最为有利或最合理的方案。v博弈论就是研究博弈行为中，斗争各方是否存在最 合理的行动方案，以及如何找到这个合理方案的理 论和方法。10.1 博弈论的基本概念 10.2 矩阵博

2、弈的纯策略 10.3 矩阵博弈的混合策略 10.4 矩阵博弈求解方法 10.5 纳什均衡 10.6 合作博弈与效益分配 10.7 动态博弈与承诺行动 10.8 应用举例 附录 博弈论与诺贝尔经济学奖10.1 博弈论的基本概念v1944年，数学家冯诺伊曼(J.von-Neumann) 和经济学家摩根施特恩（O.Morgenstern） 写成了博弈论与经济行为一书，这是博 弈论这一分支的经典之作. v该书不仅建立了博弈论的严格的公理化体系 ，而且对大量的经济活动进行了深入的分析 ，奠定了博弈论的基础. 10.1 博弈论的基本概念5.1 博弈论的基本概念10.1 博弈论的基本概念博弈论是矛盾和合作的

3、规范研究，是系统研究决 策主体的行为发生直接相互作用情况下的决策以 及这种决策均衡的理论. 也就是说，当一个决策主 体的选择受到其他决策主体选择的影响，并且它 的决策也影响其他决策主体的决策时的合理选择 问题.博弈论思想的主要特征是各参与人所实施的行为 方案（策略）相互依存，各方在冲突或合作后所 实现的得失结果不仅取决于自己所采用的行为方 案，同时也依赖于其他参与人所采用的行为方案 ，它是各参与人行为方案组合的函数.在现实生活中，经常可以看到一些具有对抗和竞争性的现 象，如体育比赛、军事斗争中双方兵力的对抗，各公司企 业之间的经济谈判以及为争夺市场而进行的竞争等等。在 竞争过程中，各方为了达到

4、自己的目标和利益，必须考虑 对手的各种可能的行动方案，并力图选取对自己最为有利 或最为合理的方案，也就是说要研究采取对抗其他竞争者 的策略。从数学角度来说，博弈论就是研究竞争行为中的 竞争各方是否存在着最合理的行动方案，以及如何找到这 个合理的行动方案的数学理论和方法。10.1 博弈论的基本概念v博弈论认为：人是理性的，即人人都会在约束条 件下最大化自身的利益；人们在交往合作中有冲 突，行为互相影响，而且信息不对称.10.1 博弈论的基本概念10.1 博弈论的基本概念v囚徒困境问题甲和乙两个小偷联手作案，因私入民宅被警方 抓住但未获证据。警方将两人分别置于两间房 间分开审讯，政策是若一人招供但

5、另一人未招 ，则招者立即被释放，未招者判入狱10年；若 二人都招，则两人各判刑8年；若两人都不招，则未获证据但因私入民宅各拘留1年。将这些数 据列出，如下： 10.1 博弈论的基本概念v囚徒困境博弈尽管甲不知道乙是否招供，但他认为自己选“ 招”最好，因而甲会选择“招”，乙也同样会 选择“招”，结果各判8年；但若两人都不招， 结果是每人只被判1年，但在“人是理性的，即 人人都会在约束条件下最大化自身的利益”的 基本假设下，这种结果是不会出现的.10.1 博弈论的基本概念v甲和乙是参与博弈的人，称为“局中人”.表中每 一个小方格内的数字被称为局中人的支付，其中 左边的数字代表甲的支付，右边的是乙的

6、支付.表 中的双变量矩阵称为博弈支付矩阵.局中人所选择 的战略构成的组合（招,招）被称为博弈均衡.这 个组合中前后两个战略分别表示甲和乙所选择的战略.10.1 博弈论的基本概念v如果甲和乙在决策时抛掉谨慎，加入一定的“疯 狂”，不约而同地采取“不招”的策略，其结果 是每人只被判1年.显然，这对甲、乙二人来说， 比他们采取理性策略的结果“好”. 10.1 博弈论的基本概念10.1 博弈论的基本概念v商家价格战 出售同类产品的商家之间本来可以通过共同将 价格维持在高位而获利，但实际上却是相互杀 价，结果都赚不到钱. 当一些商家共谋将价格 抬高，消费者实际上不用着急，因为商家联合 维持高价的垄断行为

7、一般不会持久，可以等待垄断的自身崩溃，价格就会掉下来.10.1 博弈论的基本概念博弈论有三个基本假设：v参与人是理性的；v他们有这些理性的共同知识；v他们知道博弈规则. 任何一个博弈问题都包含如下三个要素：局中人、 策略和支付函数.10.1 博弈论的基本概念（1）局中人(Players)v在一场具有竞争性的决策中，有制定对付对手的 行动与方案权，并有权作出决策的参加者称为局 中人，如囚徒困境问题中的甲和乙.v局中人可理解为那些利益完全一致的集体或集团 ，局中人是有理智、聪明的，并有行动决定权的.v我们称只有两个局中人的博弈现象为两人博弈;v而多于两个局中人的博弈称为多人博弈.在多人博弈中，局中

8、人之间允许合作的称为结盟博弈，不允许合作的称为不结盟博弈. 10.1 博弈论的基本概念（2）策略(Strategies)v在一局博弈中，每个局中人都有一套可供选择的 指导自始至终如何行动的方案，以求争取较好的 结果，我们称此行动方案为这个局中人的一个策 略，而把这个局中人的策略全体称为这个局中人 的策略集.v在一局博弈中，各个局中人选定的策略构成的一 个策略组，称之为一个局势.v如果在一局博弈中，各个局中人只有有限的策略 ，我们称之为有限博弈；否则称为无限博弈.10.1 博弈论的基本概念（3）支付函数(Payoff Function)v在一局博弈结束后，对每个局中人来说，其结果不 外乎是赢（得

9、）或输（失）.显然，这种输赢局势 是随局中人所选取的策略组的变化而变化的，局中 人选定一个策略组，必然对应着一个博弈结果.因 此，我们可以用一个函数来表示输赢（或得失）.将这个函数称之为支付函数.对应所有策略组的支 付函数的各个取值可以用一个矩阵来表示，称之为 支付矩阵.10.1 博弈论的基本概念v对于一个博弈问题，如果在每一个局势中，全体局中人的得失相加都是零，则称此博弈为零和博弈，否则称为非零和博弈.10.1 博弈论的基本概念v博弈中有关局中人的策略集、支付函数等构成 了博弈的信息.按照局中人对信息掌握的情况，可分为完全信息博弈和不完全信息博弈。按照 局中人采取行动的次序，当局中人同时采取

10、行 动或在互相保密情况下采取行动，称这种情况 为静态博弈.如果局中人采取行动有先后，后采取行动的人可以观察到前面人采取的行动，则 属于动态博弈。按照局中人是否结盟情况，还 可以将博弈分为结盟博弈与不结盟博弈.10.1 博弈论的基本概念10.1 博弈论的基本概念v二人有限零和博弈在众多博弈模型中，占有重要地位的是二人有限零和博弈，即在博弈只有两个局中人，各自的策略集只含有限个策略，每局中两个局中人的得失总和为零（即一个局中人的赢得恰为另一个局中人所输掉的值），这类博弈又称为矩阵博弈.10.1 博弈论的基本概念10.1 博弈论的基本概念v【例10.1】田忌赛马v战国时期（自公元前475周元王元年起

11、，至公元前 221年秦始皇吞并六国建立中国第一个统一的多民 族的中央集权的封建国家为止，是我国历史上的战 国时期）齐王与田忌赛马.双方约定：每人从自己 的上、中、下三个等级的马中，各选出一匹马参赛 ，每一场比赛各出一匹马，一共比三场，每匹马只 能参加一场比赛，每场比赛后输者要付给赢者一千 金.就同级的马而言，齐王的马都比田忌的马强.v解 在本问题中局中人为齐王和田忌。以马出场的顺序而言，齐王有六种博弈策略.例如先用上等马，再用中等马，最后下等马，以（上 、中、下）表示之.同样，田忌也有六种博弈策略 ，即两位局中人的策略集都含有六个策略.可以用表10.2表示齐王的支付.10.1 博弈论的基本概念

12、10.1 博弈论的基本概念v表10.210.1 博弈论的基本概念v将表10.2中的数字表成矩阵v称为齐王的赢得矩阵 .v 这个博弈问题是一个二人有限零和博弈问题. 形势显然对田忌不利.但是田忌的谋士孙膑建议 ，每场比赛前要齐王报他要出哪匹马.孙膑让田 忌的下等马对齐王的上等马，用中等马对齐王 的下等马，用上等马对齐王的中等马.结果反而 赢了齐王一千金，这是一个典型的博弈问题.它 表明在博弈问题中，局中人必须运用智慧，保 守自己的秘密并设法获得对方的情报，采取恰 当的策略方能取得较好的结果.10.1 博弈论的基本概念v本节知识要点1.博弈论研究的问题2.博弈论思想的主要特征3.博弈论的基本概念4

13、.博弈论有三个基本假设5.博弈论的分类 10.1 博弈论的基本概念10.2 矩阵博弈的纯策 略v局中人从 中选一个策略 ，同时局中人从 中选一个策略 ，这样就构成一个局势对应于策略集 和 ，一共有 个局势.在 局势 下局中人的赢得记为 ，则局中 人在m个策略 下的赢得构成一个矩 阵.10.2 矩阵博弈的纯策略v用，分别表示两个局中人，设局中人有m个 策略；局中人有n个策略；其策略集分别表示为 ，10.2 矩阵博弈的纯策略称为局中人的赢得矩阵. v由于对策是零和的， 表示在同一局势 下 局中人的赢得，故局中人的赢得矩阵为 记这 个博弈为 v矩阵博弈的数学模型为： ，其 中 10.2 矩阵博弈的纯

14、策略10.2 矩阵博弈的纯策略v在矩阵博弈中要讨论的问题是：各局中人应该如何选择自己的策略，使自己在博弈中获得最好的结果.下面用一个例子说明.10.2 矩阵博弈的纯策略v【例10.2】设矩阵博 弈v局中人，应如何选择自己的策略，以保证自己 在博弈中取得有利的地位？v解: 对局中人而言，他的最大的收益是8， 他理所当然地会选择策略 ，同时，他希望 局中人选择策略 。但是局中人发现， 如果局中人采取策略 ，他不会愚蠢地选 择 以致失去8。反之，他会选择 ，这样 他仅失去1。然而，当局中人选择 时，局 中人就会选择 ，这样做比选择 有利， 可使收益由1增加到3。这时，局中人、 都不愿再改变选择，因为

15、如果局中人改变 选择，失去的不是3，而是5或4，如果局中 人改变选择，其得到的不是3，而是1或2 。显然，这种状态是一种平衡状态。10.2 矩阵博弈的纯策略v对应于策略 ，局中人的赢得由5降到3，然后 又由3升到4；对应于策略 ，局中人的支付由1上升到3，然后又由3下降到2.中间这个数3，从第二行看来它形成一个凹槽，从第二列看它形成一个凸脊，正像一个马鞍形，点3处于马鞍的中心.10.2 矩阵博弈的纯策略v上面解题的数学方法为：对局中人来讲， 先对矩阵A的每行元素取最小值：v再从这些最小值中取最大值： 。 也就是说，局中人采取悲观主义原则，从 最坏的情况中，取得的最好结果是3，这时 ，他应采取的策略是 ，不论局中人采取 什么策略，都可以保证赢得不会少于3.10.2 矩阵博弈的纯策略10.2 矩阵博弈的纯策略v注意到矩阵A中的元素 反号后是局中人 的赢得，故局中人采取悲观主义原则时， 应先对矩阵A的每一列元素中取出最大值：v再从这些最大值中取最小值： 。因此，局中人应采取策略 ，则不论局 中人采取什么策略，最大损失不会大于3 。10.2 矩阵博弈的纯策略v因此，局中人、只有分别采取 、 时 才是他们的最优策略。为了与后面的概念相 区别，我们称 、 分别为局中人、的 最优纯策略 而局势