第七讲重复博弈

Size: px

Start display at page:

Download "第七讲重复博弈"

上肴禾
5 years ago
Views:

1 信息与博弈校通识课 (GEN14251L) 第六讲重复博弈张少强

2 重复博弈 (repeated game) 动态博弈的另一种特殊但是非常重要且常见的类型就是所谓的重复博弈重复博弈是指同样结构的博弈重复多次, 其中的每次博弈称为阶段博弈 (stage game) 以囚徒困境为例, 如果每次判刑不是很重, 那么, 两个囚徒在刑满释放之后再作案, 作案之后再判刑, 释放之后又作案, 如此等等, 他们之间进行的就是重复博弈, 其中每次作案就是一个阶段博弈

3 生活中重复博弈的例子当你到菜市场去买菜, 当你担心上当受骗而犹豫不决时, 摊主便会对你说 : 你放心好了, 我天天在这里卖菜, 不会骗你的, 如果菜不好你回来找我! 他强调自己天天在这里卖菜, 你通常便会放下心与之成交因为他这句话翻译成博弈论的语言就是我跟你是重复博弈而你到车站旅游景点买东西往往质次价高, 其原因就在于买卖双方很少有重复博弈的机会 ( 一锤子买卖 )

4 生活中重复博弈的例子在相互联系紧密的人际关系中, 人们普遍比较注意礼节道德, 因为合作和协调对大家都有好处 ; 但是, 我们又常常见到这样的消息 : 在公共汽车上, 两个陌生人会为一个座位争吵, 为什么会发生这种事情? 原因何在? 在公共汽车上, 两个陌生人吵架, 因为彼此知道这是一次性博弈, 吵过了以后谁也不会再遇到谁 ; 可是如果相互认识, 就会相互谦让, 因为他们知道以后还有碰面甚至交往的可能, 即使发生争吵, 通常会在在争吵中留有余地, 因为二人日后还会有重复博弈

5 为什么研究重复博弈? 长期反复合作与竞争的关系存在 ( 例 : 两企业的长期竞争, 长期协议, 回头客 ); 长期关系比短期关系更加复杂, 考虑当前也得兼顾未来 ; 一般动态博弈环环相扣 ; 长期关系中, 各个阶段之间的相互独立性 ; 长期关系需要考虑信誉信任 ; 重复博弈不是阶段博弈的简单叠加, 必须把重复博弈过程作为整体进行研究

6 基本概念重复博弈是同样结构的博弈重复多次, 每次为阶段博弈重复博弈可以分为有限次重复博弈无限次重复博弈, 随机结束的重复博弈注意 : 重复博弈与一般动态博弈的区别, 每个阶段都有得益, 每个阶段的博弈方和博弈内容都相同

7 有限次重复博弈给定一个基本博弈 G( 可以是静态博弈也可以是动态博弈 ), 重复进行 T 次 G, 并且在每次重复 G 之前各博弈方都能观察到以前的博弈结果, 这样的博弈过程称为 G 的 T 次重复博弈, 记为 G(T) 而 G 则成为 G(T) 的原博弈,G(T) 的每次博弈称为 G(T) 的一个阶段

8 无限次重复博弈无限次重复博弈 : 一个基本博弈 G 一直重复博弈下去的博弈, 用 G( ) 表示如果某个重复博弈没有可以预见的结束时间, 各博弈方主观上认为博弈会不断进行下去, 就可以看作是无限重复博弈随机结束的重复博弈 : 重复的次数虽有限, 但重复次数或博弈结束时间却是不确定的

9 策略子博弈策略 : 重复博弈环境下, 参与人的策略非常复杂一般地, 我们定义参与人的一个策略是在博弈的每个阶段针对之前阶段的博弈结果而制定的行动计划 ; 子博弈 : 从某个阶段开始, 包括此后所有的重复博弈部分, 仍然可以用逆向归纳法来分析对于有限重复博弈, 可以寻找子博弈完美均衡均衡路径 : 由每个阶段博弈方的行动组合串联而成重复博弈的路径数目是 : 行动组合数的 T 次幂重复博弈使博弈有了更多的可能, 分析重复博弈就是要在这些路径中找出具有稳定性的均衡路径, 并分析它们的效率意义

10 重复博弈的支付 / 收益重复博弈中参与人的行动策略选择不可能只考虑本阶段的支付, 必须兼顾其他阶段的支付, 必须考虑整个重复博弈过程的总体情况总支付 / 总收益 : 参与人各次重复支付的总和平均支付 / 收益 : 总支付除以重复次数

11 威胁与承诺动态博弈中涉及的一个重要问题是, 博弈过程中威胁和承诺如何影响博弈的进程重复博弈所关心的议题也与之相似 : (1) 将来可信的威胁或承诺如何影响到当前的行动? (2) 在一次博弈中无法实现的均衡, 在重复博弈中能否实现?

12 有限次重复博弈分类 1. 两人零和博弈的有限次重复博弈 2. 惟一纯策略纳什均衡的有限次重复博弈 3. 多个纯策略纳什均衡的有限次重复博弈

13 1. 两人零和博弈的有限次重复博弈猜硬币博弈猜硬币方正面反面盖硬币方正面反面 -1, 1 1, -1 1, -1-1, 1 零和博弈是严格竞争的, 重复博弈并不改变这一点重复零和博弈不会创造出新的利益

14 1. 两人零和博弈的有限次重复博弈以零和博弈为原博弈的有限次重复博弈与猜硬币博弈的有限次重复博弈一样, 博弈方的正确策略是重复一次性博弈中的纳什均衡策略可用逆推归纳法来证明可以推广到非零和或多个博弈方, 但博弈方的利益严格对立, 没有纯策略纳什均衡的其他严格竞争博弈中产生原因 : 利益关系严格对立, 矛盾不可调和

15 2. 惟一纯策略纳什均衡的有限次重复博弈情形一 : 惟一纯策略纳什均衡是帕累托效率意义上的最佳策略组合 ; 情形二 : 原博弈惟一的均衡没有达到帕累托效率, 存在通过合作进一步提高效率的可能性, 例如 : 囚徒困境博弈

16 考察下列博弈 2 对抗合作对抗 1 合作 1, 1 5, 0 0, 5 4, 4 该博弈存在唯一的纳什均衡, 即 ( 对抗, 对抗 ) 同时注意到, 该博弈还存在一个高效均衡 ( 合作, 合作 ), 高效均衡对应着一种合作行为为什么高效的均衡不是纳什均衡? 如何保证这一高效均衡能够实现?

17 两次重复博弈假设将上述博弈重复两次, 用逆向归纳法, 先找第二阶段的纳什均衡, 再找第一阶段的纳什均衡 1 U 对抗 D 合作第二阶段 L 对抗 2 R 合作 1,1 5,0 0,5 4,4 1 U 对抗 D 合作第一阶段 L 对抗 2 R 合作 1+1, , , ,4+1

18 有限次重复博弈运用逆向归纳法, 可以发现上述重复博弈的子博弈完美纳什均衡为 : 在每次博弈中, 参与人 1 都选择对抗, 参与人 2 都选择对抗这说明 : 在两次重复博弈中, 高效的均衡仍无法实现同样可证明 : 在 n 阶段 ( 有限次 ) 重复博弈 ( 即博弈重复 n 次且每次博弈开始时, 前面博弈的结果都已知 ) 中, 高效的均衡同样无法实现

19 有限次重复的囚徒困境悖论假定进行两次重复博弈, 双方看到第一次博弈的结果后再进行第二次, 最后支付是两阶段各自支付的和

20 有限次重复的寡头削价竞争有唯一纯策略纳什均衡 (70,70) 有限次重复的结果仍然是 ( 低价, 低价 )

21 为什么出现悖论? 每次人际交往其实都可以简化为两种基本选择 : 合作还是背叛在人际交往中普遍都存在囚徒困境 : 双方明知合作会带来双赢, 但理性的自私和信任的缺乏缺导致合作很难形成特别是一次性博弈必然加剧选择背叛的决心背叛是个人的理性选择缺导致集体的非理性现实中, 如果多次重复博弈, 人们可以通过长期的合作契约和交往中来纠正人们的短期行为 ( 例如开会迟到?8:00 开会总有人迟到, 即使为了防止迟到, 故意通知 7:45 开会, 过段时间还是会有人迟到? 必须对迟到的惩罚而不是浪费不迟到的人的时间 ) 逆向归纳法出现的结果, 现实发生的几率很小

22 再看一个例子 : 连锁店悖论假定在位者在不同的市场上有 20 家连锁店, 进入者试图进入这些市场如果进入者进入了每一个市场, 此时博弈就变成了 20 次重复博弈当进入者进入第 1 个市场时, 在位者应该如何反应呢? (5,5) 默许进入在位者商战 (-2,3) 潜在进入者不进入 (0,10)

23 连锁店悖论逆向归纳, 倒数第二阶段默许 (5+5,5+5) 进入在位者商战 (-2+5,3+5) 潜在进入者不进入 (0+5,10+5) 子博弈完美纳什均衡为 : 在位者在每一个市场选择默许, 进入者在每一个市场选择进入

24 2. 惟一纯策略纳什均衡的有限次重复博弈定理 : 如果阶段博弈 G 有唯一的纯策略纳什均衡, 则对任意有限的 T, 重复博弈 G(T) 有唯一的子博弈完美均衡解, 即 G 的纳什均衡结果在每一个阶段重复进行总支付是原博弈的 T 倍

25 但是好像也有问题? 理论和实践的直觉矛盾 ; 现实中寡头之间的价格战并不十分普遍, 是不容易重复打价格战的囚徒困境重复 200 次, 实验结果表明当一个囚徒选择抵赖, 另一个坦白的话, 下一次博弈时, 都会选择抵赖泽尔腾在 1978 年研究连锁店悖论发现, 实际中, 对开头几个市场进入者, 在位者不计代价的打击上述问题的症结与此前讲的蜈蚣博弈类似, 在于较多阶段的动态博弈中逆向归纳法的适用性

26 其它解释虽然博弈次数有限, 但是我们不知道具体是多少, 类似一个无限次数的重复博弈类似于无限 ( 例如 : 人的生命 ) 即使我们知道准确的结束合作关系的时间, 比如劳动合同常常有明确的时间期限, 但我们并不是从上班第一天就开始偷懒, 是因为面对足够长的合同期, 偷懒被开除而损失如此长期的一笔工资收益是不划算的所以, 员工仍采取了合作的态度, 但是的确可以发现, 随着终止合同离开雇主的日期越来越近, 员工的努力程度在打折扣有限次博弈开始起作用了这个有限博弈中的合作或对抗会给你进入另外一个博弈带来影响, 必须考虑自己的表现, 例如考虑应聘到其他企业工作的影响

27 3. 多个纯策略纳什均衡的有限次重复博弈两市场博弈的重复博弈 ( 重复两次 ) A 厂商 2 B 厂商 1 A B 3,3 4,1 1,4 0,0 两市场博弈此博弈有 2 个纯策略纳什均衡 (1,4) 和 (4,1) 和混合策略纳什均衡概率 (0.5, 0.5) 平均收益 : (A,B)+(A,B) (1,4) 或 (B,A)+(B,A) (4,1) 连续两次采用混合策略 (2,2) 轮换策略 (A,B)+(B,A) 或 (B,A)+(A,B) (2.5,2.5) 一次纯策略 + 一次混合策略 (1.5,3) 或 (3,1.5)

28 3. 多个纯策略纳什均衡的有限次重复博弈考虑三次重复博弈各策略组合子博弈纳什均衡路径 : 1. 由原博弈的纳什均衡组合而成的路径, 如采取轮换策略 ( 在上述的协调博弈中, 双方轮换采取纯纳什均衡策略, 路径为 (A,B),(B,A),(A,B).), 每阶段的平均支付为 (4+1)/2=2.5, 高于混合策略的支付触发策略 : 博弈方首先采取合作行为, 如果发现对方没有合作, 那么在后续阶段的博弈中采取不合作策略进行惩罚

29 A 厂商 2 B 厂商 1 A B 3,3 4,1 1,4 0,0 两市场博弈若触发策略 ( 第二阶段触发 ) 的设计为 : (1) 厂商 1 的策略是第一阶段合作 A, 如果发现对方采取 B 不合作, 则第二阶段采取不合作的 B 策略惩罚, 否则第二阶段继续合作 ; 第三阶段无条件采取 B 策略 (2) 厂商 2 的策略是第一阶段合作 A, 如果发现对方采取 B 不合作, 则后续两个阶段一直采取不合作的 B 策略 ; 如果发现对方采取合作 A, 则第二阶段采取不合作 B, 第三阶段采取合作 A 那子博弈路径为 (A,A), (A,B), (B,A) 为子博弈纳什均衡

30 多个纯策略纳什均衡的有限次重复博弈的收益范围由于具有多个纳什均衡的重复博弈可以设计多种策略组合, 因此存在许多收益差异很大的子博弈完美纳什均衡在双方缺乏沟通的情况下, 结果具有不确定性但是, 可以设计包含报复机制的触发策略, 实现收益较高的均衡个体理性收益 : 不管对方采取何种行动, 只要自己的行动合理就可保证实现的收益可实现收益 : 各纯策略组合支付的平均收益并不一定是均衡策略的组合收益例如 (3,3) 即每次均合作也是可实现的收益

31 有限次重复博弈的民间定理用 w i 记博弈方 i 在一次性博弈中最差的均衡收益, 则 W=(w 1,w 2,,w n ) 记为各博弈方的 w i 构成的支付数组例如上例中 W=(1,1), 是 (4,1) 和 (1,4) 纯策略均衡和 (2,2) 混合策略均衡的最小数形成的数组定理 : 将一次性博弈中最差的均衡收益数组记为 W, 如果原博弈 G 的的一次性博弈有收益数组优于 W, 那么在有限次重复博弈 G(T) 中, 所有不小于个体理性收益的可实现收益至少有一个子博弈完美纳什均衡来实现

32 有限次重复博弈的民间定理厂商 (1,4) 帕累托效率最大 2 收益 (3,3) 触发策略最差均衡收益数组 (1,1) (4,1) 原博弈纯策略均衡的组合 0 厂商 1 收益民间定理揭示出 : 在有限次重复博弈中, 可以通过设计触发策略来实现阴影部分的收益阴影部分的收益都是可实现的收益

33 有限次重复博弈的民间定理民间定理表明, 在具有多个纳什均衡的有限次重复博弈中, 通过设计具有可信威胁的触发策略 ( 即在第一阶段采取合作行动, 当对方不合作时通过在后续阶段采取相应的不合作策略进行惩罚 ; 当对方合作时, 在最后阶段采取一次性原博弈的纳税均衡作为稳定的结局 ), 可以使得博弈方在重复博弈的过程中具有一定学习能力从而达到博弈的尽量多的收益

34 无限次重复博弈前面几个有限次重复博弈的例子 ( 重复的囚徒困境连锁店寡头削价等 ) 的每个阶段没有达到帕累托最优, 但存在通过合作进一步提高支付的可能性实际上, 要破解上述的悖论, 达到高效的均衡就要求助于无限次重复博弈无限次不一定真的无限, 只是不知道具体次数是多少, 没有明确的时间期限, 均可视为无限次重复由于逆向归纳法不适用无限次重复博弈, 我们使用顺向归纳法来分析无限次重复博弈中如何达成合作产生高效均衡的

35 无限次重复博弈达成合作的条件对博弈双方参与人形成一个长期利益优于短期利益的压力, 诱导双方采取合作为此, 我们需给出两个假设 : 假设一 : 折现因子 (discount factor) δ= 1 1+r, 0 < δ < 1 r 为折现率经济学家认为 : 人们喜欢现在的收入而不是未来的收入, 未来的收入 F 折现 ( 贴现 ) 成现在的收入 P = 1 F, n 为阶段数 (1+r) n 例如 : 年折现率 r=0.1, 三年后收入 1 个单位, 现 1 在折现为 P= 0.75 个单位 (1+0.1) 3 长期的利益化为短期利益就要折现

36 无限次重复博弈达成合作的条件假设二 : 博弈双方选择策略的原则是先试探合作, 如果对方不合作, 则采取对抗 : 即自己先选择合作, 如果一旦观察到对方选择对抗, 则自己从下一个阶段开始永远选择对抗在上述两个假设下, 合作的充分必要条件是 : 对任何参与人, 他在第 t 阶段选择 ( 前 t-1 一直合作 ) 对抗得到的全部好处, 将不如在第 t 阶段继续维持合作的好处

37 举例 : 无限次重复 2 对抗合作对抗 1 合作 1, 1 5, 0 0, 5 4, 4 假设一个参与人在第 t 阶段决定是否对抗, 根据上述 2 个假设, 说明在前 t-1 个阶段双方都是合作的, 若 t 阶段他选择对抗, 对方选择合作, 那从 t+1 阶段起对方也选择对抗到底若 t 阶段他选择合作, 对方也选择继续合作设折现因子为 δ

38 举例 : 无限次重复他在第 t 阶段选择对抗以后都对抗的总支付 v 1 = δ + δ δ t 2 + 5δ t 1 +1(δ t + δ t+1 + ) 他在第 t 阶段及以后继续合作的总支付 ( 永远合作 ) v 2 = 4(1 + δ + δ δ t 2 + δ t 1 +δ t + δ t+1 + ) 当 v 2 >v 1 时, 合作才能继续维持, v 2 v 1 = δ t 1 + 3(δ t + δ t+1 + ) = δ t 1 + 3δt 1 δ >0 解 δ> 1 4 所以, 只要折现因子 δ> 1 4, 合作就可以达成

39 无限重复博弈的策略选择这表明 : 参与人越注重长远的利益, 合作就越容易达成 ; 反之, 只注重眼前的利益的人, 合作越难以维持如果博弈参与人知道博弈次数, 他们在最后一定会选择相互背叛的策略但是当博弈参与人不知道次数, 参与人就会意识到, 当选择合作并达成默契时比选择背叛收益高时, 合作的动机就显现出来了

40 罗伯特阿克谢罗德竞赛实验 1984 年密西根大学政治系罗伯特阿克谢罗德 (Robert Axelord) 教授为了研究合作问题, 他组织了一次关于囚徒困境的不同策略的比赛得分矩阵如下 : 2 背叛 1 合作背叛合作 0, 0 4,-1-1, 4 2, 2 他邀请了 14 个参赛者把追求得分最多的策略写成计算机程序, 然后用单循环两两比赛, 以找出什么样的策略得分最高

41 罗伯特阿克谢罗德竞赛实验首先把 14 个队, 两两分组, 进行 200 次的重复博弈, 然后再重新分组, 直到两两比赛过实验的结果使教授大吃一惊, 因为竞赛的冠军获得者 --- 多伦多大学数学教授阿纳托拉帕波特教授提交的一报还一报策略, 该策略一点不高深, 而且非常简单一报还一报策略就是以牙还牙, 以其人之道, 还治其人之身他的特点是 : 第一次对局采用合作的策略, 以后每一步都紧随对方上一步的策略, 若上一次合作, 我这一次就合作, 若上一次背叛, 我这一次就选择背叛

42 罗伯特阿克谢罗德竞赛实验为了进一步验证第一轮游戏得到的结论, 教授邀请了更多人参与游戏, 第二次征集了 62 个程序, 结果, 第一名仍然是一报还一报策略这个策略能够反复赢得比赛, 因为它信奉针锋相对 (tit-for-tat) 法则, 即人不犯我, 我不犯人 ; 人若犯我, 我必犯人, 坚持有理有利有节的尺度并且用以下有规律可供遵循的行为特点将对手纳入长期合作的轨道上 :

43 一报还一报行为特点第一, 善良性, 即从不首先背叛 ; 第二, 可激怒的报复性, 对于对方的背叛行为一定要报复 ; 第三, 宽容性, 不能因为对手的一次背叛就没完没了地报复 ; 如果对方恢复合作, 你也要合作 ; 宽容性有助于重新恢复合作第四, 易于察觉的清晰性, 逻辑清晰, 使对手能够很轻易地发现你采取策略的规律, 并领会你的意图

44 罗伯特阿克谢罗德竞赛实验而输掉这个竞赛的策略, 总是在上述四个方面做得不够好比如竞赛者的脾气过于好, 总是以德报怨, 结果就被狡猾之徒反复地占便宜 ; 有些竞赛者不够宽容, 别人背叛一次他就不与对方再次合作, 从而使合作关系永久性断绝 ; 还有一些竞赛者太精于算计, 总是试图通过取巧来占别人的便宜, 这种人在与好脾气者的博弈中虽然大占便宜, 但与不宽容者的博弈中往往搬起石头砸自己的脚, 而从最后的总分来看, 他的小聪明总是得不偿失

45 带给我们的启示在博弈中, 城府很深兵不厌诈揣着明白装糊涂等并非上策 ; 在博弈中过分复杂的策略使得对手难于理解, 无所适从, 因而难以建立稳定的合作关系明晰的个性简练的作风坦诚的态度倒是制胜的要诀

46 你打我一拳, 我是不是应该马上踢你一脚? 有时候, 人们会对伤害选择立即报复当别人打你一拳, 你马上还他一脚, 这固然并不能减轻你已挨那一拳的疼痛, 而且用力踢回一脚通常也得不到快感那为什么还要针锋相对地坚决予以回击呢? 原因就在于, 打不还手只会让对手更加猖狂, 而只有回击才能遏制对方的进一步侵犯所以, 有些时候宽大为怀不一定好, 有些时候毫无回旋余地也不见得最佳, 人类互动世界的奇妙之处于此尽显

47 启示即使存在利益冲突, 但若有长期的合作利益, 人们的合作仍是可以达成的 ; 有必要选择眼光长远注重未来的人们为合作对象 ; 对目光短浅只注重眼前利益的人, 不可与其合作 ; 为了诱导对手合作, 自己不仅需要好斗, 也需要懂得宽恕, 并且让对手知道你爱憎分明也很重要 ;( 增加折现因子, 以加大未来的影响 ) 对于预计今后会经常碰面的人, 我们应从友善对待开始 ; 而对于那些想捞一票就走的人, 对他们的措施就是一次机会也不要给

幻灯片 1

幻灯片 1 第四讲 : 博弈的基本分析方法吴建设基本分析思路和方法上策均衡 2 严格下策反复消去法 3 划线法 4 箭头法上策均衡上策 : 不管其它博弈方选择什么策略, 一博弈方的某个策略给他带来的得益始终高于其它的策略, 至少不低于其他策略的策略智猪博弈中的小猪等待 ; 囚徒的困境中的坦白 ; 双寡头削价中低价上策均衡 : 一个博弈的某个策略组合中的所有策略都是各个博弈方各自的上策, 必然是该博弈比较稳定的结果

第七讲 重复博弈

第七讲重复博弈