博弈论-1.ppt

决策理论与方法 博弈论1 合肥工业大学管理学院2020年2月15日 2020年2月15日4时12分 决策理论与方法 博弈论 博弈论 1 博弈论的基本概念2 完全信息静态博弈3 完全信息动态博弈4 非完全信息静态博弈5 非完全信息动态博弈 2020年2月15日4时12分 决策理论与方法 博弈论 什么是博弈 棋牌游戏体育竞赛产品定价军事对抗博弈论 在多决策主体之间行为具有相互作用时 各主体根据所掌握信息及对自身能力的认知 做出有利于自己的决策的一种行为理论 博弈四要素 参加者 players 策略集或行动集 actions 博弈的次序 orders 损益 payoffs 2020年2月15日4时12分 决策理论与方法 博弈论 博弈论相关术语 1 参与人 players 理性选择的主体 i 1 2 nNature 自然环境 虚拟参与人2 行动 action 选择变量 ai代表参与人i的某一行动选择 Ai代表参与人i的选择空间 行动的顺序 theorderofaction 3 信息 information 参与人有关博弈的知识 4 策略 strategies 参与人的行动方案 预案 si代表参与人i的某一策略 Si代表参与人i的策略空间5 损益 payoff 参与人的得与失 参与人i的损益函数为ui s1 si sn 2020年2月15日4时12分 决策理论与方法 博弈论 博弈论相关术语 6 结局 outcome 某种行动 策略或损益的组合7 均衡 equilibrium 行为主体间相互作用的一种结局 在该结局中 参与人无法通过改变策略增加收益 效用 又称 僵局 此乃局外人所关心的 8 博弈 game 参与人的集合 策略空间的集合 损益函数的集合 博弈G S1 Sn u1 un 9 博弈论 gametheory 研究在给定的博弈中 各参与人的策略 行为 选择及其结局 2020年2月15日4时12分 决策理论与方法 博弈论 博弈论相关术语 10 博弈的规则 rulesofthegame 参与人 行动 结局 规则是一种人为的限制 对资格 行为主体 的限制 对行动空间 选择空间 的限制 并建立行动与结局 损益 之间的联系 游戏规则决定游戏的结局游戏规则是博弈的结果 2020年2月15日4时12分 决策理论与方法 博弈论 博弈问题分类 2020年2月15日4时12分 决策理论与方法 博弈论 博弈论基本假设 1 理性假设 Rationality 认知的理性 自我利益的最佳判断者偏好的完备性 completeness 偏好的传递性 transitivity 行为的理性 利益最大化 自我利益的追求者2 共同知识假设 commonknowledge 理性共识 commonknowledgeofrationality Zero orderCKR 每个人都是理性的 但不知道其他人是否是理性的 First orderCKR 每个人是理性的 并且知道其他每个人也都是理性的 但并不知道其他人是否知道自己是理性的博弈规则共识 commonknowledgeoftherulesofthegame 2020年2月15日4时12分 决策理论与方法 博弈论 博弈论分析方法 1 最大化分析 求极值给定约束条件 游戏规则 和损益 求最大值 博弈论专家的主要工作是研究约束条件 正确的决策取决于对约束条件的正确判断 2 均衡分析 极值的组合分析 2020年2月15日4时12分 决策理论与方法 博弈论 博弈矩阵 2020年2月15日4时12分 决策理论与方法 博弈论 博弈论发展历程 1838年古诺 Cournot 寡头竞争模型1883年伯川德 Bertrand 寡头竞争模型1944年冯 诺依曼和摩根斯坦发表 博弈论和经济行为 1950年纳什 Nash 提出了纳什均衡的概念 1965年泽尔腾 Selten 提出了子博弈精炼纳什均衡的概念1967 1968年海萨尼 Harsanyi 提出了贝叶斯纳什均衡的概念1975 1991年泽尔腾 1975 Kreps和Wilson 1982 Fudenberg和Tirole 1991 提出了精炼贝叶斯纳什均衡的概念 2020年2月15日4时12分 决策理论与方法 博弈论 博弈论发展历程 六届诺贝尔经济学奖 1994年 美国伯克利加利福尼亚大学的约翰 海萨尼 J Narsanyi 普林斯顿大学约翰 纳什 J Nash 和德国波恩大学的赖因哈德 泽尔滕 ReinhardSelten 1996年 英国剑桥大学的詹姆斯 莫里斯 JamesA Mirrlees 与美国哥伦比亚大学的威廉 维克瑞 WilliamVickrey 2001年 美国加州大学伯克莱分校的乔治 阿克尔洛夫 GeorgeA Akerlof 美国斯坦福大学的迈克尔 斯宾塞 A MichaelSpence 和美国纽约哥伦比亚大学的约瑟夫 斯蒂格利茨 JosephE Stiglitz 2005年 美国马里兰大学的托马斯 克罗姆比 谢林 ThomasCrombieSchelling 和耶路撒冷希伯来大学的罗伯特 约翰 奥曼 RobertJohnAumann 2007年 美国明尼苏达大学的里奥尼德 赫维茨 LeonidHurwicz 美国普林斯顿大学的埃里克 马斯金 EricS Maskin 以及美国芝加哥大学的罗杰 迈尔森 RogerB Myerson 2012年 哈佛商学院教授埃尔文 罗斯 AlvinE Roth 2020年2月15日4时12分 决策理论与方法 博弈论 几类典型的博弈模型 囚徒困境 prisoner sdilemma 两个嫌疑犯作案后被警察抓住 分别关在不同的屋子里接受审讯 警察知道两人有罪 但缺乏足够的证据 警察告诉每个人 如果两人都抵赖 各判刑一年 如果两人都坦白 各判五年 如果两人中一个坦白而另一个抵赖 坦白的放出去 抵赖的判八年 嫌疑犯会怎么决策 2020年2月15日4时12分 决策理论与方法 博弈论 几类典型的博弈模型 为什么市场常出现价格战 囚徒困境的实际应用 垄断市场的两个寡头以较高价销售可替代的同一种产品 各获得利润10亿元 若一方不满足现在的市场份额而采取降价策略 背叛 另一方没有选择降价 市场份额将发生变化带来收益的变化 降价方将获得15亿元 不降价方将获得2亿元 这必然遭到不降价方的报复而实施降价 双方获得的收益各为7亿元 2020年2月15日4时12分 决策理论与方法 博弈论 几类典型的博弈模型 赌胜博弈 假设我和你一起玩 石头 剪子 布 的游戏 如果我告诉你说 我准备出 石头 请问 你会出什么 赌注为100元 田忌赛马 特点 保密自己的策略 一次博弈的结果是无法确定的 2020年2月15日4时12分 决策理论与方法 博弈论 几类典型的博弈模型 产量决策的古诺模型 n个具有相同生产条件的企业分享总容量为a的市场 设市场出清价格 p a Q a q1 q2 qn 若Q a p 0 则各自的产量为多少才会处于平衡状态 求厂家i最佳产量的思路 设其他n 1家企业均按照最佳产量生产 且产量和为q i 则p a qi q i 厂家i的收益为 i p qi a qi q i qi使 i有极大值 i对qi的导数 0 qi a q i 2 i 1 2 n 联合求解该方程组即可得到均衡解 若考虑到各企业的生产条件相同 因此它们的最佳生产量也应该相同 故q i n 1 qi 因而求得qi a n 1 思考 若考虑到企业的生产成本 如固定成本为c 可变成本每件为d 那么各自的产量又是多少 i a qi q i qi c d qi 2020年2月15日4时12分 决策理论与方法 博弈论 博弈论 1 博弈论的基本概念2 完全信息静态博弈3 完全信息动态博弈4 非完全信息静态博弈5 非完全信息动态博弈 2020年2月15日4时12分 决策理论与方法 博弈论 完全信息静态博弈 各博弈方同时决策 且所有博弈方对各方损益均了解的博弈 囚徒困境 赌胜博弈 古诺模型都是完全信息静态博弈 完全信息静态博弈的特点 策略集已知互不知道对方选择何种策略各博弈方的损益完全可预见完全信息静态博弈是非合作博弈的最基本类型 2020年2月15日4时12分 决策理论与方法 博弈论 上策均衡 上策均衡 Dominantstrategyequilibrium 若存在一个策略A 无论对方选择什么策略 选择策略A的得益不比选择其他任何策略差 则A为上策 Dominantstrategy 博弈方总是优先选择上策 坦白 若存在一个策略组合 使得该组合中的策略对各自的博弈方均是上策 则该策略组合为博弈中的一个 上策均衡 坦白 坦白 2020年2月15日4时12分 决策理论与方法 博弈论 重复删除严格劣策略 重复删除严格劣策略 IteratedEliminationofstrictlyDominatedStrategy 若存在策略A B 无论对方选择什么策略 选择策略B的得益均比选择策略A差 则称B为严格下策 strictlyDominatedStrategy 反复将存在的严格下策删除 该方法既能求解包含上策均衡的博弈 也能求解或简化一些不存在上策均衡 但存在一定特殊结构的博弈模型 2020年2月15日4时12分 决策理论与方法 博弈论 划线法 上述两种方法均是根据策略之间的绝对优劣作为选择标准的 而在实际博弈中 这种绝对优劣关系往往并不存在 而只是存在相对优劣关系 划线法可根据相对优劣关系找到可能存在的均衡解 划线法的过程如下 从各个博弈方出发 在假定对方选择某一策略的情况下 自己应该选择什么策略使自己得益最大 该策略一定存在但不一定惟一 并将此策略所对应的得益用下划线标记 若各博弈方的某个策略组合所对应的得益均被下划线标记 则此策略组合即为均衡解 2020年2月15日4时12分 决策理论与方法 博弈论 划线法 划线法适合于求解具有惟一的 确定性的均衡解的博弈问题 2020年2月15日4时12分 决策理论与方法 博弈论 箭头法 有些博弈问题不存在确定性均衡解 如石头 剪子 布 或存在多个确定性均衡解 如夫妻之争就有两个确定性均衡解 丈夫偏向于看拳击 妻子偏向于看电影 但大家都更愿意一起行动 用箭头法可以帮助我们看出均衡解的转移过程 箭头法 当博弈双方处于一个不稳定的策略组合时 将会使得某一博弈方单独改变策略 用箭头表示转移方向 而使其得益增加 直到稳定状态出现 2020年2月15日4时12分 决策理论与方法 博弈论 箭头法 2020年2月15日4时12分 决策理论与方法 博弈论 纳什均衡 博弈G S1 S2 Sn u1 u2 un 其中Si表示博弈方i的策略集 ui表示在某个策略组合下博弈方i的得益 是各博弈方策略的多元函数 Si中的某个策略用si表示 则其余n 1个博弈方的策略组合 s1 s2 si 1 si 1 sn 用s i表示 纳什均衡 NashEquilibrium 对于博弈G和s i 如果存在si 使得对任意si Si有ui si s i ui si s i 则称 si s i 为G的一个纳什均衡 s i 表示其他n 1个博弈者所选择的最佳策略组合 上述方法均可用来求解纳什均衡 但并不是所有的纳什均衡均可用上述方法获得 如多方博弈 无限博弈等问题 2020年2月15日4时12分 决策理论与方法 博弈论 纳什均衡 纳什均衡的一致预测性质当博弈各方预测到存在一个特定的博弈结果出现 那么所有博弈方都不愿偏离这一博弈结果 因此此博弈结果最终会成为实际结果 反之 所有博弈方均不愿偏离的博弈结果也一定是纳什均衡解 纳什均衡与均衡求解方法间的关系若某博弈存在上策均衡 则该上策均衡一定是纳什均衡 反之 并不是所有具有纳什均衡的博弈都有上策均衡 上策均衡是一种最稳定的均衡解 划线法 箭头法找到的均衡解均是纳什均衡解 消去法得到的均衡解也是纳什均衡 纳什均衡在消去过程中不可能被删除 若消去法获得一个均衡解 则该均衡解一定是纳什均衡解 2020年2月15日4时12分 决策理论与方法 博弈论 无限策略博弈分析和反应函数 产量决策的古诺模型 qi a q i 2反应函数 reactionfunction 对于博弈G 博弈方i的得益函数是 ui ui si s i 根据得益最大化原则 博弈方i在得知其他n 1个博弈方的策略组合是s i时 其选择si的依据是使ui最大 因此ui对si的导数应为0 即dui dsi 0 对此方程做变化 得到si Ri s i 称此函数是博弈方i对其他博弈方策略组合s i的反应函数 i 1 2 n 联立求解上述n个方程 即可得到均衡解 s1 s2 sn 从几何图上观察 每个方程对应于n维空间上的一个曲面 当n 2时即为曲线 这些曲面的交点即为均衡解 反应函数只能适合求解具有连续得益函数的博弈问题 且要求这些博弈问题存在惟一均衡解 否则就不适合使用反应函数 2020年2月15日4时12分 决策理论与方法 博弈论 混合策略和混合纳什均衡 混合策略 mixedstrategy 在博弈G中 博弈方i的策略空间包含k种可选策略 则i以概率分布pi pi1 pi2 pik 或pij p sij 随机选择的策略称为混合策略 可确定性选择的策略称为纯策略 purestrategy 它是混合策略的一种特殊形式 混合策略纳什均衡 由混合策略构成的新的策略空间所对应的博弈称为该博弈的混合策略扩展博弈 每个混合策略就成了该扩展博弈的纯策略 这时纳什均衡就是扩展博弈模型中的均衡解 求解均衡解的关键是求得最佳的概率分布 2020年2月15日4时12分 决策理论与方法 博弈论 混合策略纳什均衡的求解 设G S1 S2 Sn u1 u2 un 对于博弈方i 从策略集Si中选择策略sij的概率为pij 其概率分配的原则是 或者使自身的收益最大 或者使对方无论选择什么策略均具有相等的得益 2020年2月15日4时12分 决策理论与方法 博弈论 混合策略纳什均衡的求解 设A选择S1和S2的概率分别是p和 1 p B选择T1和T2的概率分别是q和 1 q 则A的收益为 UA p q 2 1 q 5 1 p q 3 1 q 1 4p 5pq 2q 1UB q p 3 1 p 1 1 q p 2 1 p 5 3p 5pq 4q 5UA对p求导且令其为0 即4 5q 0 得q 0 8UB对q求导且令其为0 即5p 4 0 得p 0 8 2020年2月15日4时12分 决策理论与方法 博弈论 混合策略纳什均衡的求解 或者当A选择S1和S2的概率分别是p和 1 p 时 B无论选择T1或T2 其得益均相同 即p 3 1 p 1 p 2 1 p 5 解得p 0 8 同理可得q 0 8 类似可讨论有两个纯策略纳什均衡的 夫妻之争 博弈问题 2020年2月15日4时12分 决策理论与方法 博弈论 混合策略纳什均衡的求解 对于无限策略博弈分析 设博弈方i策略空间的概率分布函数为fi Si 则博弈方i在混合策略扩展博弈下的得益为 其中 博弈的目标是使博弈方i在对方确定的策略空间 S i确定 下得益最大化 因此有 联立方程组 即可解得fi Si 2020年2月15日4时12分 决策理论与方法 博弈论 纳什均衡的存在性 纳什定理 1950 在一个有n个博弈方的博弈G中 如果n是有限的且每个博弈方i的策略集Si是有限集 则该博弈至少存在一个纳什均衡 可能是纯策略纳什均衡 也可能是混合策略纳什均衡 2020年2月15日4时12分 决策理论与方法 博弈论 纳什均衡的选择与分析方法扩展 帕累托上策均衡 当博弈中存在多个均衡时 如某个均衡对各博弈方的得益均大于另一个均衡 则各博弈方会优先选择该纳什均衡 称此纳什均衡为 帕累托上策均衡 如战争与和平问题 2020年2月15日4时12分 决策理论与方法 博弈论 纳什均衡的选择与分析方法扩展 风险上策均衡 riskdominantequilibrium 虽然存在帕累托上策均衡 但若选择该均衡存在较大风险时 则会选择另一个均衡 以求降低风险 依据是当选择每个均衡的概率相等时 博弈方的期望得益哪个更大 如猎鹿博弈问题 选择 1 2概率 猎鹿 猎鹿 的期望得益是5 而选择 猎兔 猎兔 的期望收益是7 参与博弈的人越多 风险上策被选择的可能性就越大 选择风险上策的人越多 选择帕累托上策均衡的风险就越大 2020年2月15日4时12分 决策理论与方法 博弈论 纳什均衡的选择与分析方法扩展 聚点均衡 FocalPointEquilibrium 如果不存在帕累托上策均衡 如夫妻之争问题 则对均衡解的选择是困难的 但如果借助一些诸如文化 背景知识 特殊因素等信息 可能就会将目标聚焦到某个更恰当的解上 例如某个文化强调尊重妇女 则可能选择利于妻子的均衡策略 而另一种文化属于男权主义社会 则更可能选择利于丈夫的均衡策略 这些体现了某些特征的策略被称为 聚点 双方同时选中一个聚点构成的纳什均衡就称为 聚点均衡 如 报时间匹配 游戏中的一些特殊时间点 如12点等 就是聚点 聚点 很难根据一般规律寻找 只能根据具体问题 具体分析 2020年2月15日4时12分 决策理论与方法 博弈论 纳什均衡的选择与分析方法扩展 相关均衡 correlatedequilibrium 双方借助一定的措施或规则进行选择所得到的均衡解 例如 夫妻之争可以按照下列规则选择 天晴就去看足球 下雨就去看电影 在制定这类规则时一般要避免出现最差结果 相关均衡甚至