《博弈论》精品讲义

正 大 光 明 公 正 無 私 1 博 弈 论 the Theory of Games css 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 2 主要内容 一、博弈现象及基本概念 二、完全信息静态博弈 三、完全信息动态博弈 四、不完全信息静态博弈 五、不完全信息动态博弈 六、不完全信息专题 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 3 主要参考书 (1) 姚国庆： 博弈论 ， 高等教育出版社 ， 2007. (2) 罗云峰： 博弈论教程 ， 清华大学出版社 、 北京交通大学出版社 。 (3) 张维迎： 博弈论与信息经济学 ， 上海三联书店 ， 上海人民出版社 ， 2004。 (4) 施锡铨 ， 博弈论 ， 上海财经大学出版社 ，2002。 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 4 (5) 张守一 ， 现代经济对策论 ， 高等教育出版社 ，1998。 (6) 钱颂迪 ， 运筹学 ， 清华大学出版社 ， 1996。 (7) 美 艾里克 .拉斯缪森： 博弈与信息 ， 北京大学出版社 ， 2003。 (8) 美 弗登博格： 博弈论 ， 中国人民大学出版社 ， 2002。 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 5 第一讲 博弈现象与基本概念 1博弈现象 2. 博弈概念 3. 博弈描述 4. 博弈练习 5. 关于博弈论 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 6 1博弈现象 田忌赛马： 正确的策略可以反败为胜 。 囚徒困境： 认罪 不认罪 认罪 （ -5,-5） （ 0,-10） 不认罪 （ -10,0） （ -1,-1） 甲 乙 理性的人是自私自利的； 理性选择不是全局最优。 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 7 经济合作： 合作 欺骗 合作 （ 2,2） （ -2,4） 欺骗 （ 4,-2） （ 0,0） 甲 乙 诚信的价值； 一报还一报策略； 人类生存环境启示。 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 8 长街上的超市 （ 海滩占位模型 ） 0 1/2 3/4 1 1/4 A O 资源浪费还是理性的必然？ 其它相似情形： 旅行社的热门路线；黄金时间的电视节目；总统竞选。 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 9 狩猎与投资 狩猎： 两个猎人围住一头鹿 ， 各卡住两个关口中的一个 ， 齐心协力即可成功获得并平分猎物 。 此时有一群兔子跑过 ， 任何一人去抓兔子必可成功 ，但鹿会跑掉 。 他们会坚持猎鹿还是去抓兔子 ？ 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 10 共同投资： 双方共同投资一个大项目 ， 可期望有较大收益 。 此时如某方抽出资金去进行小项目投资 ，必可成功获小利 ， 但会使共同项目陷入困境 ，使对方蒙受损失 。 投资者会如何选择 ？ 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 11 旅行者困境 两个旅行者花瓶被摔坏 ， 向航空公司索赔 。航空公司知道价格约为八九十元 ， 但不知道确切价格 。 于是请两位旅客在 100元以内自己写下花瓶的价格 。 如两人写的一样 ， 就认为他们讲真话 ， 并按所写数额赔偿；如果两人写的不一样 ， 就认定低者讲真话 ， 并照此价格赔偿 。 同时 ， 对讲真话的旅客奖励 2元钱 ， 对讲假话的旅客罚款 2元 。 理性原则下 ， 他们会写多少价格呢 ？ 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 12 什么是博弈： 个人或团体间在依存和对抗、合作和冲突中的决策问题。 博弈论研究博弈过程中的理性行为。 2. 博弈概念 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 13 如何理解理性行为： 自身利益最大； 持续地有意图的行动； 不对动机妄加猜测； 不考虑道德问题； 只研究合法问题； 盈利函数有多重标准。 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 14 博弈三要素 局中人 (参与人） players： 决策主体 ； 自然人、团体或“虚拟局中人”； 有可供选择的策略和明确定义的利益函数； 分为两人和多人 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 15 策略（战略） strategies： 采取行动的规则； 可以是一次行动也可以是一个行动序列； 可以是纯策略也可以是混合策略； 分为有限和无限。 支付（盈利函数） payoff： 对应于某策略组合的局中人利益或损失； 确定的或是期望的； 分为零和和非零和。 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 16 扩展术语： 信息： 信息集； 完全信息 （ complete） ； 完美信息 （ perfect） 。 共同知识： 双方可能获取的相同信息； 彼此都能算清楚 。 博弈结果： 均衡策略组合；均衡行动组合 。 均衡： 所有局中人最优策略的组合 。 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 17 博弈的策略型 （ 标准型 、 正则型 ） 表述： 指定 n个局中人 ， 以及他们各自的纯策略空间 和这些局中人各自的支付 （ 盈利 ） 函数 我们将该博弈表示为： niS i ,2,1, niSSSu ni ,2,1),( 21 3. 博弈描述 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 18 例：寡头竞争问题 ),(),(；0,0 21221121 qqqqqqG 策略型表述多适用于静态博弈 。 另一种表述方式是扩展式表述 ， 两种表述形式几乎是完全等价的 ， 但是扩展式表述更适合于讨论动态博弈 。 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 19 房地产开发实例 双方： A， B 策略： 开发投资 1亿元；不开发 ， 投资 0 售价： 高需： 1.4亿元 (两栋 )， 1.8亿元 (一栋 )； 低需： 0.7亿元 (两栋 )， 1.1亿元 (一栋 )。 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 20 结果： 高需 ， (开 ， 不开 )， (0.8， 0) 高需 ， (不开 ， 开 )， (0， 0.8) 高需 ， (开 ， 开 )， (0.4， 0.4) 高需 ， (不开 ， 不开 )， (0， 0) 低需 ， (开 ， 不开 )， (0.1， 0) 低需 ， (不开 ， 开 )， (0， 0.1) 低需 ， (开 ， 开 )， (-0.3， -0.3) 低需 ， (不开 ， 不开 )， (0， 0) 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 21 策略型表述： （ 两人有限博弈；矩阵形式） 开发 不开发 开发 （ 0.4,0.4） （ 0.8,0） 不开发 （ 0,0.8） （ 0,0） A B 高需求情况 低需求情况？ 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 22 房地产博弈分析 假设： 同时决策；市场需求双方已知 若市场需求大，双方开发，各得 0.4万元。 若市场需求小，依赖于对方行动。 若市场不确定，依赖对市场的判断及对方行动。 例： P 0.5,最坏情况期望盈利 500万元，开发。 P 0.3,对方开发概率 31/40时，开发；否则，不开发。（？） 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 23 关键问题： 对自然状态的概率估计； 不同时间决策（决策顺序）； 对对方先验信息的估计（即估计对方对信息的掌握程度）。 现实困难： 对市场了解程度不同； 对对方了解程度不同； 如何向对方暗示自己的行动。 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 24 4.博弈练习 游戏一： 心灵感应 两个人一组 ， 独立写出 1至 10之间的任意 5个数 。 如果不重复则得奖；否则受罚 。 获胜的秘诀是什么 ？ 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 25 游戏二： 海盗逃生 有 5个海盗，即将被处死刑。法官愿意给他们一个机会。从 100个黄豆中随意抓取，最多可以全抓，最少可以不抓，可以和别人抓的一样多。抓得最多的和最少的要被处死。 如果你第一个抓，你抓几个？ 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 26 游戏三： 100元怎么分？ 你看见两个小孩在玩耍，出于好奇，你给他们 100元，让他们猜拳。猜赢者决定怎么分这 100元，而输者如果同意赢者的分配比例，那么他们将各有所得，如果不同意，那么这 100元，你将收回。 请你替赢者考虑一下，怎样分配，赢者既得到最大利益，又能让输者也同意呢？ 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 27 游戏四： 一元钱竞拍 给一元钱钞票开出你的价钱，使自己获益最大或损失最少；每次叫价以 5分钱为单位；开价最高者得到这一元钱；出价最高和次高者一并按所开的价钱支付。 斜坡上的均衡； “ 骑虎难下 ” 的博弈； “ 协和谬误 ” 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 28 游戏五： 强盗分赃 有五个强盗抢得 100枚金币，在如何分赃问题上争吵不休。于是他们决定： （ 1）抽签决定自己的号码（ 1， 2， 3， 4，5）； （ 2）由 1号提出分配方案，然后 5人表决，如果方案超过半数同意就通过，否则他将被仍进大海喂鲨鱼； 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 29 （ 3） 1号死后，由 2号提方案， 4人表决，当且仅当超过半数同意方案通过，否则 2号同样被仍进大； （ 4）依次类推，直到找到一个每个人都接受的方案（当然，如果只剩下 5号，他当然接受一个人独吞的结果）。 如果你是第一个强盗，你该如何提出分配方案才能使自己的收益最大化呢？ 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 30 5. 关于博弈论 博弈分类 : 合作、非合作： 是否存在一个具有约束力的协议（ binding agreement） 前者强调团体理性（效率、公正、公平） 后者强调个人理性（最优决策，不保证效率） 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 31 完全信息与不完全信息： 每一个局中人对自己及其它局中人是否有完全的了解； 包括局中人特征、策略空间、盈利函数等知识。 动态与静态： 行动的先后顺序 ； 是否同时（或不同时但对方不知）。 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 32 发展历史： 1944 Von Neumann & Morgenstern “The theory of games and economic behavior” 1950 Nash & 1953 Shapley “讨价还价 ” 模型 1950、 1951 Nash 非合作博弈 1950 Tucker Prisoners dilemma 1953 Gillies & Shapley 合作博弈 1965 Selton 动态分析 ； “精炼纳什均衡 ” 1967、 1968 Harsanyi “不完全信息 ” 1994 Nash 、 Selton、 Harsanyi 诺贝尔经济学奖 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 33 纳什的传奇人生 1928年出生于一个电子工程师家庭。 17岁进入今卡耐基梅隆大学，专攻数学。 20岁时进入普林斯顿大学攻读博士学位。 1949年， 21岁的纳什写下论文 多人博弈的均衡点 。 1950年以论文 非合作型博弈 获得数学博士学位。 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 34 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 35 毕业后先后在兰德研究所、普林斯顿大学、 MIT工作。 1957年他与 MIT学生爱莉西娅结婚。 在而立之年患上了妄想型精神分裂症，九十年代逐渐恢复了正常。 1994年纳什博士获诺贝尔经济学奖。 2002年来北京参加 “ 国际数学家大会 ” 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 36 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 37 电影 “美丽心灵” 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 38 静态 动态 完全 信息 完全信息静态博弈 纳什均衡 纳什（ 1950， 1951） 完全信息动态博弈 子博弈精炼纳什均衡 泽尔滕（ 1965） 不完全信息 不完全信息静态博弈 贝叶斯纳什均衡 海萨尼（ 1967 1968） 不完全信息动态博弈 精炼贝叶斯纳什均衡 泽尔滕（ 1975） 博弈论体系 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 39 第二讲 完全信息静态博弈 1.矩阵博弈 2.累次严优均衡 3.纳什均衡 4.混合策略纳什均衡 5.纳什均衡的存在性与多重性 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 40 1. 矩阵博弈 什么是矩阵博弈： 两人零和有限策略博弈； 可用矩阵形式表述。 矩阵元素为局中人 A的赢得，亦即 B的损失。 例： 用矩阵形式表述田忌赛马博弈（？） 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 41 有鞍点情形 ： 存在最优纯策略 例： 表中数据为 I的赢得 II I 1 2 3 min 1 6 1 8 8 2 3 2 4 2 3 9 1 10 10 4 3 0 6 3 max 9 2 6 2 博弈哲学 ： 从最坏处考虑，争取最好结果 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 42 无鞍点情形： 最优混合策略 例： II I 1 2 min 1 11 5 5 2 7 9 7 max 11 9 ? )1,(),()；1,(),( 2121 yyxx 设最优混合策 略： 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 43 对局中人 I： 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 44 I的最优混合策略为 同理 ， II的最优混合策略为 G 8 同理可求局中人 II的最优混合策略 （ ？ ） )21,21(),( 21 )43,41(),( 21 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 45 2.累次严优均衡 占优策略均衡 (严格 )劣策略： 无论对方如何选择都更差 。 占优策略： 无论对方如何选择存在唯一最优 。 占优策略均衡： 所有局中人占优策略的组合 。 特点： 只要求每个人理性 ， 并不要求知道其它人是不是理性 。 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 46 例：裁军问题 以巴 武装 裁军 武装 （ 3000, 3000） （ 10000 ， ） 裁军 （ , 10000） （ 0,0） 例： 囚徒困境中的（认罪，认罪） 例： 房地产投资市场大情况下（开发，开发） 博弈论 2009 正大光明 公正無私 幫助別人 成就自己 47 重复剔除的占优均衡 （ iterated elimination） 也称为累次严优均