博弈论完全信息动态博弈.ppt

《博弈论完全信息动态博弈.ppt》由会员分享，可在线阅读，更多相关《博弈论完全信息动态博弈.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、博 弈 论,Game Theory,江西财经大学数学与管理工程系 华长生 H 0791-3816092 江西南昌（330013）,2,华长生制作,第三章 完全信息动态博弈,1. 博弈的扩展式表述 2. 扩展式表述博弈的纳什均衡 3. 子博弈精炼纳什均衡 4. 子博弈精炼纳什均衡应用举例 5. 重复博弈与民间定理(无名氏定理),3,华长生制作,“完全信息”是指每个参与人对所有其他参与人的特征 (战略空间、支付函数等)有完全的了解;,“动态”是指所有参与人分先后选择行动且可能选择多 次行动;,“完全信息动态博弈”就是指每个参与人对所有其他参 与人的特征(战略空间、支付函数等)有完全了解的前提下,

2、分先后选择行动的博弈.,手雷博弈: 第一步:Tom要求Smith负1000$给自己,否则就引爆手中的手雷; 第二步:Smith决定是否要负Tom1000$(要判断Tom所说话的可 信度); 第三步:Tom观察Smith的决定,然后决定是否要引爆手雷.,在动态博弈中都有一个问题:可信任性问题,4,华长生制作,1.博弈的扩展式表述,在上一章,我们利用战略式表述研究了完全信息静态博 弈,并且作为静态博弈的解的概念,重点讨论了纳什均衡(NE).,手雷博弈: 第一步:Tom选择是否威胁要求Smith付1000$给自己,否则就引 爆手中的手雷; 第二步:Smith决定是否要付Tom1000$(要判断Tom

3、所说话的可 信度); 第三步:Tom观察Smith的决定,然后决定是否要引爆手雷.,该博弈的语言描述可以转化为一种很直观的表述结构:,5,华长生制作,这种结构称为博弈树,也称为 博弈的扩展式表述.这是动态博弈 分析中最常用的表述方法.,博弈的扩展式表述包含以下要素:,注意:在这里没有提到战略,战略是选择行动时的策略,博弈的扩展式表述,6,华长生制作,博弈的扩展式表述的一般结构：,结(nodes): 分决策结和终点结, 决策结是参与人采取行动的时 点 , 而终点结则是对应支付向 量的点 .,每一个决策结都只有一个直接前列结(初始结除外), 但可能有若干个直接后续结.,博弈的扩展式表述,7,华长生

4、制作,(2) 枝(branches): 是博弈树上一个 决策结到它的直接后续结的连 线或箭头, 枝实际上是参与人 的一个行动选择.,注意终点结不存在行动集合，只有支付组合,初始结没有进入的枝；终点结没有出去的枝； 每个中间的决策结只有一个进入的枝，但有多个出去的枝.,博弈的扩展式表述,8,华长生制作,(3) 信息集(information sets),开发商博弈的行动次序: 开发商A选择行动: 开发、不开发; 自然选择市场的大小: 大、小; 开发商B选择行动: 开发、不开发;,如果开发商B在决策 之前清楚地知道开发商A 和自然的选择,即参与人在轮到他决策时知道在他之前所发生 的一切,这种情形下

5、的每一个决策结属于一个信息集,即开发商 B有四个信息集.只含有一个决策结的信息集成为单结信息集 . 如果博弈树中的信息集都是但单结的，则称为完美信息博弈, 在完美信息博弈中，参与人在决策前都知道自己处于哪个决 策结.,信息 集,开发商博弈(1),博弈的扩展式表述,9,华长生制作,但是如果开发商B在决 策之前只知道A的选择,并不 清楚自然的选择 , 此时对于 B只有两个信息集,即B在决 策前只知道自己处于哪个信 息集,每个信息集有两个决策 结,而开发商并不知道自己处 于哪个决策结.,开发商博弈(2),含有两个或以上的决策结的信息集称为多结信息集，含有 多结信息集的博弈称为不完美信息博弈。不完美信

6、息博弈中要 求至少有一方具有不完美信息。,博弈的扩展式表述,10,华长生制作,还有一种情形时,开发 商B在决策之前知道市场 需求的大小, 但并不知道开 发商A的选择(如A,B同时选 择), 此时对于B仍然只有两 个信息集,即B在决策前只知 道自己处于哪个信息集, 并 且每个信息集也有两个决策 结,而B不知道自己处于哪个 决策结.,开发商博弈(3),博弈的扩展式表述,11,华长生制作,开发商博弈(4),将开发商博弈的行动 顺序改变：由自然首先选 择市场的大小，然后由开 发商A选择是否开发.并且 开发商A行动前不知道自 然的选择(市场的大小)， 开发商B在行动前知道市 场的大小，但不知道开发 商A

7、的选择.,博弈的扩展式表述,12,华长生制作,博弈的扩展式表述,13,华长生制作,完美记忆和不完美记忆,参与人2的 不完美信息集,参与人1将 第一步自己的选择忘记了,参与人2的 不完美信息集,参与人1将 第二步自己的选择忘记了,忘记自己 选择的博 弈称为不 完美记忆,博弈的扩展式表述,14,华长生制作,2.扩展式表述博弈的纳什均衡,2.1 扩展式表述博弈的战略式表述,战略式表述在博弈开始之前就制定 了相机行动计划 ,即“如果.,我将 选择.,扩展式表述是相机行动，要等待博 弈到达自己的信息集，然后再决定 选择什么行动 .,考虑手雷博弈是否存在纳什均衡,扩展式表述的博弈如何求纳什均衡？,先考虑该

8、博弈的战略式表述方法：,15,华长生制作,扩展式表述博弈的纳什均衡,第一步Tom有两个纯战略：,威胁，不威胁,第二步在Tom选择“威胁时”Smith有 两个战略为：,付,不付,引爆,不引爆,第三步在Smith选择“付”时Tom有 两个战略为：,唯一的纳什均衡 (不威胁,不付),16,华长生制作,开发商A的战略有两个：,开发，不开发,而开发商B的战略有四个：,A开发我也开发； A开发我不开发； A不开发我开发； A不开发我不开发；,开发商B的四个战略表示为,开发,开发;开发,不开发;不开发,开发; 不开发,不开发;,注意行动和战略的区别 战略是行动的准则,扩展式表述博弈的纳什均衡,17,华长生制

9、作,这个战略式表述的博弈中有两个 纯战略的纳什均衡：,(开发,开发,开发), (开发,开发,不开发),对应的行动组合只有一个:,(A开发,B也开发),但均衡(开发,开发,不开发)中B的均衡 战略开发,不开发是不可信的.,扩展式表述博弈的纳什均衡,18,华长生制作,再考虑第二步：,Smith知道第三步Tom会选择“不 引爆”,因此比较了“付”和“不付”的 支付后，Smith应该选择“不付”,最后考虑第一步：,Tom知道Smith第二步会选择 “不付”，因此Tom一开始就会 选择“不威胁”,因此可以得到该博弈的均衡,（不威胁、不付、不引爆）,这种从后面往前面推导的 方法称为逆向归纳法,我们先考虑第

10、三步：,Tom的行动“不引爆”比“引爆”更 占优，Tom应该选择“不引爆”,2.2 扩展式表述博弈的纳什均衡和逆向归纳法,扩展式表述博弈的纳什均衡,19,华长生制作,定理 (Zermelo,1913;Kuhn,1953):一个有限完美信息博弈 至少有一个纯战略纳什均衡.,如果一个扩展式博弈有有限个信息集 , 每个信息集上参 与人有有限个行动选择,并且这个博弈是完美信息的,那么一定 有一个纯战略纳什均衡,即,这个定理可是使用逆向 归纳法解释.,开发商博弈 : 假设这是 一个有限完美信息博弈.,自然N,大,(4,4),支付:(开发商A,开发商B),小,开发商A,开发商A,开发,开发,不开发,不开发

11、,开发商B,B,B,B,开发,不开发,开发,不开发,开发,不开发,开发,不开发,(8,0),(0,8),(0,0),(-3,-3),(1,0),(0,1),(0,0),有均衡的结果:,(市场需求大,A开发,B开发),(市场需求小,A开发,B不开发),扩展式表述博弈的纳什均衡,20,华长生制作,将这两个纳什均衡写成战略组合形式有四个:,(大,开发,开发,开发),(市场需求大,A开发,B开发),(市场需求小,A开发,B不开发),(小,开发,不开发,开发),(大,开发,开发,不开发),(小,开发,不开发,不开发),战略组合(大,开发,开发,不开发), (小,开发,不开发,不开发) 显然不合理,B的合

12、理战略在市场需求大时为开发,开发,而在 市场需求小时应为不开发,开发,那么如何将不合理的纳什均衡剔除呢?,扩展式表述博弈的纳什均衡,21,华长生制作,3.子博弈精炼纳什均衡,3.1 子博弈,22,华长生制作,如果开发商B在行 动时不知道开发商A的 选择,则开发商B有两个 信息集 , 且每个信息集 有两个决策结.,定义 : 由一个动态博弈 第一阶段以外的某阶段 开始的后续博弈阶段构 成的,有初始信息集和进 行博弈所需要的全部信 息,能够自成一个博弈的 一部分,称为原动态博弈 的一个“子博弈”.,子博弈精炼纳什均衡,23,华长生制作,条件(1)说明,“子博弈”的初始结x必定在原博弈的一个 单结信息

13、集中,即只有当参与人在原博弈中确切地知道博弈 进入一个特定的决策结时,该决策结才能作为一个子博弈的 初始结 . 如果一个信息集包含两个以上的决策结, 则这些决 策结都不能作为子博弈的初始结.,完美信息博弈由于所有信息集都是单结的,所以每个决 策结都可以开始一个子博弈.,条件(2)说明,“子博弈”中的信息集必须只含有子博弈中 的决策结,并且结构与原博弈一致.,子博弈精炼纳什均衡,24,华长生制作,3.2 子博弈精炼(完美)纳什均衡,开发商博弈有两个纯战略的纳什均衡：,(开发,开发,开发), (开发,开发,不开发),子博弈1,子博弈2,子博弈1的纳什均衡是开发商B “开发”,子博弈2的纳什均衡也是

14、开发商B “开发”,在扩展式表述的动态博弈中, 有的纳什均衡中可能会含有不可 信的战略被选择,在前面的例子中 我们已经发现,虽然这些战略构成 的战略组合是纳什均衡,但就这些 战略本身而言不符合参与人的自 身利益.,子博弈精炼纳什均衡,25,华长生制作,原博弈的另一个纳什均衡(开发,开发,不开发)中B的 战略为开发,不开发,即A开发则B开发,A不开发则B也不 开发,与子博弈2的纳什 均衡“开发”矛盾.,(开发,开发,开发)是既是原博弈也是子博弈的纳什均衡,原博弈的第一个纳什均衡(开发,开发,开发)中,B的 战略是开发,开发,即不管A是否开发,都选择开发,即B的 战略也是子博弈1和2的纳什均衡.,

15、(开发,开发,不开发)虽然什原博弈的纳什均衡,但并 不是子博弈的纳什均衡,即这是一个不合理的均衡,如何将扩展式博弈中博不合理的纳什均衡去除?,子博弈精炼纳什均衡,26,华长生制作,子博弈精炼纳什均衡和纳什均衡的区别就在于子博弈 精炼纳什均衡可以将含有不可信战略的纳什均衡排除.,在开发商博弈中,纳什均衡(开发,开发,开发)是子博弈 精炼纳什均衡,但(开发,开发,不开发)不是一个子博弈精炼 纳什均衡. (开发,开发,开发)也是原博弈中唯一可信的纯战略的 纳什均衡,子博弈精炼纳什均衡,27,华长生制作,3.3 用逆向归纳法求完美信息博弈的子博弈精炼纳什均衡,子博弈1,子博弈2,使用逆向归纳法可以求出

16、完全且完美信息动态博弈的纯 战略的子博弈精炼纳什均衡.,(开发,开发),(大,开发,开发) 和(小,开发,不开发),子博弈精炼纳什均衡,28,华长生制作,4.1 讨价还价博弈(一),Smith和Jones分100美圆 . 在谈判的第一回合中由Smith 提出方案,由自己留下S1 美圆,出价费用为零,Jones或者接受 (此时博弈结束) 或者拒绝并转入第二回合;第二回合由Jones 提出方案,出价费用为10美圆, Jones提出给Smith的数量为S2 美圆, Smith选择接受(此时博弈也结束)或拒绝并转入第三回 合;第三回合再次由Smith提出方案,出价费用为c美圆, Smith 提出自己留

17、下S3美圆.讨价还价谈判最多只进行三轮,如果三 轮都不能达成协议,则100$将全部给Jim. 如何就不同的出价费用c找到均衡的结果? (1) c=0; (2) c=80; (3) c=10;,4.子博弈精炼纳什均衡应用举例,29,华长生制作,(1),(2),(3),应用逆向归纳法求解：,首先考虑第三回合,Smith提出自己留下100美圆 Jones会接受,再考虑第二回合,Jones只能提出自己留下0美圆 而给Smith100美圆,否则Smith 一定是不接受,(100，-10),(0，-10),(100，-10),子博弈精炼纳什均衡应用举例,30,华长生制作,最后考虑第一回合,Smith提出自

18、己留下100美圆, 而Jones只能选择接受,不然第 二回合还要出10美圆的出价 费用,(1),(2),(3),(100，-10),(0，-10),(100，-10),(100，0),子博弈精炼纳什均衡应用举例,31,华长生制作,(1),(2),(3),首先考虑第三回合,Smith提出自己留下100美圆 Jones会接受,再考虑第二回合,Jones只能提出自己留下80美圆 而给Smith20美圆,否则Smith 一定是不接受,(20，-10),(-80，-10),(20，70),子博弈精炼纳什均衡应用举例,32,华长生制作,最后考虑第一回合,Smith提出自己留下30美圆, 而Jones只能选

19、择接受,不然第 二回合还要出10美圆的出价 费用,(20，70),(30，70),(1),(2),(3),(20，-10),(-80，-10),子博弈精炼纳什均衡应用举例,33,华长生制作,(1),(2),(3),首先考虑第三回合,Smith提出自己留下100美圆 Jones会接受,再考虑第二回合,Jones只能提出自己留下10美圆 而给Smith90美圆,否则Smith 一定是不接受,(90，-10),(-10，-10),(90，0),子博弈精炼纳什均衡应用举例,34,华长生制作,最后考虑第一回合,Smith提出自己留下100美圆, 而Jones只能选择接受,不然第 二回合还要出0美圆的出价

20、 费用,(100，0),(90，0),(1),(2),(3),(90，-10),(-10，-10),子博弈精炼纳什均衡应用举例,35,华长生制作,思考： 1. 如果Jones是一个非常情绪化的人，博弈的结果会如何?,将4.1中的讨价还价博弈的条件改变如下:Smith和Jones 分100美圆 . 谈判的次序与讨价还价一样,出价费用都是零, 但是每一回合谈判后,总资金的价值都会降低,贴现因子为, 即 第一回合如果Jones选择拒绝,第二回合由Jones给Smith的 数量为S2 , 自己留下100- S2 , 但二人实际所得分别为S2 和 (100-S2 ) ,依此类推,此博弈得均衡结果如何?

21、(贴现),子博弈精炼纳什均衡应用举例,36,华长生制作,4.2 讨价还价博弈(二),一个公司的管理层和工会之间的关系往往比较紧张,经常 为利益的分配或薪水问题进行谈判,双方以裁员或罢工相威胁, 甚至有时会贻误商机 .,我们设想有一家拥有自然资源的公司比如一家夏季度假 酒店,每年只有101的旺季,其他时间没有客人.在旺季中每开门 营业一天酒店就赚取1000$的利润,但在旺季开始之际,管理层 与工会之间就利益分配问题发生纠纷而进行谈判.工会首先提 出自己的要求,管理层要么同意,要么不同意并且于第二天提出 反建议.酒店只能在达成协议后才能开业.,分析谈判能否达成双方都接受的协议(纳什均衡)?,我们依

22、然使用逆向归纳法.,子博弈精炼纳什均衡应用举例,37,华长生制作,1 2 3 4 5 100 101,工会 管理层 工会 管理层 工会 管理层 工会,1000 1000 0 0 1000 500 1000 500 2000 667 1000 333 2000 500 2000 500 3000 600 2000 400 50000 500 50000 500 51000 505 50000 495,子博弈精炼纳什均衡为工会每天获得505$,管理层获得495$.,工会每一次提出建议都具有一个优势, 因为它是最后一个提出建议的一方.,子博弈精炼纳什均衡应用举例,38,华长生制作,思考： 1. 如果

23、讨价还价(二)中,在工会与管理层谈判期间,工会成员 可以出去打工,每天收益300$,谈判结果将会怎样? 2. 如果谈判期间,管理层可以发动不愿罢工的工人维持酒店 的营业,但每天的利润只有500$,谈判结果又会怎样? “以上两个问题结果反映的是:谁能在没有协议的情况下过 得越好,谁就能从讨价还价的利益大饼中分得更大一块.” 3. 如果谈判的建议只能又管理层一方提出,均衡的结果是什 么? 4. 如果管理层和工会对利润价值的看法不一样,假如管理层 认为1$现金一周后价值1.02$,而工会认为只有1.01$,均衡 结果又将是什么?,子博弈精炼纳什均衡应用举例,39,华长生制作,4.3 轮盘赌,策略思维

24、的作者之一的巴里.奈尔伯夫在毕业的时候 参加了剑桥大学的五月舞会,其中活动的一部分是到一个赌场 下注,舞会结束时收获最大的人将获得下一年度的舞会入场券, 开始时每人有20英镑的筹码,到了最后一盘轮盘赌下注的时候 巴里手里已经有了700英镑的筹码,独占鳌头,排第二的是一位 拥有300英镑的小姐,该小姐提出分享入场券,但巴里拒绝了.,轮盘赌规则:输赢取决于轮盘停止转动时小球落在什么地方,一 般轮盘上有刻有0到36的37个格子,若小球落在0算庄家赢.常见 玩法有赌小球落在奇数还是偶数格子里,赔率一赔一;赌小球落 在3的倍数的格子里,赔率一赔二.,该小姐有没有赢的可能?,子博弈精炼纳什均衡应用举例,4

25、0,华长生制作,如果小姐先下注,轮盘赌,小姐,奇偶300,3的倍数300,奇偶,3的倍数,如果小姐押奇偶300英镑, 赢获得600英镑,输则为0;,巴里只需观望即可获胜.,因此小姐只能押3的倍数 300英镑,赢获得900英镑, 输仍然为0;,巴里该怎么办?,巴里只要同样将300英镑押在3的倍数上,所以她只能寄希望于巴里先下注,如果巴里押200英镑在奇数上,她又该怎么办?,她只能将300英镑押在偶数上!,实际结果是小姐押300英镑在3的倍数,而巴里押200在偶数上,后动优势,子博弈精炼纳什均衡应用举例,41,华长生制作,4.4 斯塔克尔博格(Stackelberg)寡头竞争模型(产量模型),19

26、34年,在完全信息静态博弈中,我们介绍了古诺特(Cournot)的寡 头产量竞争模型,两个寡头同时确定产量.,如果在市场上存在两个厂商,厂商1是市场上的领头企业, 首先选择产量,厂商2在观察到厂商1的产量后,再确定自己的产 量 . 这个博弈显然是完全且完美信息动态博弈 .,子博弈精炼纳什均衡应用举例,42,华长生制作,能否用博弈树表述？,仍然使用逆向归纳法均衡,子博弈精炼纳什均衡应用举例,43,华长生制作,子博弈精炼纳什均衡应用举例,44,华长生制作,在Cournot模型中，本博弈的两个反应函数为,这不是纳什均衡,在Stackleberg模型中, 总产量增加了,总利润 减少 ; 厂商1的产量增

27、 加,利润也增加,厂商2 则相反,产量和利润均 减少 . 这种现象称为 “先动优势” . 如果将选 择产量改为选择价格, 结果将会怎样?,子博弈精炼纳什均衡应用举例,45,华长生制作,不稳定因素:,子博弈精炼纳什均衡应用举例,46,华长生制作,4.5 进入威慑(Entry Deterrence),工业组织中有一个老问题:一个在位的垄断者是否能通过 威胁引发价格战来阻止新公司进入市场以维持自己的垄断地 位, 这种思想遭到了芝加哥学派学者的猛烈抨击, 认为价格战 给在位者带来的损失大于和进入者合作的损失,博弈论可以作 出推理.,博弈参与人为进入者和在位者,博弈顺序为进入者选择进 入或不进入;如果进

28、入者进入,在位者选择是与进入者合作还是 使用大幅度降价来斗争 . 我们对支付作出假设:在垄断价格上, 市场利润为300;在斗争价格上,市场利润为0;双寡头竞争(合作) 时市场利润为100 , 两家平分 .,进入者战略空间:进入、不进入,在位者战略空间:进入者进入合作、进入者进入斗争,子博弈精炼纳什均衡应用举例,47,华长生制作,该博弈的有两个纳什均衡:,(进如者不进入,在位者斗争) (进入者进入,在位者合作),因为(进入者不进入,在位者斗争) 不是子博弈的纳什均衡,因此是不可信的纳什均衡,即在位者的威慑不可信.,如果在位者在进入者进入之前声称 如果有进入者进入,一定斗争,进入者 是否还会选择进

29、入?,进入者将不会理会在位者的威慑,子博弈精炼纳什均衡应用举例,48,华长生制作,5.重复博弈与民间定理(无名氏定理),某连锁机构在20个城市开设有分店,现在该机构试图阻止 竞争对手进入这20个市场,即上节4.5中的“进入威慑”博弈就会 重复进行20次 . 根据4.5中,竞争对手如果只是进入其中一个市 场,在位者选择的应该不是斗争而是合谋,但是,该连锁结构为了 阻止竞争者进入其他19个市场 , 因而现在的结果可能不同于只 有一个市场的结果.,5.1 连锁店悖论、重复囚徒博弈和有限次重复博弈,这个形式的博弈称为重复博弈,分有限次和无限次两种.,这种重复博弈的均衡是什么?,1.连锁店悖论(Selt

30、en ,1978),49,华长生制作,如果竞争者已经进入了19个市场(在位者可能选择了斗 争,也可能选择了合作),在最后一个市场,竞争双方意识到他 们所在的子博弈与一次性的“进入威慑”博弈是一样的:进入 者总是选择进入,而在位者总是选择合作 .,我们使用逆向归纳法推导下去,在第19个市场,双方知道, 不管双方选择什么行动,第20个市场都是“进入者进入,在位者 合作”,因此在第19个市场,“进入者一定会选择进入,而在位者 一定选择合作”,依此类推,在所有的市场,进入者都将选择进 入,而在位者则都将选择合作 .,这与我们前面在位者将会在第一个市场选择斗争建立威 慑的想法相矛盾,称为“连锁店悖论”.

31、,进入者总是选择“进入”而在位者总是选择“合作”是唯一 的子博弈精练纳什均衡.,重复博弈与民间定理,50,华长生制作,2.重复囚徒困境,如果将囚徒困境博弈重复进行20次,会发生什么?,显然囚徒们更希望大家都能选择抵赖,但在个体理性的 前提下,这种结果会发生吗?,在最后一轮即第20次博弈时,情况与一次博弈的囚徒困 境是一样的,因此囚徒们都会选择最后一论子博弈的纳什均 衡即“坦白”;,在第19次博弈时,囚徒们知道在最后一轮大家都会选择 “坦白”, 因此会认为在第19次建立声誉是毫无意义的,也会选 择“坦白”;,逐次递推下去,唯一的子博弈精练纳什均衡为两人每依 次都选择“坦白”.,重复博弈与民间定理

32、,51,华长生制作,连锁店悖论和重复囚徒困境这两个重复博弈都有以下 共同点:,(1) 都进行了有限次的重复;,(2) 两个重复博弈的基本博弈都有唯一的纳什均衡;,两个重复博弈都有唯一的子博弈精练纳什均衡,并且 是将基本博弈的纳什均衡重复而成.,定理:如果G是一个基本博弈,并且只有唯一的纳什均衡,那么 将G重复进行n次的有限次重复博弈也只有一个子博弈精练 纳什均衡,并且结果是由G的纳什均衡复合而成.,这个定理成立有两个必备的条件:重复的次数有限和基本 博弈只有唯一的纳什均衡.,另外在前面的两个博弈中还提到了两个词:威慑和声誉,重复博弈与民间定理,52,华长生制作,5.2 无限次重复博弈和无名氏定

33、理,“连锁店悖论”中得出的均衡与是进行一次的“进入威慑” 博弈是一致的，与我们所观察到的现实是不一致的. 出现这种 结果的原因是由于博弈的重复次数有限造成的,毕竟一个经济 实体不会期望在有限的时间内结束!重复囚徒困境的结果也是 一样的.,在有限次博弈中,囚徒们 总是会选择“坦白”,但在无限次博弈中,囚徒 们会不会选择合作呢?,囚徒们的战略是什么?,冷酷战略 针锋相对战略,重复博弈与民间定理,53,华长生制作,冷酷战略(Grim strategy):,(1) 开始时选择“抵赖”;,(2) 一直选择“抵赖”,除非有人选择了“坦白”;如果有人 选择“坦白”,自己就永远选择“坦白”.,由于是无限次博弈

34、,开始时选择“抵赖”,以表明自己合作的 意向(声誉),直至有人不合作为止.并给予不合作者以惩罚.,在无限次重复囚徒博弈中,如果囚徒A选择了“冷酷战略”, 那么“冷酷战略”也是囚徒B的最优战略,如果他选择合作即选 择抵赖,会永远得到(抵赖,抵赖)的较高支付;而如果选择“坦白” 只能得到一次 ( 抵赖 , 坦白) 的很高支付,但以后最多只能得到 (坦白,坦白)的较低支付.,冷酷战略是一种可信的“惩罚威胁”或者“报复”,在无穷次 重复博弈可能会促成参与人之间的合作.,冷酷战略是无限次囚徒博弈的子博弈精炼纳什均衡.,开始时友好地建立自己的声誉,对破坏合作者进行惩罚,重复博弈与民间定理,54,华长生制作

35、,冷酷战略是子博弈纳什均衡的证明:,假设囚徒A选择了冷酷战略, 囚徒B应该选择什么战略呢?,如果囚徒B在某一期不选择“抵赖”而是选择“坦白”,那么B 在这一期的支付为0而不是-1,但是由于囚徒A选择了冷酷战略, 以后都选择“坦白”,因此囚徒B在以后的支付最多为-8而不是-1, 由于博弈的次数无限,囚徒B如果一开始就选择了“抵赖”,他就不 会再选择“坦白”,以后也不会,只要A不“坦白”,但如果囚徒B在一开始就选择了“坦白”,由于囚徒A执行冷 酷战略,那么囚徒B在以后也将永远选择“坦白”,即自己惩罚自己.,因此,如果A执行冷酷战略,B也将执行冷酷战略,反过来,如 果B执行冷酷战略,A也将一致,即冷

36、酷战略是“纳什均衡”.,重复博弈与民间定理,55,华长生制作,由于博弈重复无限次,因此从任意一期开始的子博弈与 原博弈完全一致,所以冷酷战略也是任意一个子博弈的纳什 均衡.,冷酷战略是无限次囚徒博弈的子博弈精炼纳什均衡.,虽然冷酷战略是一种可信的“惩罚威胁”或者“报复”,在无 穷次重复博弈中, 惩罚“坦白”可能会促成囚徒们之间的合作, 但是不是所有惩罚“坦白”的战略都能促成囚徒们之间的合作, 如“针锋相对”战略.,冷酷战略的结果也表明,在无限次的博弈中,任何机会主 义的选择都将可能带来更大的损失 .,但是冷酷战略并不是无限次囚徒博弈唯一的子博弈精炼纳什均衡.如果双方选择“总是坦白”战略也将是一

37、个子博弈纳什均衡, 因为在对方选择“坦白”的情况下, 不可能选择“抵赖”.,重复博弈与民间定理,56,华长生制作,针锋相对战略(Tit-for-tat strategy):,(1) 开始时选择“抵赖”;,(2) 以后每一期选择与其他参与人上一期相同的行动.,针锋相对战略不是囚徒博弈的子博弈纳什均衡.,无限次重复博弈的无名氏定理(民间定理):,重复博弈与民间定理,57,华长生制作,无名氏定理的几何解释:,无名氏定理说明:子博弈均精炼什均衡不只一个, 当然更多的是混合形式的,重复博弈与民间定理,58,华长生制作,5.3 声誉与单边囚徒困境博弈,双边博弈:是指每个参与人的战略空间都是相同的,并且支付

38、 也是对称的静态博弈.,单边博弈:指战略或行动、支付不对称的博弈.,如双寡头博弈和原始的囚徒困境博弈,如单边囚徒困境博弈和产品质量博弈,重复博弈与民间定理,59,华长生制作,单边囚徒困境到产品质量博弈的转化,重复博弈与民间定理,60,华长生制作,产品质量博弈的纳什均衡为,(低质量,抵制),可以理解为一个参与人拒绝 与其他参与人打交道,一个理性的消费者更热衷于购买熟悉的厂家的高质量产品,如一个消费者拒绝购买克莱斯勒公司的汽车,因为他知道 克莱斯勒公司有一次在汽车里程表上作弊.,生产者要生存,必须建立自己的“声誉”,愿意与消费者“合 作”,生产“高质量”的产品.,重复博弈与民间定理,61,华长生制

39、作,重复博弈与民间定理,62,华长生制作,5.4 不合作的战例,Spirit航空公司和西北航空公司 这是美国的两家航空公司.1995年之前,西北航空经营着 底特律至费城的航线,单程平均票价高于170美圆.1995年12 月Spirit航空公司涉足该航线,每天有一趟往返航班,开始时单 程平均票价为49美圆. 1996年, 6月20日西北航空公司将该航 线所有票价降至49美圆,并且将其大部分运力集中于该航线, 增加了30%的客位.同见9月30日, Spirit航空公司宣布退出该 航线.1997年第一季度,西北航空公司将该航线的单程平均票 价提高至230美圆,并且为该航线提供的客位也下降.,重复博弈

40、与民间定理,63,华长生制作,重复博弈与民间定理,64,华长生制作,5.5 无限次重复博弈的产品质量模型(参与人不固定),这是一个生产者与消费者之间的博弈,唯一的是纳什均衡为,(低质量,抵制),如果这是一个无限次重 复博弈,情形将如何?,假设生产者是长期的产品提供者,但消费者是不同的,假定每 次每个消费者只购买一件产品,不知道自己购买的产品的质量,但 知道前面的消费者购买的产品的质量.,生产者和消费者将如何决策?,重复博弈与民间定理,65,华长生制作,生产者的战略:,如果生产低质量的产品, 被消费者购买,可以得到8个单 位的较高支付 , 但以后将失去 所有的消费者,支付永远为零.,如果总是生产

41、高质量的产品,即使消费者不购买,支付也不 会比生产低质量产品得到的支付差,并且消费者预期生产者会 继续生产高质量的产品(声誉)，因此会选择购买,从而总是得到 7个单位的较高支付.,消费者的战略:,如果生产者生产高质量的产品 , 消费者会选择购买,由于不 知道自己购买的产品的质量,因此只有生产者持续生产高质量的 产品,建立声誉,消费者才会选择持续购买. (冷酷战略),重复博弈与民间定理,66,华长生制作,因此,该博弈子博弈精炼纳什均衡为:,(生产者总是生产高质量的产品,消费者总是购买),不过,这不是唯一的子博弈精炼纳什均衡,如,(生产者总是生产低质量的产品,消费者总是抵制),思考:为什么一个大商

42、场,一般不会销售假冒伪劣商品,而一个走 街串巷的小贩却总是销售假冒伪劣的货物?,关于更详细的产品质量博弈的模型是Klein和Leffler在 1981年建立的.见艾里克.拉斯缪森的博弈与信息博弈论 概论P141,北京大学出版社,重复博弈与民间定理,67,华长生制作,思考题,一、教材:P138 1. 3.,二、一美圆的价格,美国耶鲁大学教授Martin Shubik设计了一个游戏:他拿 出一张一美圆来拍卖,无底价,每次叫价的增幅为5美分,出价 最高者得到这一美圆,但是规则是叫价最高和次高者都要向 拍卖者支付所叫价的费用. 1.假如Airy和John各有2.5美圆,并且都互相知道对方有 2.5美圆

43、,他们俩参加Shubik的游戏,请分析结果. 2.这个博弈有均衡吗?,68,华长生制作,三、海盗分金问题,海盗，大家听说过吧。这是一帮亡命之徒，在海上抢人钱财，夺人性命，干的是刀头上舔血的营生。在我们的印象中，他们一般都瞎一只眼，用条黑布或者讲究点的用个黑皮眼罩把坏眼遮上。他们还有在地下埋宝的好习惯，而且总要画上一张藏宝图，以方便后人掘取。不过大家是否知道，他们是世界上最民主的团体。参加海盗的都是桀骜不驯的汉子，是不愿听人命令的，船上平时一切事都由投票解决。船长的唯一特权，是有自己的一套餐具-可是在他不用时，其他海盗是可以借来用的。船上的唯一惩罚，就是被丢到海里去喂鱼。,现在船上有若干个海盗，

44、要分抢来的若干枚金币。自然，这样的问题他们是由投票来解决的。投票的规则如下：先由最凶猛的海盗来提出分配方案，然后大家一人一票表决，,69,华长生制作,1. 如果有50%或以上的海盗同意这个方案，那么就以此方案分配，如果少于50%的海盗同意，那么这个提出方案的海盗就将被丢到海里去喂鱼，然后由剩下的海盗中最凶猛的那个海盗提出方案，依此类推。试就10个海盗100枚金币给出你认为合理的方案；,2.改变一下规则，投票中方案必须得到超过50%的票数（只得到50%票数的方案的提出者也会被丢到海里去喂鱼），那么如何解决10个海盗分100枚金币的问题？,*3.不改变规则，如果让500个海盗分100枚金币，会发生什么？ *4.如果每个海盗都有1枚金币的储蓄，他可以把这枚金币用在分配方案中，如果他被丢到海里去喂鱼，那么他的储蓄将被并在要分配的金币堆中，这时候又怎样？,