信息与博弈

Size: px

Start display at page:

Download "信息与博弈"

眉炬茹
5 years ago
Views:

1 信息与博弈校通识课 GEN14251L 天津师范大学计算机与信息工程学院张少强

课程介绍与考核方式主讲人 : 张少强每周 3 课时 ; 共 11 讲 ;33+1 课时课件下载地址 http://www.escience.

2 课程介绍与考核方式主讲人 : 张少强每周 3 课时 ; 共 11 讲 ;33+1 课时课件下载地址问题答疑 zhangshaoqiang@tjnu.edu.cn 考核方式 (100%): 作业 20%+ 点名 20%+ 期末论文 60%

3 参考书目 Eric Rasmusen, Game and Information: An Introduction to Game Theory (4th Ed.), BLACKWELL Publishing. 中译本, 博弈与信息 : 博弈论概论 ( 第四版 ), 中国人民大学出版社焦宝聪, 陈兰平 : 博弈论, 首都师范大学出版社,2013 通识课教材. 教材可以不用购买

4 课程开始语要想在现代社会做一个有文化的人, 你必须对博弈论有一个大致了解 ---- Paul A. Samuelson( 保罗萨缪尔逊,1970 年诺贝尔经济学奖得主 )

经典人物 : 约翰纳什 John Nash 1928.6.13 -- 2015.

岁的纳什以非合作博弈 (Non-cooperative Games) 为题的 27 页博士论文毕业他在那篇仅仅 27 页的博士论文中提出了一个重要概念, 也就是后来被称为纳什均衡的博弈理论 1958 年, 幻听幻觉, 直到上世纪

5 经典人物 : 约翰纳什 John Nash , 普林斯顿大学数学系教授, 在非合作博弈的均衡分析理论方面做出了开创性的贡献, 对博弈论和经济学产生了重大影响, 与其他两位博弈论学家约翰 C 海萨尼和莱因哈德泽尔腾一起获得 1994 年诺贝尔经济学奖 1950 年,22 岁的纳什以非合作博弈 (Non-cooperative Games) 为题的 27 页博士论文毕业他在那篇仅仅 27 页的博士论文中提出了一个重要概念, 也就是后来被称为纳什均衡的博弈理论 1958 年, 幻听幻觉, 直到上世纪 80 年, 一直在普林斯顿校园游荡妻子艾里西亚在纳什生病期间精心照料他 30 年因精神问题, 错失了数学的最高奖 -fields 奖要不是 30 多年的严重精神病折磨, 恐怕他早已站在诺贝尔奖的领奖台上了, 而且也绝不会与其他人分享这一殊荣 2015 年 5 月 23 日, 约翰纳什夫妇遇车祸, 在美国新泽西州逝世, 终年 86 岁他 82 岁的夫人艾丽西亚也在车祸中去世

6 起源数学家冯诺伊曼与摩根斯顿 (von Neumann & Morgenstern) 于 1944 年出版的名著博弈理论与经济行为 (The Theory of Games and Economic Behavior).

7 博弈论与诺贝尔经济学奖 1994: 美国人约翰海萨尼 (John C. Harsanyi) 和美国人约翰纳什 (John F. Nash Jr.) 以及德国人莱因哈德泽尔腾 (Reinhard Selten) 获奖理由 : 在非合作博弈的均衡分析理论方面做出了开创性的贡献, 对博弈论和经济学产生了重大影响 1996: 英国人詹姆斯莫里斯 (James A. Mirrlees) 和美国人威廉 - 维克瑞 (William Vickrey) 获奖理由 : 前者在信息经济学理论领域做出了重大贡献, 尤其是不对称信息条件下的经济激励理论的论述 ; 后者在信息经济学激励理论博弈论等方面都做出了重大贡献

8 博弈论与诺贝尔经济学奖 2001: 三位美国学者乔治阿克尔洛夫 (George A. Akerlof) 迈克尔斯宾塞 (A. Michael Spence) 和约瑟夫斯蒂格利茨 (Joseph E. Stiglitz) 获奖理由 : 应用博弈论在对充满不对称信息市场进行分析领域做出了重要贡献 2005: 以色列经济学家罗伯特奥曼 (Robert J. Aumann) 和美国经济学家托马斯谢林 (Thomas C. Schelling) 获奖原因 : 通过博弈论分析加强了我们对冲突和合作的理解所作出的贡献而获奖

9 博弈论与诺贝尔经济学奖 2007: 三位美国学者 : 里奥赫尔维茨埃里克马斯金罗杰迈尔森获奖理由 : 在应用博弈论创立和发展机制设计理论方面的突出贡献 2012: 两位美国学者 : 埃尔文罗斯罗伊德夏普利 ( 合作博弈 )

10 实际上, 博弈论已经潜移默化运用到我们的日常生活只是你不像学者上升到理论探讨和研究

11 想一想? 假如你正在跟家人或恋人 ( 注 : 不是普通朋友或陌生人 ) 用手机通电话, 突然信号断了这时, 你会立即拨打电话过去, 还是等你的家人拨电话过来呢? 很显然, 你是否应该拨电话过去, 取决于你的家人是否拨打回来其中一方拨, 另一方最好是等待 ; 若一方等待, 另一方最好是拨回去 ; 若双方都拨, 那会出现线路忙, 若双方都等待, 那时间就会在等待中流逝

12 这, 就是博弈! 在一场博弈中, 你必须考虑对方的选择以确定你自己的最优选择, 而对方也必须考虑你的选择来确定 ta 的最优选择你从博弈中得到的结果, 不仅取决于你的行动策略, 也取决于对方的行动策略 ( 例如 : 你若你知道家人经常是等你电话, 或者对方接听免费而你包月额度足够, 那你的最优策略就是拨回去 ) 博弈最本质的特征是 : 双方的行动相互影响又相互依赖

13 无处不在的博弈人们在日常生活中进行着博弈 : 同学间, 配偶, 朋友, 与陌生人, 老板 / 员工, 师生等类似的博弈也在商业活动政治和外交事务战争中进行着在任何一种情况下, 人们相互影响以达成彼此有利的协议或者解决争端博弈论为众多学科提供了分析的概念和方法 : 经济学商学政治学生物学心理学哲学信息科学, 等等但很多专业很少就博弈单独开设一门课程

14 例 1: 经典小故事 - 田忌赛马比赛规则 : 马分上中下三等, 马的装饰也不同 ; 三赛两胜赢比赛比赛方 : 田忌齐威王比赛前, 田忌按照孙膑的主意偷换马的配饰 : 第一场田忌用下等马冒充上等马与齐威王的上等马比赛 ; 第二场田忌用上等马冒充中等马与齐威王的中等马比赛 ; 第三场用中等马冒充下等马与齐威王下等马比赛结果 2:1, 田忌赢在双方条件相当时, 对策得当可以战胜对方, 在双方条件相差很远, 对策得当可将损失减低到最低程度

15 其它常见身边例子石头剪刀布划拳 ( 老虎鸡虫杠子 ) 下棋拍卖是否逃课与老师是否点名论文抄袭与被人发现行人与机动车工资要求与工作机会你能举出几个博弈论的例子?? 人类社会始终面临竞争对抗冲突妥协合作选择是人生的最大智慧如何选择策略?

16 例 2: 点名博弈学生如果逃课没有被发现 ( 也就是没有点名 ), 那 ta 就会利用逃课时间获得 2 个单位的收益 ; 若逃课被发现 ( 点名 ), 那就会影响自己的成绩, 其得益为 -3 单位不管老师点不点名,ta 来上课, 就收益 1 个单位老师点名花费时间, 若点名没逃课, 老师收益为 -1; 如果点名有逃课的老师收益是 -2. 若有很多逃课的老师没有点名, 教学效果差, 老师收益 -4; 若学生不逃课, 老师也不点名, 老师教学效果好并节省点名时间的收益为 2 单位

17 老师 \ 学生逃课不逃课点名 -2,-5-1,1 不点名 -4,2 2,1 老师和学生的最佳对策是什么?

18 例 3: 教授为什么严苛许多教授强硬地规定, 不允许迟交作业或论文教授们为何如此苛刻? 如果允许某种迟交, 那么学生就总是会迟交避免这一滑梯通常只有一种办法, 就是没有例外的策略问题是, 一个好心肠的教授如何维持如此铁石心肠的承诺? 1 拿行政程序或学校规定来做挡箭牌 2 在课程开始时做出明确和严格的宣布 3 通过几次严打

19 ( 学生教师 ) 教师惩罚不惩罚学生迟交 (-10,10) (10,-10) 按时 (-10,-10)(10,10) 学生选择迟交的情况下, 教师选择惩罚的收益最大 ;(-10,10) 学生选择按时的情况下, 教师选择不惩罚的收益最大 ;(10,10) 在 (-10,10) 和 (10,10) 情况下, 学生只有选择 (10,10) 收益最大

20 例 4: 无谓竞争你所注册的一门课程按照比例来给分 : 无论期末论文写的好与差, 只有 40% 的人能够得优秀, 40% 的人能得良好所有学生达成一个协议, 大家都不要太用功, 如何? 想法不错, 但无法实施! 稍加努力即可胜过他人, 诱惑大矣 ( 这就是为何总有叛徒?) 问题是 : 大家都这么做, 这样一来, 所有人的成绩都不比大家遵守协议来得高而且, 大家还付出了更多的功夫去比较正因为这样的博弈对所有参与者存在着或大或小的潜在成本, 如何达成和维护互利的合作就成为一个值得探究的重要问题

21 博弈论 (Game Theory) 在对抗与冲突时如何选择最优策略的学问又名 : 对策论, 游戏论 ; 是研究相互依赖相互影响的决策主体的理性决策行为以及这些决策的均衡结果的理论运筹学 (Operations Research) 的一个分支, 运筹学是数学的一个专业

22 基本假设 : 理性人的理性行为强调个人理性, 即理性的选择 : 指博弈参与者通常选择使其收益最大化的策略博弈论研究的是理性行为 : 参与博弈的每个人都会根据对手的策略, 选择自己的最优反应, 以最大化自身的利益注意 : 理性的假设不仅包括每个参与人是理性的, 而且彼此也都知道对方是理性的注意 : 不考虑道德良心情感等因素

23 如何描述一个博弈? 一个博弈中的基本要素 : 1 参与人 (players): 局中人博弈方 : 能独立做决策和独立行动且承担决策结果的个体或组织 2 行动 (actions): 参与人的行动一个参与人可采用的全部行动形成行动集 3 支付 (payoffs): 每个参与人选择策略后所获得的收益可以是实际支付, 也可是期望支付 4 信息 (information): 参与人在特定时点对不同变量取值的了解参与人的信息集是随博弈的进程变化的 ( 例如打牌 ) 形成博弈规则 (PAPI)

24 信息知己知彼, 百战不殆完美信息不完美信息确定性不确定性对称信息非对称信息不完全信息完全信息共同知识

25 博弈的分类合作博弈与非合作博弈 ; 完全信息博弈与不完全信息博弈 ; 静态博弈与动态博弈 ; 常和博弈与非常和博弈 ( 零和非零和 ); 结盟博弈与不结盟博弈

26 课程章节设置 1. 博弈论的规则包括策略均衡聚点等 (3 学时 ) 2. 纳什均衡 (3 学时 ) 3. 信息包括信息集完美信息确定信息对称信息等 (3 学时 ) 4. 混合策略和连续策略 (3 学时 ) 5. 动态博弈 (3 学时 ) 6. 子博弈 (3 学时 ) 7. 重复博弈 (3 学时 ) 8. 三人博弈 (3 学时 ) 9. 合作博弈 (3 学时 ) 10. 合作博弈续 (3 学时 )

27 一点点数学要求授课时尽量减少数学公式, 尽量改用图表简单了解一点数学 ( 例如 : 函数向量矩阵集合组合排列古典概率正态分布等 ) 简单的数学符号 (min max n! (a,b) Sup, Inf, x, 等 ) 用到时再做介绍 ( 科学并不一定意味着繁琐的计算和测量, 而是一种具有浓厚艺术气息的思维方式, 例如 : 曹冲称象 )

28 学习博弈论的目的博弈论首先是我们思索现实世界的一套逻辑, 其次才是把这套逻辑严密化成数学形式不是为了享受博弈分析的过程, 而是学会运用博弈智慧来指导我们现实的生活工作中的决策

29 第一讲博弈论的规则基本的定义优势策略重复剔除优势

30 1.1 基本定义参与人行动支付信息策略均衡结果

31 案例 1: 干洗店博弈某社区有一家干洗店 ( 老店 ), 某商家也打算在该社区开设一家干洗店 ( 新店 ), 若老店听到有人要开新店, 决定是否打价格战还是继续保持原价来逼退新店另外, 新店开与不开也与当前的经济是否景气有关参与人 : 做决策的个体, 每个参与人的目标都是通过选择行为来最大化自身的收益 ( 老店和新店是参与人 ) 虚拟参与人 : 以纯机械的方式行动, 行动不受其他参与人的影响自然 : 自然是一种虚拟参与人, 在博弈的特定时点上以特定的概率随机选择行动 ( 自然决定经济景气概率 0.7, 不景气 0.3)

32 干洗店博弈 : 行动和支付参与人 i 的行动以 a i 表示, 表示他所能作出的某一选择参与人 i 的行动集 A i ={a i } 是其可以采用的全部行动的集合新店的行动集 ={ 开店, 不开店 } 老店的行动集 ={ 降价, 原价 } 参与人 i 的支付 : 表示所有参与人和自然都选择了各自策略后, 参与人 i 的期望效用, 或博弈完成后的实际效用经济景气 ( 单位 : 万元 ) ( 新店, 老店 ) 老店降价老店原价新店开业 (-10,-5) (10,10) 新店不开 (0,5) (0,30) ( 新店, 老店 ) 老店降价老店原价经济不景气 ( 单位 : 万元 ) 新店开业 (-16,-11) (4,4) 新店不开 (0,-1) (0,24)

33 干洗店博弈 : 信息 ( 新店, 老店 ) 老店降价老店原价新店开业 (-10,-5) (10,10) 新店不开 (0,5) (0,30) 经济景气 ( 单位 : 万元 ) ( 新店, 老店 ) 老店降价老店原价新店开业 (-16,-11) (4,4) 新店不开 (0,-1) (0,24) 经济不景气 ( 单位 : 万元 ) 信息集 : 不同时刻, 参与人对不同变量取值的了解例如 : 老店知道新店一定开业的信息 ; 或两个店都知道经济景不景气, 或只有一个知道景不景气

34 干洗店博弈 : 博弈顺序新店老店自然三个参与人的博弈顺序 : 与信息集有关 1. 若两店均不知道经济景气不景气, 则博弈顺序为 : 新店 ( 开, 不开 ) 老店 ( 降价, 不降价 ) 自然 { 景气不景气 } 2. 若两店都知道经济景不景气, 则博弈顺序 : 自然 { 景气不景气 } 新店 ( 开, 不开 ) 老店 ( 降价, 不降价 ) 3. 若老店知道景不景气, 新店不知道, 则博弈顺序 : 新店 ( 开, 不开 ) 自然 { 景气不景气 } 老店 ( 降价, 不降价 )

35 博弈论是对策论, 而不是决策论若信息是两店均不知经济情况新干洗店开老干洗店原价 0.5 低价 0.5 自然自然景气 0.7 不景气 0.3 景气不开 0 决策树不景气新店开业的期望支付是 : = 18 这样新店选择不开了这不是博弈论, 是决策论, 缺陷是老店决策由概率推算

36 干洗店博弈的博弈树若信息是两店均不知经济情况新干洗店不开开老干洗店老干洗店原价低价原价低价自然自然自然自然景气 0.7 景气 0.7 不景气 0.3 景气 0.7 不景气 0.3 景气 0.7 不景气 0.3 不景气 :100 40:40-100: :-110 0: 340 0: 240 0: 50 0: -10

37 博弈论专家必须将自身放在每个决策者的位置上考虑问题新店开业 : 老店若原价, 则老店利润 0.7* *40=82; 若老店降价, 则老店利润 -50* *0.3=-68; 显然老店必须选择原价 ; 新店不开 : 老店若原价, 则利润为 0.7* *240=282; 若老店降价, 则老店利润 50*0.7-10*0.3=32; 显然老店必须选原价 ; 不管新店开不开 ; 老店必须原价才能利润最大 ; 反过来, 老店原价, 则新店开的利润为 82; 不开就是 0; 新店选开店利润最大决策者视角的转换是博弈论的一个特点

38 策略 (strategy), 策略集策略是行动的组合参与人 i 的策略 s i 是 : 给定其信息集, 该策略是决定在博弈的每个时间点他选择何种行动参与人 i 的信息集包括知道其它参与人在过去的一切行动 ; 那参与人 i 的策略就是对别的参与人的行动作出反应新干洗店的策略集 ={ 开, 不开 } 老干洗店的策略集 ={ 若新店开则原价 ; 若新店开则降价 ; 不论新店开不开都原价 ; 不论新店开不开都降价 }

39 均衡 (equilibrium) 均衡 S*={S 1,S 2,,S n } 是指由博弈中的 n 个参与人每人选取的最佳策略所形成的一个策略组合均衡策略是参与人在最大化各自支付所选的策略新干洗店的均衡策略 : 开店老干洗店的均衡策略 : 不论新店开不开都原价均衡不一定唯一或者根本没有均衡 ; 没有均衡或多重均衡往往是由于建模的设定不足, 不能对将要发生什么作出全面准确的预测

untitled

untitled 2 3 4 Microeconomics aims to model economic activity as an interaction of individual economic agents pursuing their private interests ---M-W-G (1995) Game theory strategic interaction 5 2/3 n 0-100 x i