博弈论 Game Theory Game Theory--Chapter 1

教材 Gibbons, Robert, Game Theory for Applied Economists, Princeton University Press, 1992. 中文版，博弈论基础， 中国社会科学出版社, 1999。 Game Theory--Chapter 1

参考书 1.张维迎，博弈论与信息经济学，三联书店上海分店和上海人民出版社，2004。 2.谢识予，经济博弈论，复旦大学出版社，2010. 3. A.迪克西特和S.斯克斯，策略博弈，中国人民大学出版社，2009. Game Theory--Chapter 1

参考书 4. P. K.杜塔, 策略与博弈：理论及实践与上海财经大学出版社,2005. 5. [美]朱•弗登博格，[法]让•梯若尔(Jean Tirole) 博弈论。中国人民大学出版社，2010。 6. [美]拉斯穆森，博弈与信息：博弈论概论（第四版），中国人民大学出版社，2009。 Game Theory--Chapter 1

考核要求 期末考试（60％）：闭卷 期中考试（20%）：开卷 考勤和作业（20％） 试题范围：讲授内容及其实际应用问题 Game Theory--Chapter 1

教学日历 第１章 完全信息静态博弈(8class) 第２章 完全信息动态博弈(12class) Game Theory--Chapter 1

教学日历 第3章 非完全信息静态博弈(8class) 第４章 非完全信息动态博弈(12class) 复习考试 Game Theory--Chapter 1

教学语言 教材：英文，学生可参考推荐的中文教材。 讲义：中文 考试：中文试题 Game Theory--Chapter 1

前言（Preface） 0.1 博弈定义 0.2 博弈的分类 0.3 博弈论(GameTheory,对策论) Game Theory--Chapter 1

0.1博弈定义 博弈即两个（些）人、团队（组织），面对一定的环境条件，在一定的规则下，同时或先后，一次或多次，从各自允许选择的行为或策略中进行选择并加以实施，各自取得相应结果的过程。 Game Theory--Chapter 1

博弈中的四要素 1、参与人（Players） 2、策略（Strategies） 3、博弈次序（Orders） 参与者是博弈中独立决策、独立承担博弈结果的个人或组织 2、策略（Strategies） 策略是博弈中各参与者的决策内容或计划. 3、博弈次序（Orders） 参与者做出策略选择的顺序 4、收益或支付（payoffs） 参与者通过博弈获得的利益，是其根本目标 Game Theory--Chapter 1

0.2 博弈的分类 . 行动顺序 信息 静态 动态 完全信息 完全信息静态博弈 纳什均衡 纳什（1950，1951） 完全信息动态博弈 0.2 博弈的分类 行动顺序 信息 静态 动态 完全信息 完全信息静态博弈 纳什均衡 纳什（1950，1951） 完全信息动态博弈 子博弈精炼纳什均衡 泽尔腾（1965） 不完全信息 不完全信息静态博弈 贝叶斯纳什均衡 海萨尼（1967-1968） 不完全信息动态博弈 精炼贝叶斯纳什均衡 泽尔腾（1975） Kreps和Wilson（1982） Fudenberg和Tirole（1991） . Game Theory--Chapter 1

0.3 博弈论 博弈论就是系统研究各种博弈问题中各博弈方具有充分或者有限理性、能力的条件下，合理的策略选择和合理选择策略时博弈的结果，并分析这些结果的经济意义、效率意义的理论和方法。 通俗的说，即博弈方如何获得最佳结果。 Game Theory--Chapter 1

博弈论: 博弈论是研究人们在利益相互影响的格局 中的策略选择问题、是研究多人决策问 题的理论。 而策略选择是人们经济行为的核心内容． 　中的策略选择问题、是研究多人决策问　　　题的理论。 　而策略选择是人们经济行为的核心内容． 　此外，经济学和博弈论的研究模式是一样的：即强调个人理性，也就是在给定的约束条件下追求效用最大化。可见，经济学和博弈论具有内在的联系。在经济学和博弈论具有的这种天然联系的基础上产生了经济博弈论。 Game Theory--Chapter 1

博弈论的产生和发展 将博弈的思想明确地应用于经济领域，始于古诺（Cournot,1838）、伯特兰德(伯川德)（Bertrand,1883）和艾奇沃斯(Edgeworth,1925）等人关于两寡头的产量和价格垄断、产品交易行为的研究，他们通过对不同的经济行为方式和案例建立了相应的博弈论模型，为经济博弈论的发展提供了思想雏形和有益尝试。近半个多世纪以来，博弈论引起了众多经济学家的极大兴趣，使得博弈论在经济学中的应用模型越来越多。大约从20世纪80年代开始，博弈论逐渐成为主流经济学的一部分，甚至可以说成为微观经济学的基础。 Game Theory--Chapter 1

博弈论的产生和发展 《The theory of Games and Economic Behaviour》 冯·诺依曼和摩根斯坦（Von.neumann and morgenstern） （冯 ·诺依曼是20世纪伟大的数学家之一， 　摩根斯坦是美国当代杰出经济学家。） 　合作完成了： 《The theory of Games and Economic Behaviour》 Game Theory--Chapter 1

博弈论的产生和发展 冯·诺依曼（Von Neumann），摩根斯坦（Morgenstern）（1944），博弈论和经济行为（The Theory of Games and Economic Behavior）。标志着博弈理论的初步形成 Nash（1950，1951）两篇关于非合作博弈的重要文章，在非常一般的意义下。定义了非合作博弈及其均衡解，并证明了均衡解的存在。基本上奠定了现代非合作博弈论的基石。 Game Theory--Chapter 1

值得人们尊敬的人 因对博弈论研究作出杰出贡献而获诺贝尔经济 学奖的经济学家： ●纳什(Nash): Nash-Equilibrium 约翰·纳什, 1928年生于美国 1994年Nobel 经济学奖得主 在非合作博弈的均衡分析 理论方面做出了开创性的 贡献，对博弈论和经济学 产生了重大影响 。 Game Theory--Chapter 1

值得人们尊敬的人 泽尔藤(Selten):Subgame-Perfect Nash E--- 莱因哈德·泽尔腾，1930年生于德国 1994年Nobel 经济学奖得主 在非合作博弈的均衡分析理论方面做出了开创性的贡献，对博弈论和经济学产生了重大影响 。 Game Theory--Chapter 1

值得人们尊敬的人 海萨尼(Harsanyi) : Bayes-Nash Equilibrium 约翰·海萨尼，1920年生于美国 1994年Nobel 经济学奖得主 在非合作博弈的均衡分析理论 方面做出了开创性的贡献，对 博弈论和经济学产生了重大影响 。 Game Theory--Chapter 1

值得人们尊敬的人 莫里斯 1996获奖 詹姆斯·莫里斯 1936年生于英国 在信息经济学理论领域做出了重大贡献， 莫里斯 1996获奖 詹姆斯·莫里斯 1936年生于英国 在信息经济学理论领域做出了重大贡献， 尤其是不对称信息条件下的经济激励理论 Game Theory--Chapter 1

值得人们尊敬的人 威廉·维克瑞1914-1996，生于美国,1996获奖 在信息经济学、激励理论、 博弈论等方面都做出了重大贡献 Game Theory--Chapter 1

值得人们尊敬的人 迈克尔·斯宾斯(Spence)2001获奖 斯宾斯（A. Michael Spence ）生于1943年， 美国加州斯坦福大学教授 为不对称信息市场的一般理论奠定了基石。 他们的理论迅速得到了应用，从传统的农业 市场到现代的金融市场。他们的贡献来自于 现代信息经济学的核心部分...... Game Theory--Chapter 1

值得人们尊敬的人 阿克洛夫（George A. Akerlof ）生于1940年，美国加州大学伯克莱分校教授 2001获奖 为不对称信息市场的一般理论奠定了基石。 他们的理论迅速得到了应用，从传统的农业 市场到现代的金融市场。他们的贡献来自于 现代信息经济学的核心部分...... Game Theory--Chapter 1

值得人们尊敬的人 斯蒂格利兹（Joseph E. Stiglitz ）生于1943年，美国纽约哥伦比亚大学教授 2001获奖 为不对称信息市场的一般理论奠定了基石。 他们的理论迅速得到了应用，从传统的农业 市场到现代的金融市场。他们的贡献来自于 现代信息经济学的核心部分...... Game Theory--Chapter 1

值得人们尊敬的人 罗伯特·奥曼 （Robert J. Aumann） 1930年6月出生于德国的法兰克福，拥有以色列和美国双重国籍 。 2005获奖 通过博弈论分析，促进了 人们对冲突和合作的理解 Game Theory--Chapter 1

值得人们尊敬的人 托马斯·谢林（Thomas C. Schelling） 1921年出生于美国加利福尼亚州的奥克兰市。 2005获奖 通过博弈论分析，促进了 人们对冲突和合作的理解 Game Theory--Chapter 1

值得人们尊敬的人 赫维奇 1917年出生于俄罗斯莫斯科，后加入美国国籍，目前为美国明尼苏达大学经济学荣誉教授 2007获奖 创立和发展了“机制设计理论” 。 这一理论有助于经济学家、 各国政府和企业识别在哪些情况 下市场机制有效，哪些情况下市 场机制无效。此外，借助“机制 设计理论”，人们还可以确定最 佳和最有效的资源分配方式。 Game Theory--Chapter 1

值得人们尊敬的人 马斯金1950年出生于美国纽约，现任美国普林斯顿进修学院教授 2007获奖 创立和发展了“机制设计理论” 。 这一理论有助于经济学家、 各国政府和企业识别在哪些情况 下市场机制有效，哪些情况下市 场机制无效。此外，借助“机制 设计理论”，人们还可以确定最 佳和最有效的资源分配方式。 Game Theory--Chapter 1

值得人们尊敬的人 迈尔森1951年出生在美国波士顿，现任美国芝加哥大学教授 2007获奖 创立和发展了“机制设计理论” 。 这一理论有助于经济学家、 各国政府和企业识别在哪些情况 下市场机制有效，哪些情况下市 场机制无效。此外，借助“机制 设计理论”，人们还可以确定最 佳和最有效的资源分配方式。 Game Theory--Chapter 1

Static Games of Complete Information-Chapter 1 Lecture 1 May 19, 2003 Static Games of Complete Information-Chapter 1 Nash Equilibrium

Outline of Static Games of Complete Information Introduction to games Normal-form (or strategic-form) representation Iterated elimination of strictly dominated strategies Nash equilibrium Review of concave functions, optimization Applications of Nash equilibrium Mixed strategy Nash equilibrium Game Theory--Chapter 1

What is game theory? 我们聚焦于博弈: 实例:六个人去饭馆. 有至少两个理性的参与人 每个参与人的选择超过一种 策略外部性: 存在策略互动 结果取决于所有参与人所选择的策略; 实例:六个人去饭馆. 每个人为自己的饭付费– 一个简单的决策问题 吃饭前，每个人都同意他们之间平分账单– a game Game Theory--Chapter 1

What is game theory? 博弈论是分析一群理性的参与人（或代理人）之间的策略互动的标准方法 博弈论的应用 经济学 政治学 社会学 法学 生物学 Game Theory--Chapter 1

Classic Example : Prisoners’ Dilemma 两名犯罪嫌疑人被捕并受到指控，他们被关入不同的牢室。但是警方并无充足证据. 两名犯罪嫌疑人被告知以下政策: 如果两人都不坦白，将均被判为轻度犯罪，入狱一个月. 如果双方都坦白，都将被判入狱六个月. 如果一人招认而另一人拒不坦白，招认的一方将马上获释，而另一人将判入狱九个月. Prisoner 1 Prisoner 2 Confess Mum -1 , -1 -9 , 0 0 , -9 -6 , -6 Game Theory--Chapter 1

Example : The battle of the sexes 在分开的工作场所，Chris 和Pat 必须决定晚上是看歌剧还是去看拳击. Chris 和 Pat 都知道以下信息: 两个人都愿意在一起度过这个夜晚. 但是Chris更喜欢歌剧. Pat则更喜欢拳击. Chris Pat Prize Fight Opera 2 , 1 0 , 0 1 , 2 Game Theory--Chapter 1

Example : Matching pennies 两个参与人都有一枚硬币. 两个参与人必须同时选择是Head朝上还是Tail朝上. 两个参与人都知道以下规则: 如果两枚硬币配对 (both heads or both tails) ，那么参与人2将赢得参与人1的硬币. 否则, 参与人1会赢得参与人2的硬币. Player 1 Player 2 Tail Head -1 , 1 1 , -1 Game Theory--Chapter 1

Static (or simultaneous-move) games of complete information 一个静态（或同时行动）博弈包括的要素: 一个参与人集合（至少两个参与人） 每个参与人都有一个策略集/行动集 每个参与人针对策略组合，或者说对他所偏好的策略组合所获得的收益 {Player 1, Player 2, ... Player n} S1 S2 ... Sn ui(s1, s2, ...sn), for all s1S1, s2S2, ... snSn. Game Theory--Chapter 1

Static (or simultaneous-move) games of complete information 每个参与人在选择他/她的策略时不知道其他参与人的选择. 完全信息（Complete information） 每个参与人的策略和收益函数都是所有参与人的共同知识（common knowledge ）. 对参与人的假设 理性（Rationality） 参与人的目的是使他的收益最大化 参与人是完美的计算者 每个参与人都知道其他参与人是理性的 Game Theory--Chapter 1

Static (or simultaneous-move) games of complete information 参与人是否合作? 不.我们仅仅考虑非合作博弈 （non-cooperative games ） 时间顺序 每个参与人 i 在不知道其他人的选择的情况下选择他/她的策略si. 然后每个参与人 i 得到他/她的收益 ui(s1, s2, ..., sn). 博弈结束. Game Theory--Chapter 1

Definition: normal-form or strategic-form representation 参与人的策略空间S1 S2 ... Sn 和 他们的收益函数u1 u2 ... un 其中， ui : S1 × S2 × ...× Sn→R. 我们把这个博弈表示为 Game Theory--Chapter 1

Normal-form representation: 2-player game 双变量矩阵表述 2个参与人: Player 1 和 Player 2 每个参与人有有限数量的策略 例如: S1={s11, s12, s13} S2={s21, s22} Player 2 s21 s22 Player 1 s11 u1(s11,s21), u2(s11,s21) u1(s11,s22), u2(s11,s22) s12 u1(s12,s21), u2(s12,s21) u1(s12,s22), u2(s12,s22) s13 u1(s13,s21), u2(s13,s21) u1(s13,s22), u2(s13,s22) Game Theory--Chapter 1

Classic example: Prisoners’ Dilemma: normal-form representation 参与人集合: {Prisoner 1, Prisoner 2} 策略集: S1 = S2 = {Mum, Confess} 收益函数: u1(M, M)=-1, u1(M, C)=-9, u1(C, M)=0, u1(C, C)=-6; u2(M, M)=-1, u2(M, C)=0, u2(C, M)=-9, u2(C, C)=-6 Players Prisoner 1 Prisoner 2 Strategies Confess Mum -1 , -1 -9 , 0 0 , -9 -6 , -6 Payoffs Game Theory--Chapter 1

Example: The battle of the sexes Chris Pat Prize Fight Opera 2 , 1 0 , 0 1 , 2 标准式（或策略式）表述: 参与人集合: { Chris, Pat } (={Player 1, Player 2}) 策略集: S1 = S2 = { Opera, Prize Fight} 收益函数: u1(O, O)=2, u1(O, F)=0, u1(F, O)=0, u1(F, F)=1; u2(O, O)=1, u2(O, F)=0, u2(F, O)=0, u2(F, F)=2 Game Theory--Chapter 1

Example: Matching pennies Player 1 Player 2 Tail Head -1 , 1 1 , -1 标准式（或策略式）表述: 参与人集合: {Player 1, Player 2} 策略集: S1 = S2 = { Head, Tail } 收益函数: u1(H, H)=-1, u1(H, T)=1, u1(T, H)=1, u1(T, T)=-1; u2(H, H)=1, u2(H, T)=-1, u2(T, H)=-1, u2(T, T)=1 Game Theory--Chapter 1

Example: Tourists & Natives 城市里仅有两家酒吧 (bar 1, bar 2) 可以索取的价格为$2, $4, or $5 6000名游客随机挑选酒吧 4000个当地人挑选价格最低的酒吧 例1: 两家酒吧都索取$2 每家酒吧得到5,000名顾客和 $10,000 例2: Bar 1 索取 $4, Bar 2 索取 $5 Bar 1 得到3000+4000=7,000名顾客和 $28,000 Bar 2 得到3000名顾客和 $15,000 Game Theory--Chapter 1

Example: Cournot model of duopoly 一种同质的（ homogeneous ）产品仅仅由两家企业进行生产: firm 1 和 firm 2. 产量分别用q1 和q2表示. 每家企业选择产量时并不知道其他企业的选择. 市场价格是 P(Q)=a-Q, 其中Q=q1+q2. firm i 生产产量qi 的成本是Ci(qi)=cqi. 标准式表述: 参与人集合: { Firm 1, Firm 2} 策略集: S1=[0, +∞), S2=[0, +∞) 收益函数: u1(q1, q2)=q1(a-(q1+q2)-c), u2(q1, q2)=q2(a-(q1+q2)-c) Game Theory--Chapter 1

One More Example n 个参与人同时选择0到100 之间的一个数字. xi 表示player i 选择的数字. Player i的收益 = xi – 3y/5 标准式表述: Game Theory--Chapter 1

Solving Prisoners’ Dilemma 无论其他参与人怎样选择，坦白都是更好的策略 劣势策略（Dominated strategy） 无论其他参与人怎样选择，都存在比这个策略更好的其他策略 Players Prisoner 1 Prisoner 2 Strategies Confess Mum -1 , -1 -9 , 0 0 , -9 -6 , -6 Payoffs Game Theory--Chapter 1

Definition: strictly dominated strategy si” is strictly better than si’ regardless of other players’ choices Prisoner 1 Prisoner 2 Confess Mum -1 , -1 -9 , 0 0 , -9 -6 , -6 Game Theory--Chapter 1

Example 两家企业, Reynolds和Philip, 分享市场 如果两家企业都不做广告，则每个企业会从各自顾客那里获得$60百万 每个企业的广告成本是$20 百万 如果做广告则会从竞争对手那里获得$30 百万 Philip No Ad Ad Reynolds 60 , 60 30 , 70 70 , 30 40 , 40 Game Theory--Chapter 1

2-player game with finite strategies S1={s11, s12, s13} S2={s21, s22} s11 is strictly dominated by s12 if u1(s11,s21)<u1(s12,s21) and u1(s11,s22)<u1(s12,s22). s21 is strictly dominated by s22 if u2(s1i,s21) < u2(s1i,s22), for i = 1, 2, 3 Player 2 s21 s22 Player 1 s11 u1(s11,s21), u2(s11,s21) u1(s11,s22), u2(s11,s22) s12 u1(s12,s21), u2(s12,s21) u1(s12,s22), u2(s12,s22) s13 u1(s13,s21), u2(s13,s21) u1(s13,s22), u2(s13,s22) Game Theory--Chapter 1

Definition: weakly dominated strategy si” is at least as good as si’ regardless of other players’ choices Player 1 Player 2 R U B L 1 , 1 2 , 0 0 , 2 2 , 2 Game Theory--Chapter 1

Strictly and weakly dominated strategy 一个理性的参与人肯定不会选择严格劣势策略.所以，任何严格劣势策略都可以被剔除. 一个理性的参与人有可能选择一个弱劣势策略. 剔除的顺序对严格优势策略来说无关紧要，但是对弱优势策略来说就很重要了. 剔除掉顺序可以是（B,R,C,M）和（C,M,L,B），结果分别是（T,L）和（T,R） Player 2 L C R Player 1 T 2 , 12 1 , 10 1 , 12 M 0 , 12 0 , 11 B 0 , 10 0 , 13 Game Theory--Chapter 1

Iterated elimination of strictly dominated strategies 如果一个策略是严格劣势的，那么剔除它 博弈的规模和复杂程度减少（reduced）了 在这个简化后的博弈中剔除任何严格劣势策略 继续不断的这样做 得到理性化的均衡（Rationalizable equilibrium） Game Theory--Chapter 1

Iterated elimination of strictly dominated strategies: an example Player 2 Left Middle Right Up 1 , 0 1 , 2 0 , 1 0 , 3 2 , 0 Player 1 Down Player 1 Player 2 Middle Up Down Left 1 , 0 1 , 2 0 , 3 0 , 1 Game Theory--Chapter 1

Example: Tourists & Natives 城市里仅有两家酒吧 (bar 1, bar 2) 可以索取的价格为$2, $4, or $5 6000名游客随机挑选酒吧 4000个当地人挑选价格最低的酒吧 例1: 两家酒吧都索取$2 每家酒吧得到5,000名顾客和 $10,000 例2: Bar 1 索取 $4, Bar 2 索取 $5 Bar 1 得到3000+4000=7,000名顾客和 $28,000 Bar 2 得到3000名顾客和 $15,000 Game Theory--Chapter 1

Example: Tourists & Natives Bar 2 $2 $4 $5 Bar 1 10 , 10 14 , 12 14 , 15 12 , 14 20 , 20 28 , 15 15 , 14 15 , 28 25 , 25 Payoffs are in thousands of dollars Bar 2 $4 $5 Bar 1 20 , 20 28 , 15 15 , 28 25 , 25 Game Theory--Chapter 1

One More Example n 个参与人同时选择0到100 之间的一个数字. xi 表示player i 选择的数字. Player i的收益 = xi – 3y/5 Game Theory--Chapter 1

One More Example 标准式表述: 存在劣势策略吗? 应该选哪些数字? 参与人: {player 1, player 2, ..., player n} 策略: Si =[0, 100], for i = 1, 2, ..., n. 收益函数: ui(x1, x2, ..., xn) = xi – 3y/5 存在劣势策略吗? 应该选哪些数字? 如果ui(x1, x2, ..., xn) = xi – 6y/5，会怎么样？ Game Theory--Chapter 1

New solution concept: Nash equilibrium Player 2 L C R Player 1 T 0 , 4 4 , 0 5 , 3 M B 3 , 5 6 , 6 策略组合(B, R) 有以下性质: 如果player 2选R ，那么除B以外，Player 1不可能有更好的策略选择. 如果player 1选B，那么除 R以外， Player 2不可能有更好的策略选择. Game Theory--Chapter 1

New solution concept: Nash equilibrium Player 2 L’ C’ R’ Player 1 T’ 0 , 4 4 , 0 3 , 3 M’ B’ 3.5 , 3.6 策略组合 (B’, R’) 有以下性质: 如果player 2选R’ ，那么除B’以外，Player 1不可能有更好的策略选择. 如果player 1选B’，那么除 R’以外， Player 2不可能有更好的策略选择. Game Theory--Chapter 1

Nash Equilibrium: idea 纳什均衡 是一个策略集。其中，每个参与人选择的策略都是针对其他参与人选择策略的最优反应 Game Theory--Chapter 1

Definition: Nash Equilibrium Given others’ choices, player i cannot be better-off if she deviates from si* (cf: dominated strategy) Prisoner 2 Mum Confess Prisoner1 -1 , -1 -9 , 0 0 , -9 -6 , -6 Game Theory--Chapter 1

2-player game with finite strategies S1={s11, s12, s13} S2={s21, s22} (s11, s21)is a Nash equilibrium if u1(s11,s21)  u1(s12,s21), u1(s11,s21)  u1(s13,s21) and u2(s11,s21)  u2(s11,s22). Player 2 s21 s22 Player 1 s11 u1(s11,s21), u2(s11,s21) u1(s11,s22), u2(s11,s22) s12 u1(s12,s21), u2(s12,s21) u1(s12,s22), u2(s12,s22) s13 u1(s13,s21), u2(s13,s21) u1(s13,s22), u2(s13,s22) Game Theory--Chapter 1

Finding a Nash equilibrium: cell-by-cell inspection Player 2 Left Middle Right Up 1 , 0 1 , 2 0 , 1 0 , 3 2 , 0 Player 1 Down Player 1 Player 2 Middle Up Down Left 1 , 0 1 , 2 0 , 3 0 , 1 Game Theory--Chapter 1

Example: Tourists & Natives Bar 2 $2 $4 $5 Bar 1 10 , 10 14 , 12 14 , 15 12 , 14 20 , 20 28 , 15 15 , 14 15 , 28 25 , 25 Payoffs are in thousands of dollars Bar 2 $4 $5 Bar 1 20 , 20 28 , 15 15 , 28 25 , 25 Game Theory--Chapter 1

One More Example 标准式表述: 哪个策略集是纳什均衡? 参与人: {player 1, player 2, ..., player n} 策略: Si =[0, 100], for i = 1, 2, ..., n. 收益函数: ui(x1, x2, ..., xn) = xi – 3y/5 哪个策略集是纳什均衡? Game Theory--Chapter 1

Best response function: example Player 2 L’ C’ R’ Player 1 T’ 0 , 4 4 , 0 3 , 3 M’ B’ 3.5 , 3.6 如果Player 2 选L’ ，那么Player 1的最优策略是M’ 如果Player 2 选C’ ，那么Player 1的最优策略是T’ 如果Player 2 选R’ ，那么Player 1的最优策略是 B’ 如果Player 1 选B’ ，那么Player 2的最优策略是 R’ 最优反应: 给定其他所有参与人的策略，一个参与人能够选择的最优策略 Game Theory--Chapter 1

Example: Tourists & Natives Bar 2 $2 $4 $5 Bar 1 10 , 10 14 , 12 14 , 15 12 , 14 20 , 20 28 , 15 15 , 14 15 , 28 25 , 25 Payoffs are in thousands of dollars 针对Bar 2选择的$2, $4 或$5的策略， Bar 1的最优反应分别是什么? 针对Bar 1选择的$2, $4 或$5的策略， Bar 2的最优反应分别是什么? Game Theory--Chapter 1

2-player game with finite strategies S1={s11, s12, s13} S2={s21, s22} 如果 u1(s11,s21)  u1(s12,s21) 且 u1(s11,s21)  u1(s13,s21). 那么Player 1的策略 s11 是她对Player 2策略s21的最优反应， Player 2 s21 s22 Player 1 s11 u1(s11,s21), u2(s11,s21) u1(s11,s22), u2(s11,s22) s12 u1(s12,s21), u2(s12,s21) u1(s12,s22), u2(s12,s22) s13 u1(s13,s21), u2(s13,s21) u1(s13,s22), u2(s13,s22) Game Theory--Chapter 1

Using best response function to find Nash equilibrium 在2名参与人的博弈中,当且仅当（i）player 1的策略s1是对player 2的策略s2的最优反应， （ii）player 2的策略s2 是对player 1的策略s1的最优反应时，( s1, s2 ) 是一个纳什均衡. Prisoner 1 Prisoner 2 Confess Mum -1 , -1 -9 , 0 0 , -9 -6 , -6 Game Theory--Chapter 1

Using best response function to find Nash equilibrium: example Player 2 L’ C’ R’ Player 1 T’ 0 , 4 4 , 0 3 , 3 M’ B’ 3.5 , 3.6 M’ 是 Player 1对Player 2的策略 L’ 的最优反应 T’是 Player 1对Player 2的策略 C’ 的最优反应 B’是 Player 1对Player 2的策略 R’ 的最优反应 L’ 是Player 2对Player 1的策略T’的最优反应 C’是Player 2对Player 1的策略M’的最优反应 R’是Player 2对Player 1的策略B’ 的最优反应 Game Theory--Chapter 1

Example: Tourists & Natives Bar 2 $2 $4 $5 Bar 1 10 , 10 14 , 12 14 , 15 12 , 14 20 , 20 28 , 15 15 , 14 15 , 28 25 , 25 Payoffs are in thousands of dollars 使用最优反应函数找到纳什均衡. Game Theory--Chapter 1

Example: The battle of the sexes Chris Pat Prize Fight Opera 2 , 1 0 , 0 1 , 2 Opera是Player 1对Player 2的策略Opera的最优反应 Opera是Player 2对Player 1的策略Opera的最优反应 所以, (Opera, Opera) 是一个纳什均衡 Fight是Player 1对Player 2的策略Fight的最优反应 Fight是Player 2对Player 1的策略Fight的最优反应 所以, (Fight, Fight)是一个纳什均衡 Game Theory--Chapter 1

Example: Matching pennies Player 1 Player 2 Tail Head -1 , 1 1 , -1 Head是Player 1对Player 2的策略Tail的最优反应 Head是Player 2对Player 1的策略Head 的最优反应 Tail是Player 1对Player 2的策略Head 的最优反应 Tail是Player 2对Player 1的策略Tail的最优反应 所以, 没有纯策略纳什均衡 Game Theory--Chapter 1

Definition: best response function Given the strategies chosen by other players Player i’s best response Game Theory--Chapter 1

Definition: best response function Player i’s best response to other players’ strategies is an optimal solution to Game Theory--Chapter 1

Using best response function to define Nash equilibrium A set of strategies, one for each player, such that each player’s strategy is best for her, given that all other players are playing their strategies, or A stable situation that no player would like to deviate if others stick to it Game Theory--Chapter 1

Strictly dominated strategies vs. Nash Equilibrium 纳什均衡和重复剔除严格劣势策略之间的关系 纳什均衡是一个比重复剔除严格劣势策略更强的解的概念. 可预测性（Predictability） 存在性（Existence） 惟一性（uniqueness）. 如果博弈存在惟一解，它一定是一个纳什均衡 Game Theory--Chapter 1

Summary(Appendix 1.1.C) 命题A 在n个参与人的标准式博弈G={S1, ...,Sn;u1, ...un}中，如果重复剔除严格劣势策略剔除掉除策略组合( s1*, s2*, ..., sn*)外的所有策略,那么这一策略组合为该博弈惟一的纳什均衡. 命题B 在n个参与人的标准式博弈G={S1, ...,Sn;u1, ...un}中，如果策略 ( s1*, s2*, ..., sn*) 是一个纳什均衡，那么它不会被重复剔除严格劣势策略所剔除. 但是未被重复剔除严格劣势策略所剔除的策略不一定是纳什均衡策略. Game Theory--Chapter 1

1.2. Application 1.2 A. Cournot双头垄断模型 1.2 B. Bertrand双头垄断模型 Game Theory--Chapter 1

1.2 Application 我们将通过模型说明: (a) 把对一个问题的非正式描述转化为一个博弈的标准式表述; (b) 用最优反应函数求解博弈的纳什均衡的计算过程; (c) 用重复剔除严格劣势策略求解博弈的纳什均衡的计算过程. Game Theory--Chapter 1

Contributing to a public good 两个人: person 1 和 person 2. person 1 财富为 w1 ，person 2 财富为 w2, 每个人选择捐献多少时不知道其他人的选择. 捐献的数量分别用c1和c2表示. 公共物品的数量等于捐献的数目. Person 1的收益: u1(c1, c2) = v1(c1 + c2) + w1 – c1 Person 2的收益: u2(c1, c2) = v2(c1 + c2) + w2 – c2 v1(c1 + c2) 和 v2(c1 + c2) 都是凹函数 Game Theory--Chapter 1

Cournot model of duopoly 一种产品仅由两家企业生产: firm 1 和 firm 2. 它们的产量分别用 q1 和 q2 表示. 每家企业选择产量时都不知道其他企业的选择. 市场价格是 P(Q) = a - Q, 其中a 是常数且Q = q1 + q2. firm i 生产产量 qi 的成本是Ci(qi) = cqi. Game Theory--Chapter 1

Cournot model of duopoly 标准式表述: 参与人集合: { Firm 1, Firm 2} 策略集: S1= [0, +∞), S2= [0, +∞) 收益函数: u1(q1, q2) = q1(a - (q1 + q2) - c) u2(q1, q2) = q2(a - (q1 + q2) - c) Game Theory--Chapter 1

Cournot model of duopoly 如何找到纳什均衡 在2名参与人的博弈中,当且仅当 （i）player 1的策略s1是对player 2的策略s2的最优反应， （ii）且player 2的策略s2 是对player 1的策略s1的最优反应时， 策略组合( s1, s2 ) 是一个纳什均衡。 Game Theory--Chapter 1

Cournot model of duopoly 如何找到纳什均衡 找到产量组合 (q1*, q2*) ，其中 q1*是firm 1对firm 2的产量 q2* 的最优反应； q2*是firm 2对firm 1的产量 q1* 的最优反应。 即, q1* 是下面问题的解 Max u1(q1, q2*)=q1(a - (q1 + q2*) - c) subject to 0  q1  +∞ 同时 q2*是下面问题的解 Max u2(q1*, q2)=q2(a - (q1* + q2) - c) subject to 0  q2  +∞ Game Theory--Chapter 1

Cournot model of duopoly 如何找到纳什均衡 解 Max u1(q1, q2*) = q1(a - (q1 + q2*) - c) st 0  q1  +∞ FOC: a - 2q1 - q2*- c = 0 q1 = (a - q2*- c)/2, if q2*< a - c Game Theory--Chapter 1

Cournot model of duopoly 如何找到纳什均衡 解 Max u2(q1*, q2) = q2(a - (q1* + q2) - c) st 0  q2  +∞ FOC: a - 2q2 – q1* – c = 0 q2 = (a – q1* – c)/2, if q1*< a - c Game Theory--Chapter 1

Cournot model of duopoly 如何找到纳什均衡 如果 q1* = (a – q2* – c)/2 q2* = (a – q1* – c)/2 那么产量组合 (q1*, q2*) 是一个纳什均衡 解这两个方程得到 q1* = q2* = (a – c)/3 Game Theory--Chapter 1

Cournot model of duopoly 最优反应函数 firm 1对firm 2的产量q2的最优反应函数 : R1(q2) = (a – q2 – c)/2, if q2 < a– c; 0, otherwise firm 2对firm 1的产量q1的最优反应函数: R2(q1) = (a – q1 – c)/2, if q1 < a– c; q2 Nash equilibrium a – c (a – c)/2 (a – c)/2 a – c q1 Game Theory--Chapter 1

Cournot model of duopoly 思考： 当只有一家企业是市场的垄断者时，它会选择垄断产量qm使自己的利润um(qm,0)最大化 解 Max um(qm,0) = qm(a – qm - c) st 0  qm +∞ FOC: a - 2qm– c = 0 => qm = (a – c)/2 Game Theory--Chapter 1

Cournot model of duopoly 在市场上有两家企业的情况下，要使两企业总的利润最大化，两企业的产量之和 q1 + q2 等于垄断产量 qm ，比如q1 = q2 = qm/2 = (a – c)/4就可满足这一条件。但为什么这不是一个纳什均衡解? 考虑每家企业是否具有偏离这一产量qm/2的动机？ 在较低的垄断产量下，相应的市场价格较高，每家企业都倾向于提高产量，而不顾产量的增加会降低市场出清价格。 Game Theory--Chapter 1

Cournot model of duopoly 重复剔除严格劣战略 根据前面的分析，对任意 x > 0，垄断产量qm = (a – c)/2严格优于其它任何更高的产量 证明： ui(qm, qj) = [(a – c)/2][(a – c)/2 - qj] ui(qm+ x, qj) = [(a – c)/2 + x][(a – c)/2 - x - qj] = ui(qm, qj) – x(x + qj) < ui(qm, qj) 对 qj ≥ 0 成立 Game Theory--Chapter 1

Cournot model of duopoly 重复剔除严格劣战略 产量(a – c)/4严格优于任何更低的产量 证明： ui((a – c)/4, qj) = [(a – c)/4][3(a – c)/4 - qj] ui((a – c)/4 - x, qj) = [(a – c)/4 - x][3(a – c)/4 + x - qj] = ui((a – c)/4, qj) – x[(a – c)/2 + x - qj] < ui((a – c)/4, qj) 对 qj ∈ [0, (a – c)/2] 成立 重复上述过程可以把剩余战略空间限制的越来越小.到达极限时,这一区间就成为一个点qi * = (a – c)/3。 Game Theory--Chapter 1

Cournot model of oligopoly 一种产品由n 家企业生产: firm 1 ~ firm n. firm i 的产量用 qi 表示.每家企业选择产量时都不知道其他企业的选择. 市场价格是P(Q) = a - Q, 其中a是常数并且Q = q1 + q2 + ... + qn. firm i 生产产量 qi 的成本是Ci(qi) = cqi. Game Theory--Chapter 1

Cournot model of oligopoly 标准式表述: 参与人集合: { Firm 1, ... Firm n} 策略集: Si=[0, +∞), for i =1, 2, ..., n 收益函数: ui(q1 ,..., qn) = qi(a-(q1+q2 +...+qn)-c) for i =1, 2, ..., n Game Theory--Chapter 1

Cournot model of oligopoly 如何找到纳什均衡 找到产量 (q1*, ... qn*)，其中qi*是firm i 对其他企业产量的最优反应。即, q1*是下面问题的解 Max u1(q1, q2*, ..., qn*)=q1(a-(q1+q2* +...+qn*)-c) subject to 0  q1  +∞ q2*是下面问题的解 Max u2(q1*, q2 , ..., qn*)=q2(a-(q1*+q2+ ...+ qn*)-c) subject to 0  q2  +∞ q3*是....... Game Theory--Chapter 1

Cournot model of oligopoly 证明当n趋于无穷时, NE是完全竞争的结果, p=c. (提示: 借鉴对称性) ** 参见课本 PP13-17. Game Theory--Chapter 1

Bertrand model of duopoly (differentiated products) 两家企业: firm 1和firm 2. 每家企业选择它的产品的价格时不知道其他企业的选择. 价格分别用p1和p2表示. 消费者对firm 1 产品的需求量: q1(p1, p2) = a – p1 + bp2. 消费者对firm 2 产品的需求量: q2(p1, p2) = a – p2 + bp1. firm i生产数量为qi的成本是Ci(qi) = cqi. Game Theory--Chapter 1

Bertrand model of duopoly (differentiated products) 标准式表述: 参与人集合: { Firm 1, Firm 2} 策略集: S1= [0, +∞), S2= [0, +∞) 收益函数: u1(p1, p2) = (a – p1 + bp2 )(p1 – c) u2(p1, p2) = (a – p2 + bp1 )(p2 – c) Game Theory--Chapter 1

Bertrand model of duopoly (differentiated products) 如何找到纳什均衡 找到价格组合 (p1*, p2*)，其中 p1* 是firm 1对firm 2的价格p2*的最优反应； p2*是firm 2对firm 1的价格p1* 的最优反应。 即, p1* 是以下问题的解 Max u1(p1, p2*) = (a – p1 + bp2* )(p1 – c) subject to 0  p1  +∞ 且 p2*是以下问题的解 Max u2(p1*, p2) = (a – p2 + bp1* )(p2 – c) subject to 0  p2  +∞ Game Theory--Chapter 1

Bertrand model of duopoly (differentiated products) 如何找到纳什均衡 解firm 1的最大化问题 Max u1(p1, p2*) = (a – p1 + bp2* )(p1 – c) subject to 0  p1  +∞ FOC: a + c – 2p1 + bp2* = 0 p1 = (a + c + bp2*)/2 Game Theory--Chapter 1

Bertrand model of duopoly (differentiated products) 如何找到纳什均衡 解firm 2的最大化问题 Max u2(p1*, p2)=(a – p2 + bp1* )(p2 – c) subject to 0  p2  +∞ FOC: a + c – 2p2 + bp1* = 0 p2 = (a + c + bp1*)/2 Game Theory--Chapter 1

Bertrand model of duopoly (differentiated products) 如何找到纳什均衡 如果 p1* = (a + c + bp2*)/2 p2* = (a + c + bp1*)/2 那么价格组合 (p1*, p2*) 是一个纳什均衡 解这两个方程可以得到 p1* = p2* = (a + c)/(2 –b) Game Theory--Chapter 1

Bertrand model of duopoly (homogeneous products) 两家企业: firm 1 和 firm 2. 每家企业选择它的产品的价格时不知道其他企业的选择. 价格分别用p1和p2表示. 消费者对firm 1产品的需求量: q1(p1, p2) = a – p1 if p1 < p2 ; = (a – p1)/2 if p1 = p2 ; = 0, if p1 > p2 . 消费者对firm 2产品的需求量: q2(p1, p2) = a – p2 if p2 < p1 ; = (a – p2)/2 if p1 = p2 ; = 0, ow. firm i生产数量为qi的成本是Ci(qi)=cqi. Game Theory--Chapter 1

Bertrand model of duopoly (homogeneous products) 标准式表述: 参与人集合: { Firm 1, Firm 2} 策略集: S1=[0, +∞), S2=[0, +∞) 收益函数: Game Theory--Chapter 1

Bertrand model of duopoly (homogeneous products) 最优反应函数: pm =( a + c )/2 Game Theory--Chapter 1

Bertrand model of duopoly (homogeneous products) 最优反应函数: p1 p2 c pm p1 p2 c pm Firm 1’s best response to Firm 2’s p2 Firm 2’s best response to Firm 1’s p1 Game Theory--Chapter 1

Bertrand model of duopoly (homogeneous products) 最优反应函数: p1 p2 c pm Nash Equilibrium ( c, c ) Game Theory--Chapter 1

Matching pennies 所以, 不存在纳什均衡 -1 , 1 1 , -1 Player 1 Player 2 Tail Head -1 , 1 1 , -1 Head是Player 1对Player 2的策略Tail的最优反应 Tail是Player 2对Player 1的策略Tail的最优反应 Tail是Player 1对Player 2的策略Head的最优反应 Head是Player 2对Player 1的策略Head 的最优反应 所以, 不存在纳什均衡 Game Theory--Chapter 1

Contributing to a public good 两个人: person 1 和 person 2. person 1 财富为 w1 ，person 2 财富为 w2, 每个人选择捐献多少时不知道其他人的选择. 捐献的数量分别用c1和c2表示. 公共物品的数量等于捐献的数目. Person 1的收益: u1(c1, c2) = v1(c1 + c2) + w1 – c1 Person 2的收益: u2(c1, c2) = v2(c1 + c2) + w2 – c2 v1(c1 + c2) 和 v2(c1 + c2) 都是凹函数 Game Theory--Chapter 1

Contributing to a public good 标准式表述: 参与人集合: { Person 1, Person 2} 策略集: S1=[0, w1], S2=[0, w2] 收益函数: u1(c1, c2) = v1(c1 + c2) + w1 – c1 u2(c1, c2) = v2(c1 + c2) + w2 – c2 Game Theory--Chapter 1

Contributing to a public good 如何找到纳什均衡 找到捐献组合(c1*, c2*)，其中c1* 是person 1对person 2’的捐献c2* 的最优反应，而c2*是person 2对person 1的捐献c1* 的最优反应 即, c1* 是以下问题的解 Max u1(c1, c2*) = v1(c1 + c2*) + w1 – c1 subject to 0  c1  w1 而c2*是以下问题的解 Max u2(c1*, c2) = v2(c1* + c2) + w2 – c2 subject to 0  c2  w2 Game Theory--Chapter 1

Contributing to a public good 如何找到纳什均衡 解person 1的最大化问题 Max u1(c1, c2*) = v1(c1 + c2*) + w1 – c1 subject to 0  c1  w1 Game Theory--Chapter 1

Contributing to a public good 如何找到纳什均衡 解person 2的最大化问题 Max u2(c1*, c2) = v2(c1* + c2) + w2 – c2 subject to 0  c2  w2 Game Theory--Chapter 1

Contributing to a public good 如何找到纳什均衡 捐献组合 (c1*, c2*) 是一个纳什均衡，如果 Game Theory--Chapter 1

Contributing to a public good 最优反应函数 Person 1对person 2的捐献c2的最优反应函数: R1(c2) = r1 – c2 if c2 < r1; =0, if c2  r1 Person 2对person 1的捐献c1的最优反应函数: R2(c1) = r2 – c1 if c1 < r2 ; =0, if c1  r2 c2 (r1, 0) is a NE r1 Suppose that r1 > r2 The Intuition: higher valuation r2 r2 r1 c1 Game Theory--Chapter 1

公地问题 村庄里有n个农民. 每年夏天,所有村民都在村庄公共的草地上放牧. 用 gi 表示farmer i放养羊的头数. 购买和照看一只羊的成本为c, c不随一户村民拥有羊的数目多少而变化. 每只羊的价值是v(G), 其中 G = g1 + g2 + ... + gn 草地可以放牧羊的总数有一个上限. 即, v(G)>0 if G < Gmax, and v(G)=0 if G  Gmax. 假定v(G): v’(G) < 0 and v”(G) < 0. 每年春天, 所有的村民同时选择放养多少只羊. Game Theory--Chapter 1

公地问题 标准式表述: 参与人集合: { Farmer 1, ... Farmer n} 策略集: Si=[0, Gmax), for i=1, 2,..., n 收益函数: ui(g1, ..., gn)=gi v(g1 + ...+ gn) – c gi for i = 1, 2, ..., n. Game Theory--Chapter 1

公地问题 如何找到纳什均衡 找到 (g1*, g2*, ..., gn*) ，其中 gi* 是farmer i对其他村民选择的最优反应. 即, g1* 是以下问题的解 Max u1(g1, g2*, ..., gn*)= g1 v(g1 + g2* ...+ gn*) – c g1 subject to 0  g1 < Gmax 而g2*是以下问题的解 Max u2(g1*, g2 , g3*, ..., gn*)= g2v(g1*+g2+g3*+ ...+ gn*)–cg2 subject to 0  g2 < Gmax ....... Game Theory--Chapter 1

公地问题 FOCs：(g1*, g2*, ..., gn*) 是一个纳什均衡，如果 如何找到纳什均衡 gn*是以下问题的解 Max un(g1*, ..., gn-1*, gn)= gnv(g1*+...+ gn-1*+ gn)–cgn subject to 0  gn < Gmax ....... FOCs：(g1*, g2*, ..., gn*) 是一个纳什均衡，如果 Game Theory--Chapter 1

公地问题 把所有n个村民的FOC加总，再除以n，得到 Game Theory--Chapter 1

公地问题 社会问题 Game Theory--Chapter 1

公地问题 Game Theory--Chapter 1

公地问题 故事的寓意 外部性和产权 全局治理 Game Theory--Chapter 1

公地问题 公地问题的可能解决方案：（1）明确产权 一个私有化的例子：在非洲，津巴布韦、马拉维、纳米比亚和博茨瓦纳的大象数量正在增长，而这一增长源于这些国家的政府允许战利品狩猎，即将狩猎合法化。这听起来很残忍，但却从另一方面促使当地人保护野生动物。自1979年以来，津巴布韦的大象数量从3万只增加到如今的将近7万只，博茨瓦纳从2万只增加到了6.8万只。但另一方面，在禁止狩猎大象的国家中，例如肯尼亚、坦桑尼亚和乌干达，当地人几乎没有动力去养殖大象，但却很有动力去偷猎它们。在这些国家，大象正在消失。结果是肯尼亚今天只有1.6万只大象，而在当时政府禁止狩猎前，肯尼亚约有14万只大象。自1970年以来，坦桑尼亚的大象已经从25万只锐减到6万只，乌干达则从2万只减少到1600只。 私有化是灵丹妙药吗？一旦“公地”变成了可以交易的商品，那么这些资源很快会集中于少数企业或个人手中，而这些资源的拥有者却并不参与到日常生产中。私有化将会损害弱势群体的利益，那些本来依靠公共资源的弱势群体很可能因为私有化而丧失这部分权益。 Game Theory--Chapter 1

公地问题 公地问题的可能解决方案：（2）政府管理 一个政府管理的例子：2015年在巴黎签署的《巴黎协议》共12页29个大条目，包括目标、减缓、适应、损失损害、资金、技术、能力建设、透明度、全球盘点等内容。协议规定，缔约各方将加强对气候变化威胁的全球应对，到2100年，相比工业化之前的水平，全球平均气温升高幅度将力争控制在2摄氏度之内，并为把升温控制在1.5摄氏度之内而努力。全球将尽快实现温室气体排放达到峰值，并且在2050年到2100年之间实现人类活动排放与自然吸收之间的平衡。也就是说，在考虑到海洋和森林有能力吸收温室气体的情况下，本世纪下半叶让地球的新温室气体排放总量为零。《巴黎协议》描绘了一个非常美的蓝图，不过由于不具备强制约束力，这个蓝图能否实现还未可知。 环保税 Game Theory--Chapter 1

公地问题 公地问题的可能解决方案：（3）内化外部性 一个内化外部性的例子：诞生于犹他州的校园共享单车“Aggie Blue Bikes（以下简称ABB）”就是内化外部性的一个很好的例子。ABB虽然范围不大，但运营状况不错，被盗或失修率仅为6％，这主要是因为其采取的长租而非短租的形式。ABB的创始人认为，要防止破坏，就必须让用户为自己的承租行为负责，而长期的租赁方式无疑能刺激用户关爱自行车。因此，ABB的大部分自行车都必须长租一个学期，租期内如果车辆的磨损超出了一定限度而承租人没有付费的话，这个行为将会被记录在学生的档案上。当租车的行为和个人信誉档案挂钩，乃至影响到未来的毕业，恐怕没有人会锁车或是破坏了。 Game Theory--Chapter 1

公地问题 公地问题的可能解决方案：（4）集体自治 2009年诺贝尔经济学奖获得者Eleanor Ostrom认为除了私有化和政府加强管理外，群体自治也能够很好地处理公地问题，集体监督能够很好地避免由于个人私利产生的滥用问题。 集体自治的一个例子：在瑞士的托拜尔，公共财产的享用权被严格限定在拥有社群权利的居民中。任何企图侵夺更大份额放养权的尝试都会被课以大额罚金。村里的法规由全体村民投票决定。有关公共资源使用的所有重要决定都是由占用者自己做出的。他们使用的许多规则的监督成本和其他交易成本都较低，并能减少潜在的冲突。 限渔令、限伐令 Game Theory--Chapter 1

Snoopy Game Theory--Chapter 1

Solving matching pennies Player 2 Head Tail Player 1 -1 , 1 1 , -1 q 1-q r 1-r 把你的策略随机化会使你的竞争对手感到吃惊 Player 1分别以概率r和1-r选择Head和Tail. Player 2分别以概率q和1-q选择Head和Tail. 混合策略: 指定一个实际行动，它是从纯策略集中以某些指定的概率被随机选择出来的. Game Theory--Chapter 1

Mixed strategy 参与人的混合策略是在参与人（纯）策略上的概率分布. Chris的一个混合策略是概率分布(p, 1-p), 其中p 是选择Opera的概率, 1-p 是选择Prize Fight 的概率. 如果p=1，那么 Chris实际上选择了Opera. 如果p=0，那么Chris实际上选择了Prize Fight. Battle of sexes Pat Opera Prize Fight Chris Opera (p) 2 , 1 0 , 0 Prize Fight (1-p) 0 , 0 1 , 2 Game Theory--Chapter 1

Solving matching pennies Player 2 Head Tail Player 1 -1 , 1 1 , -1 Expected payoffs r 1-2q 1-r 2q-1 q 1-q Player 1的期望收益 如果Player 1选择Head, -q+(1-q)=1-2q 如果Player 1选择Tail, q-(1-q)=2q-1 Game Theory--Chapter 1

Solving matching pennies Player 2 Head Tail Player 1 -1 , 1 1 , -1 Expected payoffs r 1-2q 1-r 2q-1 q 1-q 1 q r 1/2 Player 1的最优反应 B1(q): For q<0.5, Head (r=1) For q>0.5, Tail (r=0) For q=0.5, indifferent (0r1) Game Theory--Chapter 1

Solving matching pennies Player 2 Head Tail Player 1 -1 , 1 1 , -1 Expected payoffs r 1-2q 1-r 2q-1 q 1-q Expected payoffs 2r-1 1-2r Player 2的期望收益 如果Player 2选择Head, r-(1-r)=2r-1 如果Player 2选择Tail, -r+(1-r)=1-2r Game Theory--Chapter 1

Solving matching pennies Player 2 Head Tail Player 1 -1 , 1 1 , -1 1-2q 2q-1 Expected payoffs r 1-r q 1-q Expected payoffs 2r-1 1-2r 1 q r 1/2 Player 2的最优反应 B2(r): For r<0.5, Tail (q=0) For r>0.5, Head (q=1) For r=0.5, indifferent (0q1) Game Theory--Chapter 1

Solving matching pennies Player 2 Head Tail Player 1 -1 , 1 1 , -1 Player 1的最优反应 B1(q): For q<0.5, Head (r=1) For q>0.5, Tail (r=0) For q=0.5, indifferent (0r1) Player 2的最优反应 B2(r): For r<0.5, Tail (q=0) For r>0.5, Head (q=1) For r=0.5, indifferent (0q1) 查看 r = 0.5  B1(0.5) q = 0.5  B2(0.5) r 1-r q 1-q Mixed strategy Nash equilibrium 1 q r 1/2 Game Theory--Chapter 1

Mixed strategy 混合策略: 一个参与人的混合策略是在参与人的（纯）策略上的概率分布. Game Theory--Chapter 1

Mixed strategy: example 硬币配对 Player 1 有两个纯策略: H和T ( 1(H)=0.5, 1(T)=0.5 ) 是一个混合策略. 即, player 1分别以0.5和0.5的概率选H和T. ( 1(H)=0.3, 1(T)=0.7 ) 是另一个混合策略. 即, player 1分别以0.3和0.7的概率选H和T. Game Theory--Chapter 1

Mixed strategy: example Player 2 L (0) C (1/3) R (2/3) Player 1 T (3/4) 0 , 2 3 , 3 1 , 1 M (0) 4 , 0 0 , 4 2 , 3 B (1/4) 3 , 4 5 , 1 0 , 7 Player 1: (3/4, 0, ¼) 是一个混合策略. 即, 1(T)=3/4, 1(M)=0 及 1(B)=1/4. Player 2: (0, 1/3, 2/3)是一个混合策略. 即, 2(L)=0, 2(C)=1/3 及 2(R)=2/3. Game Theory--Chapter 1

Expected payoffs: 2 players each with two pure strategies s21 ( q ) s22 ( 1- q ) Player 1 s11 ( r ) u1(s11, s21), u2(s11, s21) u1(s11, s22), u2(s11, s22) s12 (1- r ) u1(s12, s21), u2(s12, s21) u1(s12, s22), u2(s12, s22) Player 1拥有混合策略 (r, 1- r ). Player 2拥有混合策略 ( q, 1- q ). Player 1选s11的期望收益: EU1(s11, (q, 1-q))=q×u1(s11, s21)+(1-q)×u1(s11, s22) Player 1选s12的期望收益: EU1(s12, (q, 1-q))= q×u1(s12, s21)+(1-q)×u1(s12, s22) Player 1从她的混合策略中得到的期望收益: v1((r, 1-r), (q, 1-q))=rEU1(s11, (q, 1-q))+(1-r)EU1(s12, (q, 1-q)) Game Theory--Chapter 1

Expected payoffs: 2 players each with two pure strategies s21 ( q ) s22 ( 1- q ) Player 1 s11 ( r ) u1(s11, s21), u2(s11, s21) u1(s11, s22), u2(s11, s22) s12 (1- r ) u1(s12, s21), u2(s12, s21) u1(s12, s22), u2(s12, s22) Player 1拥有混合策略 (r, 1- r ). Player 2拥有混合策略 ( q, 1- q ). Player 2选s21的期望收益: EU2(s21, (r, 1-r))=r×u2(s11, s21)+(1-r)×u2(s12, s21) Player 2选s22的期望收益: EU2(s22, (r, 1-r))= r×u2(s11, s22)+(1-r)×u2(s12, s22) Player 2从她的混合策略中得到的期望收益: v2((r, 1-r),(q, 1-q))=qEU2(s21, (r, 1-r))+(1-q)EU2(s22, (r, 1-r)) Game Theory--Chapter 1

Expected payoffs: example Player 2 H (0.3) T (0.7) Player 1 H (0.4) -1 , 1 1 , -1 T (0.6) Player 1: EU1(H, (0.3, 0.7)) = 0.3×(-1) + 0.7×1=0.4 EU1(T, (0.3, 0.7)) = 0.3×1 + 0.7×(-1)=-0.4 v1((0.4, 0.6), (0.3, 0.7))=0.40.4+0.6(-0.4)=-0.08 Player 2: EU2(H, (0.4, 0.6)) = 0.4×1+0.6×(-1) = -0.2 EU2(T, (0.4, 0.6)) = 0.4×(-1)+0.6×1 = 0.2 v2((0.4, 0.6), (0.3, 0.7))=0.3×(-0.2)+0.7×0.2=0.08 Game Theory--Chapter 1

Expected payoffs: example Player 2 L (0) C (1/3) R (2/3) Player 1 T (3/4) 0 , 2 3 , 3 1 , 1 M (0) 4 , 0 0 , 4 2 , 3 B (1/4) 3 , 4 5 , 1 0 , 7 混合策略: p1=( 3/4, 0, ¼ ); p2=( 0, 1/3, 2/3 ). Player 1: EU1(T, p2)=3(1/3)+1(2/3)=5/3, EU1(M, p2)=0(1/3)+2(2/3)=4/3 EU1(B, p2)=5(1/3)+0(2/3)=5/3. v1(p1, p2) = 5/3 Player 2: EU2(L, p1)=2(3/4)+4(1/4)=5/2, EU2(C, p1)=3(3/4)+3(1/4)=5/2, EU2(R, p1)=1(3/4)+7(1/4)=5/2. v1(p1, p2) = 5/2 Game Theory--Chapter 1

Mixed strategy equilibrium 混合策略均衡 每个参与人的一个概率分布 从期望收益的角度来说，不同参与人的这些概率分布之间互为最优反应 Game Theory--Chapter 1

Mixed strategy equilibrium: 2-player each with two pure strategies s21 ( q ) s22 ( 1- q ) Player 1 s11 ( r ) u1(s11, s21), u2(s11, s21) u1(s11, s22), u2(s11, s22) s12 (1- r ) u1(s12, s21), u2(s12, s21) u1(s12, s22), u2(s12, s22) 混合策略纳什均衡: 一个混合策略组合 ((r*, 1-r*), (q*, 1-q*)) 是一个纳什均衡，如果 (r*,1-r*)是(q*, 1-q*) 的一个最优反应, 同时(q*, 1-q*)是(r*,1-r*) 的一个最优反应. 即, v1((r*, 1-r*), (q*, 1-q*))  v1((r, 1-r), (q*, 1-q*)), for all 0 r 1 v2((r*, 1-r*), (q*, 1-q*))  v2((r*, 1-r*), (q, 1-q)), for all 0 q 1 Game Theory--Chapter 1

Find mixed strategy equilibrium in 2-player each with two pure strategies 给定player 2的混合策略，找到player 1的最优反应对应（best response correspondence ） 给定player 1的混合策略，找到player 2的最优反应对应 使用最优反应对应来决定混合策略纳什均衡. Game Theory--Chapter 1

Employee Monitoring 雇员可以努力工作也可以偷懒卸责 经理可以监督也可以不监督 薪水: $100K除非消极怠工被抓 雇员不工作时的利润: $0 监督的成本: $10K Game Theory--Chapter 1

Employee Monitoring 雇员的最优反应B1(q): 50 , 90 50 , 100 0 , -10 100 , -100 Manager Monitor ( q ) Not Monitor (1-q) Employee Work ( r ) 50 , 90 50 , 100 Shirk (1-r ) 0 , -10 100 , -100 Expected payoffs 50 100(1-q) Expected payoffs 100r-10 200r-100 雇员的最优反应B1(q): Shirk (r=0) if q<0.5 Work (r=1) if q>0.5 Any mixed strategy (0r1) if q=0.5 Game Theory--Chapter 1

Employee Monitoring 经理的最优反应B2(r): 50 , 90 50 , 100 0 , -10 100 , -100 Manager Monitor ( q ) Not Monitor (1-q) Employee Work ( r ) 50 , 90 50 , 100 Shirk (1-r ) 0 , -10 100 , -100 Expected payoffs 50 100(1-q) Expected payoffs 100r-10 200r-100 经理的最优反应B2(r): Monitor (q=1) if r<0.9 Not Monitor (q=0) if r>0.9 Any mixed strategy (0q1) if r=0.9 Game Theory--Chapter 1

Employee Monitoring 雇员的最优反应B1(q): Shirk (r=0) if q<0.5 Work (r=1) if q>0.5 Any mixed strategy (0r1) if q=0.5 经理的最优反应B2(r): Monitor (q=1) if r<0.9 Not Monitor (q=0) if r>0.9 Any mixed strategy (0q1) if r=0.9 Mixed strategy Nash equilibrium ((0.9,0.1),(0.5,0.5)) 1 q r 0.5 0.9 Game Theory--Chapter 1

Battle of sexes Chris选Opera的预期收益: 2q Chris选Prize Fight的预期收益: 1-q Pat Opera (q) Prize Fight (1-q) Chris Opera ( r ) 2 , 1 0 , 0 Prize Fight (1-r) 0 , 0 1 , 2 Chris选Opera的预期收益: 2q Chris选Prize Fight的预期收益: 1-q Chris的最优反应B1(q): Prize Fight (r=0) if q<1/3 Opera (r=1) if q>1/3 Any mixed strategy (0r1) if q=1/3 Game Theory--Chapter 1

Battle of sexes Pat选择Opera的预期收益: r Pat选择Prize Fight的预期收益: 2(1-r) Opera (q) Prize Fight (1-q) Chris Opera ( r ) 2 , 1 0 , 0 Prize Fight (1-r) 0 , 0 1 , 2 Pat选择Opera的预期收益: r Pat选择Prize Fight的预期收益: 2(1-r) Pat的最优反应B2(r): Prize Fight (q=0) if r<2/3 Opera (q=1) if r>2/3 Any mixed strategy (0q1) if r=2/3, Game Theory--Chapter 1

Battle of sexes Chris的最优反应 B1(q): Pat的最优反应B2(r): Prize Fight (r=0) if q<1/3 Opera (r=1) if q>1/3 Any mixed strategy (0r1) if q=1/3 Pat的最优反应B2(r): Prize Fight (q=0) if r<2/3 Opera (q=1) if r>2/3 Any mixed strategy (0q1) if r=2/3 三个纳什均衡: ((1, 0), (1, 0)) ((0, 1), (0, 1)) ((2/3, 1/3), (1/3, 2/3)) 1 q r 2/3 1/3 Game Theory--Chapter 1

Expected payoffs: 2 players each with two pure strategies s21 ( q ) s22 ( 1- q ) Player 1 s11 ( r ) u1(s11, s21), u2(s11, s21) u1(s11, s22), u2(s11, s22) s12 (1- r ) u1(s12, s21), u2(s12, s21) u1(s12, s22), u2(s12, s22) Player 1有混合策略 (r, 1- r ). Player 2有混合策略 ( q, 1- q ). Player 1选择s11的期望收益: EU1(s11, (q, 1-q))=q×u1(s11, s21)+(1-q)×u1(s11, s22) Player 1选择s12的期望收益: EU1(s12, (q, 1-q))= q×u1(s12, s21)+(1-q)×u1(s12, s22) Player 1混合策略的期望收益: v1((r, 1-r), (q, 1-q))=rEU1(s11, (q, 1-q))+(1-r)EU1(s12, (q, 1-q)) Game Theory--Chapter 1

Expected payoffs: 2 players each with two pure strategies s21 ( q ) s22 ( 1- q ) Player 1 s11 ( r ) u1(s11, s21), u2(s11, s21) u1(s11, s22), u2(s11, s22) s12 (1- r ) u1(s12, s21), u2(s12, s21) u1(s12, s22), u2(s12, s22) Player 1有混合策略 (r, 1- r ). Player 2有混合策略 ( q, 1- q ). Player 2选择s21的期望收益: EU2(s21, (r, 1-r))=r×u2(s11, s21)+(1-r)×u2(s12, s21) Player 2选择s22的期望收益: EU2(s22, (r, 1-r))= r×u2(s11, s22)+(1-r)×u2(s12, s22) Player 2混合策略的期望收益: v2((r, 1-r),(q, 1-q))=qEU2(s21, (r, 1-r))+(1-q)EU2(s22, (r, 1-r)) Game Theory--Chapter 1

Mixed strategy equilibrium: 2-player each with two pure strategies s21 ( q ) s22 ( 1- q ) Player 1 s11 ( r ) u1(s11, s21), u2(s11, s21) u1(s11, s22), u2(s11, s22) s12 (1- r ) u1(s12, s21), u2(s12, s21) u1(s12, s22), u2(s12, s22) 混合策略纳什均衡: 一个混合策略组合 ((r*, 1-r*), (q*, 1-q*)) 是一个纳什均衡，如果 (r*,1-r*)是对(q*, 1-q*) 的最优反应, 而(q*, 1-q*)是对(r*,1-r*) 的最优反应. 即, v1((r*, 1-r*), (q*, 1-q*))  v1((r, 1-r), (q*, 1-q*)), for all 0 r 1 v2((r*, 1-r*), (q*, 1-q*))  v2((r*, 1-r*), (q, 1-q)), for all 0 q 1 Game Theory--Chapter 1

2-player each with two strategies Lecture 1 May 19, 2003 2-player each with two strategies Player 2 s21 ( q ) s22 ( 1- q ) Player 1 s11 ( r ) u1(s11, s21), u2(s11, s21) u1(s11, s22), u2(s11, s22) s12 (1- r ) u1(s12, s21), u2(s12, s21) u1(s12, s22), u2(s12, s22) 定理 1 (混合纳什均衡的性质) 一个混合策略组合 ((r*, 1-r*), (q*, 1-q*)) 是一个纳什均衡当且仅当 v1((r*, 1-r*), (q*, 1-q*))  EU1(s11, (q*, 1-q*)) v1((r*, 1-r*), (q*, 1-q*))  EU1(s12, (q*, 1-q*)) v2((r*, 1-r*), (q*, 1-q*))  EU2(s21, (r*, 1-r*)) v2((r*, 1-r*), (q*, 1-q*))  EU2(s22, (r*, 1-r*)) Game Theory--Chapter 1

Theorem 1: illustration Lecture 1 May 19, 2003 Theorem 1: illustration Matching pennies Player 2 H (0.5) T (0.5) Player 1 -1 , 1 1 , -1 Player 1: EU1(H, (0.5, 0.5)) = 0.5×(-1) + 0.5×1=0 EU1(T, (0.5, 0.5)) = 0.5×1 + 0.5×(-1)=0 v1((0.5, 0.5), (0.5, 0.5))=0.50+0.50=0 Player 2: EU2(H, (0.5, 0.5)) = 0.5×1+0.5×(-1) =0 EU2(T, (0.5, 0.5)) = 0.5×(-1)+0.5×1 = 0 v2((0.5, 0.5), (0.5, 0.5))=0.5×0+0.5×0=0 Game Theory--Chapter 1

Theorem 1: illustration Matching pennies Player 2 H (0.5) T (0.5) Player 1 -1 , 1 1 , -1 Player 1: v1((0.5, 0.5), (0.5, 0.5))  EU1(H, (0.5, 0.5)) v1((0.5, 0.5), (0.5, 0.5))  EU1(T, (0.5, 0.5)) Player 2: v2((0.5, 0.5), (0.5, 0.5))  EU2(H, (0.5, 0.5)) v2((0.5, 0.5), (0.5, 0.5))  EU2(T, (0.5, 0.5)) 所以, 根据定理1，((0.5, 0.5), (0.5, 0.5)) 是一个混合策略纳什均衡. Game Theory--Chapter 1

Theorem 1: illustration Employee Monitoring Manager Monitor (0.5) Not Monitor (0.5) Employee Work (0.9) 50 , 90 50 , 100 Shirk (0.1) 0 , -10 100 , -100 Employee选择“work”的期望收益 EU1(Work, (0.5, 0.5)) = 0.5×50 + 0.5×50=50 Employee选择“shirk”的期望收益 EU1(Shirk, (0.5, 0.5)) = 0.5×0 + 0.5×100=50 Employee混合策略的期望收益 v1((0.9, 0.1), (0.5, 0.5))=0.950+0.150=50 Game Theory--Chapter 1

Theorem 1: illustration Employee Monitoring Manager Monitor (0.5) Not Monitor (0.5) Employee Work (0.9) 50 , 90 50 , 100 Shirk (0.1) 0 , -10 100 , -100 Manager选择“Monitor”的预期收益 EU2(Monitor, (0.9, 0.1)) = 0.9×90+0.1×(-10) =80 Manager选择“Not”的预期收益 EU2(Not, (0.9, 0.1)) = 0.9×100+0.1×(-100) = 80 Manager混合策略的预期收益 v2((0.9, 0.1), (0.5, 0.5))=0.5×80+0.5×80=80 Game Theory--Chapter 1

Theorem 1: illustration Employee Monitoring Manager Monitor (0.5) No Monitor (0.5) Employee Work (0.9) 50 , 90 50 , 100 Shirk (0.1) 0 , -10 100 , -100 Employee v1((0.9, 0.1), (0.5, 0.5))  EU1(Work, (0.5, 0.5)) v1((0.9, 0.1), (0.5, 0.5))  EU1(Shirk, (0.5, 0.5)) Manager v2((0.9, 0.1), (0.5, 0.5))  EU2(Monitor, (0.9, 0.1)) v2((0.9, 0.1), (0.5, 0.5))  EU2(Not, (0.9, 0.1)) 所以, 根据定理1，((0.9, 0.1), (0.5, 0.5)) 是一个混合策略纳什均衡. Game Theory--Chapter 1

Theorem 1: illustration Battle of sexes Pat Opera (1/3) Prize Fight (2/3) Chris Opera (2/3 ) 2 , 1 0 , 0 Prize Fight (1/3) 0 , 0 1 , 2 使用命题1检查 ((2/3, 1/3), (1/3, 2/3))是否是一个混合策略纳什均衡. Game Theory--Chapter 1

Mixed strategy equilibrium: 2-player each with two strategies s21 ( q ) s22 ( 1- q ) Player 1 s11 ( r ) u1(s11, s21), u2(s11, s21) u1(s11, s22), u2(s11, s22) s12 (1- r ) u1(s12, s21), u2(s12, s21) u1(s12, s22), u2(s12, s22) 定理 2 令((r*, 1-r*), (q*, 1-q*))是一个混合策略组合, 其中 0 <r*<1, 0<q*<1. 那么 ((r*, 1-r*), (q*, 1-q*))是一个混合策略纳什均衡，当且仅当 EU1(s11, (q*, 1-q*)) = EU1(s12, (q*, 1-q*)) EU2(s21, (r*, 1-r*)) = EU2(s22, (r*, 1-r*)) 即,对于每个参与人来说，她的两个策略都是无差异的. Game Theory--Chapter 1

Use indifference to find mixed Nash equilibrium (2-player each with 2 strategies) 使用定理2来找到混合策略纳什均衡 解 EU1(s11, (q*, 1-q*)) = EU1(s12, (q*, 1-q*)) 解 EU2(s21, (r*, 1-r*)) = EU2(s22, (r*, 1-r*)) Game Theory--Chapter 1

Use Theorem 2 to find mixed strategy Nash equilibrium: illustration Matching pennies Player 2 H ( q ) T ( 1–q ) Player 1 H ( r ) -1 , 1 1 , -1 T ( 1–r ) Player 1选择 Head 和Tail无差异. EU1(H, (q, 1–q)) = q×(-1) + (1–q)×1=1–2q EU1(T, (q, 1–q)) = q×1 + ×(1–q) (-1)=2q–1 EU1(H, (q, 1–q)) = EU1(T, (q, 1–q)) 1–2q = 2q–1 4q = 2 从而 q = 1/2 Game Theory--Chapter 1

Use Theorem 2 to find mixed strategy Nash equilibrium: illustration Matching pennies Player 2 H ( q ) T ( 1–q ) Player 1 H ( r ) -1 , 1 1 , -1 T ( 1–r ) Player 2选择 Head 和Tail无差异. EU2(H, (r, 1–r)) = r ×1+(1–r)×(-1) =2r – 1 EU2(T, (r, 1–r)) = r×(-1)+(1–r)×1 = 1 – 2r EU2(H, (r, 1–r)) = EU2(T, (r, 1–r)) 2r – 1= 1 – 2r 4r = 2 从而 r = 1/2 所以, 根据定理2，((0.5, 0.5), (0.5, 0.5))是一个混合策略纳什均衡. Game Theory--Chapter 1

Use Theorem 2 to find mixed strategy Nash equilibrium: illustration Employee Monitoring Manager Monitor ( q ) Not Monitor (1–q ) Employee Work (r) 50 , 90 50 , 100 Shirk (1–r) 0 , -10 100 , -100 Employee选择“Work”的期望收益 EU1(Work, (q, 1–q)) = q×50 + (1–q)×50=50 Employee选择“Shirk”的期望收益 EU1(Shirk, (q, 1–q)) = q×0 + (1–q)×100=100(1–q) Employee选择“Work”和“Shirk”无差异. 50=100(1–q) q=1/2 Game Theory--Chapter 1

Use Theorem 2 to find mixed strategy Nash equilibrium: illustration Employee Monitoring Manager Monitor ( q ) Not Monitor (1–q ) Employee Work (r) 50 , 90 50 , 100 Shirk (1–r) 0 , -10 100 , -100 Manager选择“Monitor”的期望收益 EU2(Monitor, (r, 1–r)) = r×90+(1–r)×(-10) =100r–10 Manager选择“Not”的期望收益 EU2(Not, (r, 1–r)) = r×100+(1–r)×(-100) =200r–100 Manager选择“Monitor”和“Not”无差异 100r–10 =200r–100 implies that r=0.9. 所以, 根据定理2，((0.9, 0.1), (0.5, 0.5))是一个混合策略纳什均衡. Game Theory--Chapter 1

Use Theorem 2 to find mixed strategy Nash equilibrium: illustration Battle of sexes Pat Opera (q) Prize Fight (1-q) Chris Opera ( r ) 2 , 1 0 , 0 Prize Fight (1-r) 0 , 0 1 , 2 使用定理2找到纳什均衡 Game Theory--Chapter 1

Use Theorem 2 to find mixed strategy Nash equilibrium: illustration Lecture 1 May 19, 2003 Use Theorem 2 to find mixed strategy Nash equilibrium: illustration Battle of sexes Pat Opera (q) Prize Fight (1-q) Chris Opera ( r ) 2 , 1 0 , 0 Prize Fight (1-r) 0 , 0 1 , 2 Chris选择Opera的期望收益 EU1(O, (q, 1–q)) = q×2 + (1–q)×0 = 2q Chris选择Prize Fight的期望收益 EU1(F, (q, 1–q)) = q×0 + (1–q)×1 = 1–q Chris选择Opera和Prize无差异 EU1(O, (q, 1–q)) = EU1(F, (q, 1–q)) 2q = 1–q 3q = 1 从而q = 1/3 Game Theory--Chapter 1

Use Theorem 2 to find mixed strategy Nash equilibrium: illustration Lecture 1 May 19, 2003 Use Theorem 2 to find mixed strategy Nash equilibrium: illustration Battle of sexes Pat Opera (q) Prize Fight (1-q) Chris Opera ( r ) 2 , 1 0 , 0 Prize Fight (1-r) 0 , 0 1 , 2 Pat选择Opera的期望收益 EU2(O, (r, 1–r)) = r ×1+(1–r)×0 = r Pat选择Prize Fight的期望收益 EU2(F, (r, 1–r)) = r×0+(1–r)×2 = 2 – 2r Pat选择Opera和Prize无差异 EU2(O, (r, 1–r)) = EU2(F, (r, 1–r)) r = 2 – 2r 3r = 2 从而 r = 2/3 Game Theory--Chapter 1

Use Theorem 2 to find mixed strategy Nash equilibrium: illustration Lecture 1 May 19, 2003 Use Theorem 2 to find mixed strategy Nash equilibrium: illustration Battle of sexes Pat Opera (q) Prize Fight (1-q) Chris Opera ( r ) 2 , 1 0 , 0 Prize Fight (1-r) 0 , 0 1 , 2 所以, ( (2/3, 1/3), (1/3, 2/3) ) 是一个混合策略纳什均衡. 即, Chris以2/3的概率选择 Opera ，以1/3的概率选择 Prize Fight. Pat以1/3的概率选择 Opera ，以2/3的概率选择 Prize Fight. Game Theory--Chapter 1

Example 1 Bruce 和Sheila要决定是去看歌剧还是去看职业摔跤表演. Sheila去看歌剧和职业摔跤分别可以得到效用4和1. 他们同意使用以下方法决定去哪里: Bruce和Sheila每人把一枚硬币放在咖啡桌上电视遥控器下面（假设他们不作弊看对方的硬币）. 他们数到3，同时显示他们的硬币. 如果他们的硬币显示一致 (都是heads,或都是tails), 那么Sheila决定去看歌剧还是职业摔跤, 而如果他们的硬币显示不一致 (heads, tails 或tails, heads)，那么 Bruce决定去哪里. Game Theory--Chapter 1

Example 1 Bruce选Head的期望收益 Bruce选Tail的期望收益 Bruce选Head和Tail无差异 Sheila H ( q ) T ( 1–q ) Bruce H ( r ) 1 , 4 4 , 1 T ( 1–r ) Bruce选Head的期望收益 EU1(H, (q, 1–q)) = q×1 + (1–q)×4 = 4–3q Bruce选Tail的期望收益 EU1(T, (q, 1–q)) = q×4 + (1–q)×1 = 1+3q Bruce选Head和Tail无差异 EU1(H, (q, 1–q)) = EU1(T, (q, 1–q)) 4–3q = 1+3q 6q = 3 从而 q = 1/2 Game Theory--Chapter 1

Example 1 EU2(H, (r, 1–r)) = r ×4+(1–r)×1 = 3r + 1 Sheila H ( q ) T ( 1–q ) Bruce H ( r ) 1 , 4 4 , 1 T ( 1–r ) Sheila选Head的期望收益 EU2(H, (r, 1–r)) = r ×4+(1–r)×1 = 3r + 1 Sheila选Tail的期望收益 EU2(T, (r, 1–r)) = r×1+(1–r)×4 = 4 – 3r Sheila选Head和Tail无差异 EU2(H, (r, 1–r)) = EU2(T, (r, 1–r)) 3r + 1 = 4 – 3r 6r = 3 从而 r = ½ ( (1/2, 1/2), (1/2, 1/2) ) 是一个混合策略纳什均衡. Game Theory--Chapter 1

Example 2 Player 1选择T的期望收益 Player 1选择B的期望收益 Player 1选择T和B无差异 L ( q ) R ( 1–q ) Player 1 T ( r ) 6 , 0 0 , 6 B ( 1–r ) 3 , 2 Player 1选择T的期望收益 EU1(T, (q, 1–q)) = q×6 + (1–q)×0 = 6q Player 1选择B的期望收益 EU1(B, (q, 1–q)) = q×3 + (1–q)×6 = 6-3q Player 1选择T和B无差异 EU1(T, (q, 1–q)) = EU1(B, (q, 1–q)) 6q = 6-3q 9q = 6 从而 q = 2/3 Game Theory--Chapter 1

Example 2 EU2(L, (r, 1–r)) = r ×0+(1–r)×2 =2- 2r Player 2 L ( q ) R ( 1–q ) Player 1 T ( r ) 6 , 0 0 , 6 B ( 1–r ) 3 , 2 Player 2选择L的期望收益 EU2(L, (r, 1–r)) = r ×0+(1–r)×2 =2- 2r Player 2选择R的期望收益 EU2(R, (r, 1–r)) = r×6+(1–r)×0 = 6r Player 2选择L和R无差异 EU2(L, (r, 1–r)) = EU2(R, (r, 1–r)) 2- 2r = 6r 8r = 2 从而 r = ¼ ( (1/4, 3/4), (2/3, 1/3) ) 是一个混合策略纳什均衡. Game Theory--Chapter 1

Example 3:Market entry game 两家企业, Firm 1 和 Firm 2, 必须同时决定是否让他们的一家饭店进入一家购物中心. 每个企业有两个策略: Enter, Not Enter 企业如果选择 “Not Enter”, 它获得的利润为 0 如果一家企业选 “Enter”而另一家企业选 “Not Enter”，那么选“Enter”的企业得到 $500K 如果两家企业都选 “Enter” ，那么它们都损失$100K，因为需求是有限的 Game Theory--Chapter 1

Example 3:Market entry game Firm 2 Enter ( q ) Not Enter ( 1–q ) Firm 1 Enter ( r ) -100 , -100 500 , 0 Not Enter ( 1–r ) 0 , 500 0 , 0 你能找到几个纳什均衡? 两个纯策略纳什均衡 (Not Enter, Enter) and (Enter, Not Enter) 一个混合策略纳什均衡 ((5/6, 1/6), (5/6, 1/6)) 即 r=5/6 ， q=5/6 Game Theory--Chapter 1

Example 4 你能找到几个纳什均衡? 两个纯策略纳什均衡 (B, L) and (T, R) Player 2 L ( q ) R ( 1–q ) Player 1 T ( r ) 1 , 1 1 , 2 B ( 1–r ) 2 , 3 0 , 1 你能找到几个纳什均衡? 两个纯策略纳什均衡 (B, L) and (T, R) 一个混合策略纳什均衡 ((2/3, 1/3), (1/2, 1/2)) 即 r=2/3 ， q=1/2 Game Theory--Chapter 1

Example: Rock, paper and scissors 两个参与人同时宣称Rock, Paper或 Scissors. Paper 胜 (包住) rock Rock 胜 (撞钝) scissors Scissors 胜 (剪破) paper 获得胜利的参与人从对手那里得到$1 如果参与人获得平局则不会得到支付 Game Theory--Chapter 1

Example: Rock, paper and scissors Player 2 Rock Paper Scissors Player 1 0 , 0 -1 , 1 1 , -1 你能猜到一个混合策略纳什均衡吗? Game Theory--Chapter 1

Mixed strategy Nash equilibrium: 2-player each with two pure strategies s21 ( q ) s22 ( 1- q ) Player 1 s11 ( r ) u1(s11, s21), u2(s11, s21) u1(s11, s22), u2(s11, s22) s12 (1- r ) u1(s12, s21), u2(s12, s21) u1(s12, s22), u2(s12, s22) 混合策略纳什均衡: 一个混合策略组合 ((r*, 1-r*), (q*, 1-q*)) 是一个纳什均衡，如果(r*,1-r*)是(q*, 1-q*) 的一个最优反应,同时(q*, 1-q*)是(r*,1-r*) 的一个最优反应. 即, v1((r*, 1-r*), (q*, 1-q*))  v1((r, 1-r), (q*, 1-q*)), for all 0 r 1 v2((r*, 1-r*), (q*, 1-q*))  v2((r*, 1-r*), (q, 1-q)), for all 0 q 1 Game Theory--Chapter 1

2-player each with two strategies Lecture 1 May 19, 2003 2-player each with two strategies Player 2 s21 ( q ) s22 ( 1- q ) Player 1 s11 ( r ) u1(s11, s21), u2(s11, s21) u1(s11, s22), u2(s11, s22) s12 (1- r ) u1(s12, s21), u2(s12, s21) u1(s12, s22), u2(s12, s22) 定理 1 (混合纳什均衡的性质) 一个混合策略组合 ((r*, 1-r*), (q*, 1-q*)) 是一个纳什均衡当且仅当 v1((r*, 1-r*), (q*, 1-q*))  EU1(s11, (q*, 1-q*)) v1((r*, 1-r*), (q*, 1-q*))  EU1(s12, (q*, 1-q*)) v2((r*, 1-r*), (q*, 1-q*))  EU2(s21, (r*, 1-r*)) v2((r*, 1-r*), (q*, 1-q*))  EU2(s22, (r*, 1-r*)) Game Theory--Chapter 1

Mixed strategy equilibrium: 2-player each with two strategies s21 ( q ) s22 ( 1- q ) Player 1 s11 ( r ) u1(s11, s21), u2(s11, s21) u1(s11, s22), u2(s11, s22) s12 (1- r ) u1(s12, s21), u2(s12, s21) u1(s12, s22), u2(s12, s22) 定理 2 令((r*, 1-r*), (q*, 1-q*))是一个混合策略组合, 其中 0 <r*<1, 0<q*<1. 那么 ((r*, 1-r*), (q*, 1-q*))是一个混合策略纳什均衡，当且仅当 EU1(s11, (q*, 1-q*)) = EU1(s12, (q*, 1-q*)) EU2(s21, (r*, 1-r*)) = EU2(s22, (r*, 1-r*)) 即,对于每个参与人来说，她的两个策略都是无差异的. Game Theory--Chapter 1

2-player each with a finite number of pure strategies 参与人集合: {Player 1, Player 2} 策略集: player 1: S1= { s11, s12, ..., s1J } player 2: S2= { s21, s22, ..., s2K } 收益函数: player 1: u1(s1j, s2k) player 2: u2(s1j, s2k) for j = 1, 2, ..., J and k = 1, 2, ..., K Game Theory--Chapter 1

2-player each with a finite number of pure strategies s21 (p21) s22 (p22) ....... s2K (p2K) s11 (p11) u2(s11, s21) u1(s11, s21) u2(s11, s22) u1(s11, s22) u2(s11, s2K) u1(s11, s2K) s12 (p12) u2(s12, s21) u1(s12, s21) u2(s12, s22) u1(s12, s22) u2(s12, s2K) u1(s12, s2K) .... ...... s1J (p1J) u2(s1J, s21) u1(s1J, s21) u2(s1J, s22) u1(s1J, s22) u2(s1J, s2K) u1(s1J, s2K) Player 1 Player 1的混合策略: p1=(p11, p12, ..., p1J ) Player 2的混合策略: p2=(p21, p22, ..., p2K ) Game Theory--Chapter 1

Expected payoffs: 2-player each with a finite number of pure strategies Player 1纯策略s11的期望收益: EU1(s11, p2)=p21×u1(s11, s21)+p22×u1(s11, s22)+...+p2k×u1(s11, s2k)+...+p2K×u1(s11, s2K) Player 1纯策略s12的期望收益: EU1(s12, p2)=p21×u1(s12, s21)+p22×u1(s12, s22)+...+p2k×u1(s12, s2k)+...+p2K×u1(s12, s2K) ......... Player 1纯策略s1J的期望收益: EU1(s1J, p2)=p21×u1(s1J, s21)+p22×u1(s1J, s22)+...+p2k×u1(s1J, s2k)+...+p2K×u1(s1J, s2K) Player 1混合策略p1的期望收益: v1(p1, p2)=p11EU1(s11, p2)+p12EU1(s12, p2)+...+p1jEU1(s1j, p2)+... +p1JEU1(s1J, p2) Game Theory--Chapter 1

Expected payoffs: 2-player each with a finite number of pure strategies Player 2纯策略s21的期望收益: EU2(s21, p1)=p11×u2(s11, s21)+p12×u2(s12, s21)+...+p1j×u2(s1j, s21)+...+p1J×u2(s1J, s21) Player 2纯策略s22的期望收益: EU2(s22, p1)=p11×u2(s11, s22)+p12×u2(s12, s22)+...+p1j×u2(s1j, s22)+...+p1J×u2(s1J, s22) ........... Player 2纯策略s2K的期望收益: EU2(s2K, p1)=p11×u2(s11, s2K)+p12×u2(s12, s2K)+...+p1j×u2(s1j, s2K)+...+p1J×u2(s1J, s2K) Player 2混合策略p2的期望收益: v2(p1, p2)=p21EU2(s21, p1)+p22EU2(s22, p1) +...+p2kEU2(s2k, p1)+.... +p2KEU2(s2K, p1) Game Theory--Chapter 1

Mixed strategy Nash equilibrium: 2-player each with a finite number of pure strategies 一个混合策略组合 (p1*, p2*), 其中 p1*=(p11*, p12*, ..., p1J* ) p2*=(p21*, p22*, ..., p2K* ) 是一个混合策略均衡，如果player 1的混合策略p1* 是对 player 2的混合策略p2*的最优反应,同时p2*也是p1*的最优反应. 或者,对于player 1的所有混合策略p1, v1(p1*, p2*) v1(p1, p2*), 对于player 2的所有混合策略p2, v2(p1*, p2*)  v2(p1*, p2). 即,给定 player 2的混合策略p2*, player 1如果偏离了p1* ，那么她的境况将不会得到改善. 给定player 1的混合策略p1*, player 2如果偏离了 p2* ，那么她的境况将不会得到改善. Game Theory--Chapter 1

2-player each with a finite number of pure strategies 定理 3 (纳什均衡的性质) 一个混合策略组合 (p1*, p2*), 其中 p1*=(p11*, p12*, ..., p1J* ) p2*=(p21*, p22*, ..., p2K* ) 是一个混合策略纳什均衡，当且仅当 v1(p1*, p2*)  EU1(s1j, p2*), for j = 1, 2, ..., J v2(p1*, p2*)  EU2(s2k, p1*), for k= 1, 2, ..., K Game Theory--Chapter 1

2-player each with a finite number of pure strategies 定理 4 一个混合策略组合 (p1*, p2*), 其中 p1*=(p11*, p12*, ..., p1J* ) p2*=(p21*, p22*, ..., p2K* ) 是一个混合策略纳什均衡，当且仅当它们满足以下条件: player 1: 对任何m 和 n, 如果 p1m*>0 ， p1n*>0 那么 EU1(s1m, p2*) = EU1(s1n, p2*); 如果 p1m*>0 ， p1n*=0 那么 EU1(s1m, p2*)  EU1(s1n, p2*) player 2: 对任何i 和 k, 如果 p2i*>0 and p2k*>0 那么 EU2(s2i, p1*) = EU2(s2k, p1*); 如果 p2i*>0 and p2k*=0 那么 EU2(s2i, p1*)  EU2(s2k, p1*) Game Theory--Chapter 1

2-player each with a finite number of pure strategies 定理4告诉了我们什么? 一个混合策略组合 (p1*, p2*), 其中 p1*=(p11*, p12*, ..., p1J* ), p2*=(p21*, p22*, ..., p2K* ) 是一个混合策略纳什均衡，当且仅当它们满足以下条件: 给定 player 2的 p2*, player 1指定为正概率的每个纯策略的期望收益都相等, 且player 1指定为正概率的任何纯策略的期望收益都不会小于她指定为零概率的纯策略的期望收益. 给定player 1的 p1*, player 2指定为正概率的每个纯策略的期望收益都相等,且player 2指定为正概率的任何纯策略的期望收益都不会小于她指定为零概率的纯策略的期望收益. Game Theory--Chapter 1

2-player each with a finite number of pure strategies 定理4意味着在以下情形中我们有混合策略纳什均衡 给定player 2的混合策略, Player 1指定为正概率的纯策略之间是无差异的. 她指定为正概率的任何纯策略的期望收益都不会小于她指定为零概率的纯策略的期望收益. 给定player 1的混合策略, Player 2指定为正概率的纯策略之间是无差异的. 她指定为正概率的任何纯策略的期望收益都不会小于她指定为零概率的纯策略的期望收益. Game Theory--Chapter 1

Theorem 4: illustration Player 2 L (0) C (1/3) R (2/3) Player 1 T (3/4) 0 , 2 3 , 3 1 , 1 M (0) 4 , 0 0 , 4 2 , 3 B (1/4) 3 , 4 5 , 1 0 , 7 检查是否 ((3/4, 0, 1/4), (0, 1/3, 2/3)) 是一个混合策略纳什均衡 Player 1: EU1(T, p2) = 00+3(1/3)+1(2/3)=5/3, EU1(M, p2) = 40+0(1/3)+2(2/3)=4/3 EU1(B, p2) = 30+5(1/3)+0(2/3)=5/3. Hence, EU1(T, p2) = EU1(B, p2) > EU1(M, p2) Game Theory--Chapter 1

Theorem 4: illustration Player 2 L (0) C (1/3) R (2/3) Player 1 T (3/4) 0 , 2 3 , 3 1 , 1 M (0) 4 , 0 0 , 4 2 , 3 B (1/4) 3 , 4 5 , 1 0 , 7 Player 2: EU2(L, p1)=2(3/4) + 00 + 4(1/4)=5/2, EU2(C, p1)=3(3/4) + 40 + 1(1/4)=5/2, EU2(R, p1)=1(3/4) + 30 + 7(1/4)=5/2. Hence, EU2(C, p1)=EU2(R, p1)EU2(L, p1) 所以,根据定理4， ((3/4, 0, 1/4), (0, 1/3, 2/3)) 是一个混合策略纳什均衡. Game Theory--Chapter 1

Example: Rock, paper and scissors Player 2 Rock (p21) Paper (p22) Scissors (p23) Player 1 Rock (p11) 0 , 0 -1 , 1 1 , -1 Paper (p12) Scissors (p13) 检查在p11>0, p12>0, p13>0, p21>0, p22>0, p23>0中是否存在一个混合策略纳什均衡. Game Theory--Chapter 1

Example: Rock, paper and scissors Player 2 Rock (p21) Paper (p22) Scissors (p23) Player 1 Rock (p11) 0 , 0 -1 , 1 1 , -1 Paper (p12) Scissors (p13) 如果每个参与人为她的每个纯策略都指定正概率, 那么根据定理4,对于每个参与人来说，她的三个纯策略无差异. Game Theory--Chapter 1

Example: Rock, paper and scissors Player 2 Rock (p21) Paper (p22) Scissors (p23) Player 1 Rock (p11) 0 , 0 -1 , 1 1 , -1 Paper (p12) Scissors (p13) Player 1的三个纯策略对她来说无差异 : EU1(Rock, p2) = 0p21+(-1) p22+1 p23 EU1(Paper, p2) = 1 p21+0 p22+(-1) p23 EU1(Scissors, p2) = (-1) p21+1 p22+0 p23 EU1(Rock, p2)= EU1(Paper, p2)= EU1(Scissors, p2) 连同 p21+ p22+ p23=1, 我们有三个方程和三个未知数. Game Theory--Chapter 1

Example: Rock, paper and scissors Player 2 Rock (p21) Paper (p22) Scissors (p23) Player 1 Rock (p11) 0 , 0 -1 , 1 1 , -1 Paper (p12) Scissors (p13) 0p21+(-1) p22+1 p23= 1 p21+0 p22+(-1) p23 0p21+(-1) p22+1 p23 = (-1) p21+1 p22+0 p23 p21+ p22+ p23=1 解得 p21= p22= p23=1/3 Game Theory--Chapter 1

Example: Rock, paper and scissors Player 2 Rock (p21) Paper (p22) Scissors (p23) Player 1 Rock (p11) 0 , 0 -1 , 1 1 , -1 Paper (p12) Scissors (p13) Player 2的三个纯策略对她来说无差异 : EU2(Rock, p1)=0p11+(-1) p12+1 p13 EU2(Paper, p1)=1 p11+0 p12+(-1) p13 EU2(Scissors, p1)=(-1) p11+1 p12+0 p13 EU2(Rock, p1)= EU2(Paper, p1)=EU2(Scissors, p1) 连同 p11+ p12+ p13=1,我们有三个方程和三个未知数. Game Theory--Chapter 1

Example: Rock, paper and scissors Player 2 Rock (p21) Paper (p22) Scissors (p23) Player 1 Rock (p11) 0 , 0 -1 , 1 1 , -1 Paper (p12) Scissors (p13) 0p11+(-1) p12+1 p13=1 p11+0 p12+(-1) p13 0p11+(-1) p12+1 p13=(-1) p11+1 p12+0 p13 p11+ p12+ p13=1 解得 p11= p12= p13=1/3 Game Theory--Chapter 1

Example: Rock, paper and scissors Player 2 Rock (1/3) Paper (1/3) Scissors (1/3) Player 1 0 , 0 -1 , 1 1 , -1 Player 1: EU1(Rock, p2) = 0(1/3)+(-1)(1/3)+1(1/3)=0 EU1(Paper, p2) = 1(1/3)+0(1/3)+(-1)(1/3)=0 EU1(Scissors, p2) = (-1)(1/3)+1(1/3)+0(1/3)=0 Player 2: EU2(Rock, p1)=0(1/3)+(-1)(1/3)+1(1/3)=0 EU2(Paper, p1)=1(1/3)+0(1/3)+(-1)(1/3)=0 EU2(Scissors, p1)=(-1)(1/3)+1(1/3)+0(1/3)=0 所以,根据定理4， (p1=(1/3, 1/3, 1/3), p2=(1/3, 1/3, 1/3))是一个混合策略纳什均衡. Game Theory--Chapter 1

Example: Rock, paper and scissors Player 2 Rock (p21) Paper (p22) Scissors (p23) Player 1 Rock (p11) 0 , 0 -1 , 1 1 , -1 Paper (p12) Scissors (p13) 检查是否存在这样一个混合策略纳什均衡，其中， p11, p12, p13中有一个为正值，且p21, p22, p23中至少有两个为正值. 答案是不存在. Game Theory--Chapter 1

Example: Rock, paper and scissors Player 2 Rock (p21) Paper (p22) Scissors (p23) Player 1 Rock (p11) 0 , 0 -1 , 1 1 , -1 Paper (p12) Scissors (p13) 检查是否存在这样一个混合策略纳什均衡，其中， p11, p12, p13中有两个为正值，且p21, p22, p23中至少有两个为正值. 答案是不存在. Game Theory--Chapter 1

Example: Rock, paper and scissors Player 2 Rock (p21) Paper (p22) Scissors (p23) Player 1 Rock (p11) 0 , 0 -1 , 1 1 , -1 Paper (p12) Scissors (p13) 所以, 根据定理4，(p1=(1/3, 1/3, 1/3), p2=(1/3, 1/3, 1/3)) 是惟一的混合策略纳什均衡. Game Theory--Chapter 1