博弈论及其应用绪论(四川大学).ppt

2010-03-04,博弈论及其应用 （汪贤裕）,#,博弈论及其应用,四川大学 工商管理学院 汪贤裕 2010年3月,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,2,博弈论及其应用,第1章 绪 论 第2章 纳什均衡 第3章 纳什均衡的扩展与精炼 第4章 协调与谈判 第5章 合作博弈,2010-03-04,博弈论及其应用 （汪贤裕）,#,博弈论及其应用,第1章 绪论,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,4,第1章 绪论,主要内容 1.1 博弈论概况及本书的结构 1.2 博弈研究的三种基本表示法,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,5,1.1 博弈论概况及本书的结构,1.1.1 什么是博弈论 1.1.2 博弈论的发展与分类 1.1.3 本书的结构,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,6,1.1.1 什么是博弈论, 博弈论的来源 博弈论研究的特点 博弈论的应用领域 博弈论解决的问题 学者对博弈论的定义 博弈论与决策论的区别,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,7,博弈论的来源,博弈论来自英文Game Theory ，与游戏有着密切的关系。它最早是从游戏开始的。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,8,博弈论研究的特点,博弈论研究的特点是：参加游戏的人不仅要考虑自己如何行动，还要考虑对方如何行动。 简而言之 它研究在竞争环境中，如何进行决策,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,9,经济领域：生产管理、价格竞争、营销活动、贸易谈判等 企业管理领域：战略制定、薪酬设计、契约制定、劳资纠纷等 政治领域：谈判策略、斗争策略、选举策略、政策制定等 军事领域：进攻和防御、战略和战术等 社会领域：税收、治安、和谐等,博弈论的应用领域,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,10,博弈论解决的问题,如何在竞争冲突的环境下，用智慧和机智去分析和认识问题，进行对自己行动的决策 。 博弈论给我们提供了分析的工具,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,11,学者对博弈论的定义,海萨尼：博弈论是关于策略相互作用的理论 奥 曼：“相互有影响的决策论” 吉本斯：博弈论是研究多人决策问题的理论 迈尔森：博弈论可以定义为是对理性决策者之间冲突 与合作的数学模型的研究,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,12,博弈论与决策论的区别, 参与人数 基于的信念 行为的方式,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,13,多人决策, 参与人数 博弈论 决策论,博弈论与决策论的区别（续）,单人决策,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,14,博弈论与决策论的区别（续）,“自然”一方的随机行动是外生确定的，决策人一方的行动，是基于对“自然”外生的不确定的信念进行行动决策。,参加博弈的多个决策人的行动都是内生的，任一决策人对其它决策人的行动的不确定来自于内生的信念，从而在不确定性的环境下决定自己策略。,决策论,博弈论, 基于的信念,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,15,博弈论与决策论的区别（续）,“自然”一方的随机行为是被动的，并且不构成对决策人一方有意的威胁，决策人一方的行为是主动的，是在一种无恶意威胁的自然面前来取得自己单方面有利的行动，决策人一方的行为对“自然”一方是无损害的。,决策的任何一方都在斗智斗勇，任何一方的收益不仅要受到自身行为的影响，还要受到对方行为的影响，其决策的环境是“竞争冲突”的。,决策论,博弈论,行为的方式,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,16,1.1.2 博弈论的发展与分类, 发展 分类,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,17,博弈论的发展,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,18,博弈论的分类,非合作博弈 （多人）可选择的行动、出现的结果、作出的决策 完全信息静态博弈 不完全信息静态博弈 完全信息动态博弈 不完全信息动态博弈 合作博弈联盟的组成、参与人的权势及如何分配收益 可转移支付 不可转移支付,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,19,1.2 博弈研究的三种基本表示法,1.2.1 规范式 1.2.2 扩展式 1.2.3 联盟式（特征函数式 ） 1.2.4 三种表示式的关系,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,20,1.2.1 规范式,规范式表示 例1.2.1 囚犯困境（Prisoners Dilemma） 例1.2.2 古诺（Cournot）模型,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,21,什么是规范式表示,若博弈具有以下三个要素且能够能明确的给定，这时博弈称为规范式表示： 局中人集 局中人即博弈的参与人。局中人的全体记为 N 。一般对 ,即有 n个局中人的博弈称为 n 人博弈。 局中人 i 的策略集 局中人 i 的策略集 ，指局中人 i 可能采取的可行的策略集合。一般记为 。若每个局中人 i 都取定一个策略 ，则所有个局中人的策略全体 称为一个策略组合，记为： 局中人 i 的支付函数 对任意一个策略组合，带给局中人 i 的损益称为局中人 i 的支付函数 。根据不同问题研究的背景，支付函数可以是损益函数，也可以是效用函数。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,22,什么是规范式表示（续1）,规范式（normal form）也称策略式（strategic form）表示，并记为 。若局中人的策略允许使用混合策略 ，则混合策略集记为 。（关于混合策略将在第二章介绍）这时，博弈也称为规范式表示，并记为 。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,23,囚犯困境,警察拘捕了两个犯罪嫌疑人进行隔离审讯，检察官认为他们犯有某项罪行，但又缺乏足够的证据指证他们的罪行。如果两个嫌疑犯中至少有一个供认犯罪，就能确定罪名成立。为了获得所需的口供，警察将两人分别关押以防止他们串供，并分别向两个嫌疑人指出两条路：承认犯罪和不承认。如果两人都承认，则两人都将被判刑，每人各判8个月。如果两个人都不承认，由于检察官没有足够的证据，他们将作为犯小案件处理，分别判刑1个月。如果其中一个人承认，而另一个人不承认，则承认罪行者，将得到立功宽大处理，不判刑而释放，而不承认者将受到严惩，判刑10个月。此时，犯罪嫌疑人将如何采用自己的行动呢？,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,24,囚犯困境（续1）,博弈的支付矩阵：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,25,囚犯困境（续2）,该博弈有三个基本要素 局中人集 : =嫌疑犯A,嫌疑犯B 局中人 i 的策略集 : ， 局中人i 的支付函数,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,26,古诺（Cournot）模型（例1.2.2）,现有两个寡头垄断厂商：厂商1和厂商2。他们生产同一种产品，其生产的边际成本分别为 和 。该产品的市场逆需求函数为 ，其中 是该市场出清价格， 和 分别是两个厂商对产品的生产数量。 是一个正常数，即市场对该产品的市场最高价。市场需求情况和各厂商可能的收益对两个厂商都是共同知识。厂商1和厂商2在无协商的情况下，独立作出生产数量的决策。问他们各自作出什么样的决策，以使自己利润最大。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,27,古诺模型（续1）,用规范式表示古诺模型： 支付函数为：,，,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,28,1.2.2 扩展式,例1.2.3 二人取数游戏1 例1.2.4 二人取数游戏2 扩展式表示的内涵,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,29,二人取数游戏1,有一个二人参加取数的游戏，游戏分三步进行。第一步，局中人1在0，1中取一个数记为 r1 ，并告知局中人2。第二步，局中人2也在0，1中取一个数记为 r2 ，但不告知局中人1。第三步，又轮到局中人1取数。若局中人1在第一步中取0，则可以在0，1中取一个数，若局中人1在第一步中取1,则可以在0，1，2中取一个数,记第三步局中人1取得数为 r3 。三步后取数结束。现记 S= r1 + r2 + r3 。若 S 为偶数，则局中人1赢 S 记分点，局中人2输 S 记分点。若 S 为奇数，则局中人1输 S 记分点，局中人2赢 S 记分点。在这个游戏中，两个局中人各自采取什么行动？若你参加，你愿意当局中人1还是局中人2 ?,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,30,二人取数游戏1（续）,树形图表示,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,31,二人取数游戏2,将上述二人取数游戏作一个改变，游戏仍然分三步进行。第一步，有一个局外人称为“自然”在0，1中取一个数记为 r1 ，并告知局中人1，但不告知局中人2。第二步，局中人1在0，1中取一个数记为 r2 ，并告知局中人2。第三步，局中人2取数，若看到局中人1取 r2=0 ,则在0，1中取1个数，记该数为 r3 ；若看到局中人1取r2 =1, 在0，1，2中取1个数，记该数为 r3 。三步后取数结束。记 S= r1 + r2 + r3 。若S 为偶数，则局中人1赢 S 记分点，局中人2 输 S 记分点。若 S 为奇数，则局中人1输 S 记分点，局中人2赢S 记分点。在这个游戏中，两个局中人各自采取什么行动？若你参加，你愿意当局中人1还是局中人2 。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,32,二人取数游戏2（续）,树形图表示,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,33,什么是扩展式表示,扩展式表示博弈的6要素： 局中人集合 局中人的行动顺序 局中人的行动空间（行动集） 局中人的信息集 局中人的损益函数 “自然”的概率分布,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,34,局中人集合,局中人指博弈的参与人，全体局中人称为局中人集合。 局中人集合中一般不包括虚拟的参与人“自然”。 局中人集合一般记为：N=1，2，n。 “自然”一般记为“0”。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,35,局中人的行动顺序,局中人的行动顺序，也称博弈顺序。 在扩展式的表达中，除了最下端的结点外，每一个结点都要明确采取博弈行动的局中人。这样，扩展式中表明了局中人的行动顺序。 一个结点中采取行动的局中人可能不止一个局中人。 某些结点采取行动的局中人可以是“自然”。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,36,局中人的行动空间,注意： 局中人的行动集不等于参与人的策略集。 局中人的行动集不是永远不变的，而是根据局中人行动时所处的地位有关。,局中人的行动空间是指：轮到局中人i行动时，他能采取的行动集合。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,37,局中人的信息集,局中人的信息集 局中人的信息集表示在每次行动时，局中人知道什么。当局中人行动时，他对自己应在的结点位置不清楚，则把这些结点集归为一个信息集。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,38,局中人的损益函数,在一个扩展式表示的博弈中，从顶端的结点即树的根到最后一层结点即树的叶子，构成一条博弈的行动路径。这种行动路径与信息集无关。每一条行动路径表示局中人的一种行动组合。在这种组合下，即行动结束后，每个局中人所得的多少是局中人的损益函数或支付函数。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,39,“自然”的概率分布,“自然”是扩展式表示中引入的一个虚拟局中人。 “自然”可能表现出不同的状态，这些状态出现的可能情况即是“自然”选择行动的概率分布。 “自然”选择的概率分布可以是外生的，也可以是“内生”的，这视具体的情况而定。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,40,1.2.3 联盟式（特征函数式 ）,什么是联盟式表示 例1.2.5 投票博弈,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,41,联盟式表示,联盟式表示的博弈的两要素： 局中人集 局中人-同样指合作的参与人，局中人全体记为 ，当 时，即有n 个人参加的博弈称为 n 人博弈。 特征函数 局中人集合N的任意一个子集S ，即 ，称为该博弈中的一个联盟,若 S=N，称N为一个大联盟。特征函数指对任一个联盟 S 对应一个实数： ，并要求：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,42,投票博弈,现有一个董事会由4名董事组成：董事长、副董事 长、董事、董事（下面简称为局中人1，2，3，4) 在董事会进行议题表决时，董事长有3票，副董事长有2票，两名董事各有1票，4个人分别独立投票；并且投票规则规定，赞成票超过半数，表决的议题通过。问4个人的权势各有多大？,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,43,投票博弈（续）,若我们规定，议题被投票通过记为实数1，未通过记为实数0，第 个 局中人所拥有的票数为 ，则特征函数为： 不同的联盟 具有不同的特征函数值。这里,，,，,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪