这是第三套习题,对应 Unit 5 和 Unit 6,也就是第 23 讲到第 31 讲。一共 14 道题,每道题都有完整的解答。

这一部分的特点是:时间拉长了,同样的博弈要反复玩,玩的人还会学习、演化。算起来不再是"一次的均衡",而是"未来的影子有多长"“比例会往哪边走"“长期平均是多少”。

怎么用这套题

先做,再看。 拿一张纸,每道题先写下自己的答案,哪怕只是一个方向。写完再去看解答。没写就看,你看到的是"别人的答案”,不是"你的错误"。

难度。 每道题标了难度:

  • ★ 巩固:直接用一个定义,或者一步计算。
  • ★★ 标准:两三步,或者要自己把一段话翻译成式子。
  • ★★★ 挑战:要把几个想法拼在一起,或者里面藏着一个陷阱。

不需要任何工具。 所有题都可以用纸笔做出来(有几题需要解一个小的线性方程组,已经把数字挑得很小)。每道题的数字,我都另外验算过,验算过程不放在这里。

解答怎么写的。 每道题的解答分四步:思路、过程、答案、常见错误。

关于记号。 矩阵里每个格子写(行玩家的收益,列玩家的收益)。囚徒困境的收益统一用:(合作,合作)各 3;你背叛、对方合作,你 5、对方 0;(背叛,背叛)各 1。

题号 主题 对应讲
1 重复囚徒困境:触发策略与以牙还牙 第 23 讲
2 两期博弈:阶段博弈有两个均衡 第 23、24 讲
3 民间定理:哪些收益能维持 第 24 讲
4 声誉:先验与贝叶斯更新 第 25 讲
5 锦标赛:奖金差多大才够 第 25 讲
6 噪声下的长期平均 第 26 讲
7 零行列式策略 第 26 讲
8 鹰鸽与布尔乔亚 第 27 讲
9 复制子动态:猎鹿 第 28 讲
10 阈值与规范 第 29 讲
11 虚拟博弈 第 30 讲
12 遗憾匹配 第 30 讲
13 相关均衡:斗鸡 第 31 讲
14 判断题:哪些话是错的 综合

题目

第一部分 重复博弈(第 23–26 讲)

题 1(★★)触发策略与以牙还牙

重复的囚徒困境,每一轮的收益是上面说的 3、5、0、1。每一轮之后,博弈继续的"折现因子"是 δ(可以理解为:下一轮的 1 元,今天值 δ 元)。

(1)冷酷触发(一直合作,一旦有人背叛,永远背叛):δ 至少多大,才能维持"一直合作"?

(2)以牙还牙(第一轮合作,之后对方上一轮怎么做,你这一轮就怎么做):对手有两种偏离:一直背叛;或者"背叛、合作、背叛、合作……“轮流。δ 至少多大,才能抵抗这两种偏离?

(3)δ = 0.6 时,两种策略各能不能维持合作?

题 2(★★★)两期博弈:阶段博弈有两个均衡

阶段博弈如下,甲选行(A、B、C),乙选列(A、B、C)。

A B C
A (6,6) (0,7) (0,0)
B (7,0) (2,2) (0,0)
C (0,0) (0,0) (4,4)

这个博弈玩两期,第二期的收益用 δ 折现(δ 是一个数,0 到 1 之间)。

(1)阶段博弈有哪些纯策略纳什均衡?

(2)设计这样一个策略:第一期(A,A);第二期,如果第一期是(A,A),就玩(C,C),否则玩(B,B)。δ 至少多大,这是子博弈完美均衡?

(3)如果只有一个阶段均衡(比如只有(B,B)),第一期还能出(A,A)吗?

题 3(★★)民间定理:哪些收益能维持

囚徒困境(3、5、0、1)里,每个人的"最低保障"是 1(对方一直背叛时,你最多得 1)。判断下面这些收益组合,是否可行(是四个纯结果的某种混合),是否满足每人至少 1,以及当 δ 接近 1 时,能不能通过重复博弈维持。

(a)(2,2) (b)(4,1.5) (c)(4,2) (d)(0.5,3.5) (e)(3,3)

题 4(★★)声誉:先验与贝叶斯更新

一家连锁店面对一个又一个进入者。进入者的收益:不进入得 1;进入后被打价格战得 −1;进入后被默许得 2。连锁店有两种类型:强硬型(概率 μ = 0.2),总是打价格战;软弱型(概率 0.8),进入发生后以概率 s 打价格战。

(1)进入者进入,当且仅当打价格战的概率不高于多少?

(2)s = 1/2。有一个进入者进入后,看到连锁店打了价格战。下一个进入者认为连锁店是强硬型的概率是多少?下一个进入者面对的"打价格战"概率是多少?会进入吗?

(3)如果上一个进入者进入后,看到连锁店默许了,结果呢?

(4)要让第一个进入者对进入和不进入无差别,软弱型的 s 要是多少?

题 5(★★)锦标赛:奖金差多大才够

两个员工比赛,赢的人得工资 w₁,输的人得工资 w₂(奖金差 Δ = w₁ − w₂)。每人选努力(成本 4)或偷懒(成本 0)。两人都努力或都偷懒:各以 1/2 的概率赢;一个努力一个偷懒:努力的人赢的概率是 3/4。设 w₂ = 0。

(1)把 Δ = 20 的收益矩阵写出来(每格是两人的"期望工资 − 努力成本”)。均衡是什么?

(2)Δ 至少多少,“努力"才是占优策略?

(3)Δ = 12 时均衡是什么?

(4)Δ = 20 时,两个人都努力,每人得 6,比都偷懒的 10 少。这对公司是好事还是坏事?说出你的判断依据。

题 6(★★★)噪声下的长期平均

囚徒困境(3、5、0、1),每一次打算做的动作,都有 10% 的概率执行成相反的动作。比较三种策略(两个玩家都用同一种策略)的长期每轮平均收益:

  • 以牙还牙:打算做对方上一轮实际做的;
  • 宽容的以牙还牙:对方上一轮合作就合作;对方上一轮背叛,也以 1/3 的概率合作;
  • 赢留输换:上一轮两人做的相同(都合作或都背叛)就合作,不同就背叛。

(1)以牙还牙对以牙还牙:四种结果(合作合作、合作背叛、背叛合作、背叛背叛)的长期概率是多少?平均收益是多少?(提示:用对称性。)

(2)宽容的以牙还牙:四种结果的长期概率分别是 121/196、33/196、33/196、9/196。平均收益是多少?

(3)赢留输换:四种结果的长期概率分别是 333/500、9/100、9/100、77/500。平均收益是多少?

(4)三者排序。为什么以牙还牙在有噪声时最差?

题 7(★★★)零行列式策略

两个玩家 X 和 Y 玩无限次的囚徒困境(3、5、0、1)。X 用"记忆一步"的策略:上一轮结果是(X 与 Y 的动作)合作合作、合作背叛、背叛合作、背叛背叛时,这一轮合作的概率分别是 p = (5/6, 1/4, 1/2, 0)。可以证明:不管 Y 怎么玩,长期平均收益满足 X 的收益 − 1 = 2 × (Y 的收益 − 1)(这叫"勒索”:X 比"互相背叛的 1"多得的部分,是 Y 的两倍)。

(1)Y 一直合作。长期两人各得多少?验证上面的关系。

(2)Y 一直背叛。两人各得多少?验证关系。

(3)Y 每一轮以 1/2 的概率合作(与历史无关)。X 的长期收益是 42/17,Y 的是 59/34。验证关系。

(4)比较(1)里的两人收益:Y 的最好办法是什么?这个策略为什么会让 Y 吃亏,又为什么 Y 不得不接受?

第二部分 演化与学习(第 27–31 讲)

题 8(★★)鹰鸽与布尔乔亚

两只动物争一块价值 V = 8 的领地。鹰总是打,鸽从不打。两只鹰相遇,各以 1/2 的概率赢,输的受伤;赢得 8,受伤的代价是 C = 12,所以每只鹰平均 (8 − 12) ÷ 2 = −2。鹰遇鸽:鹰得 8,鸽得 0。两只鸽相遇:平分,各得 4。

(1)求鹰的比例 p,使得鹰和鸽的平均收益相等,以及此时的平均收益。

(2)代价 C 升到 20,p 和平均收益变成多少?为什么更危险的战斗,鹰反而少了?

(3)再加一种策略布尔乔亚:占着领地的当"主人",当主人就打(鹰);当"闯入者"就让(鸽)。每只动物当主人或闯入者的概率各 1/2。全体都是布尔乔亚时,每只的平均收益是多少?一只鹰、一只鸽闯进来,各得多少?布尔乔亚能不能被入侵?

题 9(★★)复制子动态:猎鹿

一个种群里,猎鹿者的比例是 x,猎兔者的比例是 1 − x。收益:猎鹿者遇猎鹿者 4,遇猎兔者 0;猎兔者遇猎鹿者 3,遇猎兔者 2。每一代,各类的比例变成"上一代比例 × [1 + 0.1 × (自己的平均收益 − 全体的平均收益)]"。

(1)写出两类的平均收益,找出所有的"不动点"(比例不再变的点)。

(2)从 x = 0.7 出发,下一代的 x 是多少?再下一代?从 x = 0.6 出发呢?

(3)哪些不动点是稳定的?每个的"吸引范围"是什么?

(4)种群一开始有 65% 的猎鹿者,最后会变成什么?为什么说这像一个"门槛"?

题 10(★★)阈值与规范

10 个人,每人有一个"阈值":只有当已经加入的人数不少于自己的阈值时,才加入。例如阈值 0 的人一开始就加入。

(1)阈值是 0、1、2、3、4、5、6、7、8、9。最后有多少人加入?一步一步写出来。

(2)把阈值为 1 的那个人,换成阈值 2(其余不变),最后有多少人加入?

(3)这说明了什么?为什么两个看起来几乎一样的人群,结果天差地别?

题 11(★★)虚拟博弈

甲乙玩猜硬币:甲想让两面相同,乙想让两面不同。每个人从第 2 轮起,都对对手到目前为止的历史频率做最佳回应;如果打平,甲出"正",乙出"反"。第 1 轮,两人都出"正"。

(1)把前 8 轮的出法一轮一轮写出来。

(2)8 轮之后,甲出"正"的频率、乙出"正"的频率各是多少?

(3)每一轮的出法有没有稳定下来?频率往哪里走?

题 12(★★)遗憾匹配

你和一个"总是出石头"的对手玩石头剪刀布(赢 1,输 −1,平 0)。你用遗憾匹配:每一轮之后,对每个选择,计算"如果当时出这个,会比实际多得多少",累计起来;下一轮按照累计遗憾的正部分,按比例随机选择。

(1)第 1 轮你出剪刀。三个选择的累计遗憾各是多少?第 2 轮你出各个选择的概率是多少?

(2)第 2 轮你出布。更新累计遗憾,第 3 轮的概率是多少?

(3)这个过程会收敛到什么?

题 13(★★★)相关均衡:斗鸡

斗鸡博弈:每人选冲或让。(冲,冲)各 0;(冲,让)冲的人 7、让的人 2;(让,让)各 6。

(1)求两个纯策略纳什均衡,和混合纳什均衡(冲的概率,期望收益)。

(2)一个"红绿灯":一个中间人从(冲,让)、(让,冲)、(让,让)三个结果里,等概率抽一个,悄悄各告诉每人"自己该做什么"。验证:每个人听从建议是最优的。每人的期望收益是多少?

(3)更好的红绿灯:(让,让)的概率 1/2,(冲,让)和(让,冲)各 1/4。验证听从建议仍是最优,每人期望收益是多少?

(4)中间人能不能总是建议(让,让)?

题 14(★)判断题:这些话对吗

判断对错,并用一两句话说明理由。

(a)无限次重复的囚徒困境里,合作一定能维持。

(b)有限次重复的囚徒困境,每一轮都背叛是唯一的子博弈完美均衡。

(c)演化稳定策略一定是纳什均衡。

(d)复制子动态一定收敛到纳什均衡。

(e)虚拟博弈里,每一轮的出法一定会稳定下来。

(f)相关均衡是纳什均衡的一种特殊情形。

解答

第一部分 重复博弈

题 1 解答

思路: 比较"合作到底的现值"和"偏离一次的得失"。

过程与答案:

(1)合作到底:每轮 3,现值 3 ÷ (1 − δ)。偏离一次:这一轮得 5,之后永远是(背叛,背叛),每轮 1,现值 5 + δ ÷ (1 − δ)。不偏离的条件:3 ÷ (1 − δ) 不小于 5 + δ ÷ (1 − δ)。两边乘 (1 − δ):3 不小于 5(1 − δ) + δ = 5 − 4δ,δ 不小于 1/2。

(2)以牙还牙,对手有两种偏离。一直背叛:第一轮 5,之后(背叛,背叛)每轮 1,和(1)一样,要求 δ 不小于 1/2。轮流背叛合作:对手背叛时你合作(对手得 5),对手下一轮合作时你背叛(对手得 0),之后又……所以对手的收益序列是 5、0、5、0……,现值 5 ÷ (1 − δ²)。要不超过合作的 3 ÷ (1 − δ):5 不大于 3(1 + δ),δ 不小于 2/3。两个条件都要满足,所以以牙还牙需要 δ 不小于 2/3。

(3)δ = 0.6:冷酷触发(要 1/2)能维持;以牙还牙(要 2/3)不能。

常见错误: 只检查"一直背叛"这一种偏离,得到 1/2;以牙还牙更宽容,所以对手能通过"背叛一次、再合作"这类偏离占便宜,要求的 δ 更高。

题 2 解答

思路: 第二期用不同的阶段均衡,来奖励或惩罚第一期的行为。

过程与答案:

(1)逐格检查。(B,B):甲得 2,改 A 或 C 得 0;乙同理,是均衡。(C,C):甲得 4,改 A、B 得 0;乙同理,是均衡。(A,A):甲得 6,改 B 得 7,不是均衡。所以两个纯策略均衡:(B,B)和(C,C)。(C,C)对双方都更好(4 大于 2),可以做"奖励";(B,B)做"惩罚"。

(2)第一期(A,A),之后如果是(A,A)就玩(C,C)。甲在第一期偏离到 B:第一期得 7,第二期因为偏离被惩罚,玩(B,B),折现得 2δ,合计 7 + 2δ。不偏离:6 + 4δ。不偏离的条件:6 + 4δ 不小于 7 + 2δ,δ 不小于 1/2。乙对称。第二期无论哪种情形,玩的都是阶段均衡,所以子博弈完美。

(3)如果阶段博弈只有一个均衡(B,B):第二期一定是(B,B),没有办法惩罚第一期的偏离;第一期的偏离收益 7 大于 6,所以第一期也是(B,B)。不能。 这就是"有限次重复里,只有阶段博弈有多个均衡时,合作才可能"。

常见错误: 把(A,A)当成阶段均衡。它不是,A 对 B 有 7 对 6 的诱惑。

题 3 解答

思路: 民间定理:可行且每人不低于最低保障的收益,当 δ 接近 1 时都能维持。

过程与答案: 可行的收益区域,是四个纯结果(3,3)、(0,5)、(5,0)、(1,1)的凸包(所有混合)。它的上边界是:从(0,5)到(3,3),再到(5,0)两段线段。其中(3,3)到(5,0)这一段:y = 3 − 1.5(x − 3),x = 4 时 y = 1.5。

(a)(2,2):是(3,3)与(1,1)的各一半,可行;两人都不低于 1,满足。能维持。

(b)(4,1.5):恰好在(3,3)到(5,0)这段边界上(x = 4 时 y = 1.5),可行;都不低于 1,满足。能维持(要 δ 相当接近 1)。

(c)(4,2):x = 4 时边界是 1.5,而 2 大于 1.5,在边界之外,不可行。

(d)(0.5,3.5):x = 0.5 时,凸包的下边界是 3(从(0,5)到(1,1))、上边界是 4.67,所以 3.5 在其中,可行;可是甲只得 0.5,低于最低保障 1,不满足,甲不会接受。不能维持。

(e)(3,3):可行,满足,能维持(题 1:δ 不小于 1/2)。

常见错误: 把(4,2)当成可行:只看"每个数都不大于 5"。可行性看的是整体,混合不能让两人同时都"超过"线段。

题 4 解答

思路: 用贝叶斯公式,把观察到的行为转化成对类型的判断。

过程与答案:

(1)进入者进入的期望:不被打的概率是 1 − f,被打的概率是 f:2(1 − f) − f = 2 − 3f。不进入得 1。进入不亏:2 − 3f 不小于 1,f 不大于 1/3。

(2)软弱型打的概率 s = 1/2。看到"打":强硬型一定打,软弱型以 1/2 的概率打。后验 = 0.2 ÷ (0.2 + 0.8 × 0.5) = 0.2 ÷ 0.6 = 1/3。下一个进入者面对的"打"的概率 = 1/3 × 1 + 2/3 × 1/2 = 2/3,大于 1/3,不进入。

(3)看到"默许":强硬型绝不会默许,所以一定是软弱型,后验强硬 = 0。下一个进入者面对的"打"的概率只有 s = 1/2,仍然大于 1/3,不进入(只要 s 大于 1/3)。

(4)第一个进入者的情形:打的概率 = 0.2 + 0.8s。无差别:0.2 + 0.8s = 1/3,0.8s = 2/15,s = 1/6。

常见错误: 以为"看到默许"之后,连锁店的声誉就没了,所以应该进入:只要软弱型打的概率 s 不低于 1/3,仍然不值得进入。声誉的价值,是让进入者对"打"的概率估计保持在门槛之上。

题 5 解答

思路: 把每个格子的期望工资减去努力成本,看努力能不能占优。

过程与答案:

(1)w₂ = 0,w₁ = 20。两人都努力:赢的概率 1/2,期望工资 10,减成本 4,各 6。两人都偷懒:各 10。一个努力、一个偷懒:努力的人赢的概率 3/4:15 − 4 = 11;偷懒的人赢的概率 1/4:5。矩阵(行的收益,列的收益):

乙:努力 乙:偷懒
甲:努力 (6,6) (11,5)
甲:偷懒 (5,11) (10,10)

甲:乙努力时,努力 6 大于偷懒 5;乙偷懒时,努力 11 大于偷懒 10。努力是占优策略,均衡是(努力,努力),各 6。

(2)一般的 Δ:(努力,努力):Δ/2 − 4;(偷懒,努力):Δ/4;(努力,偷懒):3Δ/4 − 4;(偷懒,偷懒):Δ/2。努力占优,要求:对乙努力:Δ/2 − 4 不小于 Δ/4,Δ 不小于 16;对乙偷懒:3Δ/4 − 4 不小于 Δ/2,Δ 不小于 16。Δ 至少 16。

(3)Δ = 12:对乙努力,努力 2 小于偷懒 3;对乙偷懒,努力 5 小于偷懒 6。偷懒是占优策略,均衡是(偷懒,偷懒),各 6。(此时奖金差太小,没有人愿意努力。)

(4)Δ = 20 时每人 6,小于都偷懒的 10:这是一种"囚徒困境":两个人都白白付出了努力的成本(互相抵消了赢的概率)。对员工是坏事;对公司,要看产出:如果努力带来的产出增加值超过努力的成本(两个人合计 8),公司就是赢家;要判断好坏,看的是产出的增加和总成本的比较,而不是员工自己的收益。

常见错误: 只看员工的收益,就说"锦标赛让大家变穷";公司设计它,是为了让产出变高。

题 6 解答

思路: 把四种结果当作马尔可夫链的状态,用长期概率加权。

过程与答案:

(1)以牙还牙对以牙还牙,有 10% 的错误:一个简单的论证是,因为对称,(合作,背叛)和(背叛,合作)是互相转换的;所有状态之间的转移没有"偏向",长期每种结果各 1/4(可以逐个检验)。四种各 1/4。平均收益 = (3 + 0 + 5 + 1) ÷ 4 = 2.25。

(2)宽容的以牙还牙:平均 = 3 × 121/196 + 0 × 33/196 + 5 × 33/196 + 1 × 9/196 = (363 + 165 + 9) ÷ 196 = 537/196 ≈ 2.74。

(3)赢留输换:平均 = 3 × 0.666 + 0 × 0.09 + 5 × 0.09 + 1 × 0.154 = 1.998 + 0.45 + 0.154 = 2.602,约 2.60。

(4)排序:宽容的以牙还牙(2.74) > 赢留输换(2.60) > 以牙还牙(2.25)。以牙还牙最差:一次误操作,会引起"你背叛我也背叛"的来回报复(合作背叛、背叛合作互相转换),很难回到互相合作,长期平均只有四种结果的算术平均 2.25。宽容的版本以 1/3 的概率"放过"一次背叛,能打断报复,更快回到(合作,合作)。赢留输换更进一步:一次误操作后,两个人下一轮同时回到合作。

常见错误: 以为以牙还牙"永远是最好的策略"。那是在没有噪声时;有噪声时,宽容有价值。

题 7 解答

思路: 勒索策略保证"X 的收益 − 1 = 2 × (Y 的收益 − 1)",对任何 Y 都成立。

过程与答案:

(1)Y 一直合作:状态只有(合作合作)和(背叛合作)。从(合作合作)出发,X 以 5/6 的概率继续合作;从(背叛合作)出发,X 以 1/2 的概率合作。X 的长期合作比例 π:π × (1/6) = (1 − π) × (1/2),π = 3/4。X 的收益:3/4 的时间得 3,1/4 的时间得 5(Y 合作而 X 背叛):9/4 + 5/4 = 3.5。Y 的收益:3/4 的时间得 3,1/4 的时间得 0:2.25。验证:3.5 − 1 = 2.5;2 × (2.25 − 1) = 2.5。成立。

(2)Y 一直背叛:状态是(合作背叛)和(背叛背叛)。从(合作背叛),X 以 1/4 合作;从(背叛背叛),X 以 0 合作。X 的合作比例 π:π = π × 1/4,π = 0。长期 X 一直背叛,两人各得 1。验证:1 − 1 = 0;2 × (1 − 1) = 0。成立。

(3)Y 以 1/2 随机:X 的收益 42/17 ≈ 2.47,Y 的收益 59/34 ≈ 1.74。验证:42/17 − 1 = 25/17;2 × (59/34 − 1) = 2 × 25/34 = 25/17。成立。

(4)(1)里:X 得 3.5,Y 得 2.25。Y 如果想最大化自己的收益,就要让 X 的收益也最大(关系是线性的:X 的收益 = 1 + 2 × (Y 的收益 − 1),Y 越高,X 越高)。Y 能得到的最高收益是 一直合作,得 2.25。Y 如果一直背叛,只有 1。所以 Y 的最好办法是合作到底:这样 Y 得 2.25,X 得 3.5,X 占了更大的份额(X 比互相背叛多得 2.5,Y 只多 1.25)。Y 不得不接受:不接受(背叛)就是 1,比 2.25 差。这就是"勒索":Y 得到的比互相合作的 3 少,却比拒绝要多。

常见错误: 以为勒索者"强迫 Y 吃亏":Y 得 2.25,比一直背叛的 1 好;Y 吃亏的是相对份额。

第二部分 演化与学习

题 8 解答

思路: 混合均衡里,鹰和鸽的平均收益相等。

过程与答案:

(1)鹰的比例 p。鹰的平均收益 = p × (−2) + (1 − p) × 8;鸽的平均收益 = p × 0 + (1 − p) × 4。令相等:8 − 10p = 4 − 4p,p = 2/3。此时平均收益:鹰 = −4/3 + 8/3 = 4/3;鸽 = 4/3。

(2)C = 20:鹰遇鹰得 (8 − 20) ÷ 2 = −6。鹰的收益 −6p + 8(1 − p) = 8 − 14p;鸽 4(1 − p) = 4 − 4p。令相等:4 = 10p,p = 2/5。平均收益 = 4 − 4 × 2/5 = 12/5 = 2.4。更危险的战斗,鹰遇鹰的代价更大,所以平衡点上的鹰更少(2/3 变 2/5):每一只想当鹰的,都要小心遇到另一只鹰。

(3)布尔乔亚。全体布尔乔亚:一半时间是主人(打)、一半是闯入者(让)。两只布尔乔亚相遇,一只是主人,一只是闯入者:主人(鹰)对闯入者(鸽)得 8,闯入者得 0。每只的平均 = (8 + 0) ÷ 2 = 4。一只鹰闯进来:鹰遇布尔乔亚主人(鹰对鹰):得 −2;鹰遇布尔乔亚闯入者(鹰对鸽):得 8;各一半:(−2 + 8) ÷ 2 = 3,小于 4。一只鸽闯进来:鸽遇布尔乔亚主人(鸽对鹰):得 0;遇闯入者(鸽对鸽):得 4;平均 2,小于 4。鹰和鸽都不如布尔乔亚,所以布尔乔亚不能被入侵,是演化稳定的。

常见错误: 以为"鹰多了对所有人都不好,所以群体会选择更和平的比例"。演化选择的是个体,不是群体;平衡点由代价和价值决定。

题 9 解答

思路: 把"比例的变化"看成"比平均好的类增加"。

过程与答案:

(1)猎鹿者的平均收益:4x;猎兔者的:3x + 2(1 − x) = 2 + x。不动点:x = 0(全是猎兔者)、x = 1(全是猎鹿者),以及两者相等的 4x = 2 + x,x = 2/3。

(2)x = 0.7:猎鹿者 2.8,猎兔者 2.7,全体平均 0.7 × 2.8 + 0.3 × 2.7 = 2.77。新的 x = 0.7 × (1 + 0.1 × (2.8 − 2.77)) = 0.7 × 1.003 = 0.7021。再下一代约 0.7043。x = 0.6:猎鹿者 2.4,猎兔者 2.6,全体平均 0.6 × 2.4 + 0.4 × 2.6 = 2.48。新的 x = 0.6 × (1 + 0.1 × (2.4 − 2.48)) = 0.6 × 0.992 = 0.5952。再下一代约 0.5900。

(3)x = 0 和 x = 1 是稳定的:稍微偏离会回来。x = 2/3 是不稳定的:偏离一点点就越走越远。吸引范围:x 在 (0,2/3) 的,走向 0(全猎兔);x 在 (2/3,1) 的,走向 1(全猎鹿)。

(4)65% 的猎鹿者,比 2/3 ≈ 66.7% 少一点点,最后会变成全体猎兔。2/3 就像一个门槛:差一点点,走向完全不同的结局。这正是协调博弈的特点:两个都是好的稳定状态,起点决定去哪个。

常见错误: 以为不动点 x = 2/3 是稳定的,因为"两类的收益相等"。相等只是不动,不是稳定。

题 10 解答

思路: 一个人加入,会让阈值更高的人也加入,像多米诺骨牌。

过程与答案:

(1)阈值 0、1、…、9。第一步:阈值 0 的 1 人加入(共 1)。现在有 1 人,阈值 1 的人(阈值不大于 1)加入,共 2。有 2 人,阈值 2 的加入,共 3……一步一步,直到阈值 9 的也加入:10 人全部加入。

(2)阈值变成 0、2、2、3、4、5、6、7、8、9。第一步:阈值 0 的 1 人加入。现在只有 1 人,没有人的阈值不大于 1(阈值最小的其余人是 2)。停在 1 人。

(3)两个人群只差了一个人的阈值(1 变成 2),结果却从全体加入变成只有 1 人。这说明:连锁反应需要"每一级台阶都有人"。少了一级,整个链条就断了。预测这类现象很难:同样的整体分布,细微差别决定结局。

常见错误: 以为"只要大多数人阈值低,就会大规模加入"。这里阈值的平均几乎一样,结果天差地别。

题 11 解答

思路: 每一轮都按对手的历史频率做最佳回应;对手的历史改变,最佳回应也跟着变。

过程与答案:

(1)规则:甲看乙的历史中"正"是否不少于"反":是就出正,否就出反(打平出正)。乙看甲的历史中"正"是否不少于"反":是就出反(要和甲不同),否就出正(打平出反)。逐轮:

轮次 1 2 3 4 5 6 7 8
甲 正 正 正 反 反 反 反 反
乙 正 反 反 反 反 反 反 正

(2)8 轮后:甲出"正"3 次,频率 3/8 = 0.375;乙出"正"2 次,频率 2/8 = 0.25。

(3)每一轮的出法没有稳定:甲的出法由乙的历史决定,乙的历史慢慢变化,甲出"正"变成"反",乙再跟着变,形成长长的"一阵一阵"的循环。可是频率在向均衡的 1/2 慢慢靠近(在零和博弈里,据理论,频率会收敛到均衡)。

常见错误: 把"频率向 1/2 靠近"理解成"每一轮的出法接近随机":虚拟博弈里每一轮的出法是确定的最佳回应,不是随机。

题 12 解答

思路: 遗憾 = 当时出另一个选择,本来能多得多少,累计。

过程与答案:

(1)对手出石头。第 1 轮你出剪刀,输,得 −1。如果出石头,平,得 0,比实际多 0 − (−1) = 1;如果出布,赢,得 1,多 1 − (−1) = 2;剪刀:多 0。累计遗憾(石头,布,剪刀)= (1,2,0)。第 2 轮的概率:按正部分的比例:石头 1/3,布 2/3,剪刀 0。

(2)第 2 轮你出布,赢,得 1。如果出石头:得 0,比实际多 0 − 1 = −1,累计 1 + (−1) = 0;布:多 0,累计 2;剪刀:得 −1,比实际多 −1 − 1 = −2,累计 0 + (−2) = −2。累计遗憾(石头,布,剪刀)= (0,2,−2)。第 3 轮:只有布是正的,布的概率 = 1。

(3)对手一直出石头,你最终只出布,每轮都赢 1,也就是对对手的最佳回应。遗憾匹配会自己学会针对对手。

常见错误: 把"遗憾"算成"实际得到的",或者忘了累计(要把每一轮的遗憾加起来)。

题 13 解答

思路: 相关均衡:每人听了建议,自己再想一想,不想偏离。

过程与答案:

(1)纯策略均衡:(冲,让):冲的人得 7,改让得 6,不想改;让的人得 2,改冲得 0,不想改。(让,冲)对称。两个纯均衡,一个人 7、一个人 2,不公平。混合均衡:设对方冲的概率为 p。让你无差别:冲 = 0 × p + 7(1 − p);让 = 2p + 6(1 − p)。7 − 7p = 6 − 4p,p = 1/3。每人的期望收益 = 7 × 2/3 = 14/3 ≈ 4.67。

(2)红绿灯:三个结果(冲,让)、(让,冲)、(让,让)各 1/3。你被告知"冲":对方一定被告知"让"(只有(冲,让)这一个结果),你冲得 7,改让得 6,听从。你被告知"让":对方是(冲)或(让)各 1/2(结果是(让,冲)或(让,让)):你让得 1/2 × 2 + 1/2 × 6 = 4;改冲得 1/2 × 0 + 1/2 × 7 = 3.5,听从。每人期望收益 = (7 + 2 + 6) ÷ 3 = 5,比混合均衡的 4.67 高,也比两个纯均衡里"2 的那个人"强。

(3)更好的红绿灯:(让,让)1/2,(冲,让)、(让,冲)各 1/4。被告知"冲":对方一定"让",冲 7 大于让 6,听从。被告知"让":对方是冲的概率 = (1/4) ÷ (1/4 + 1/2) = 1/3,让的概率 2/3:让得 1/3 × 2 + 2/3 × 6 = 14/3;冲得 1/3 × 0 + 2/3 × 7 = 14/3,一样,听从(边界)。每人期望收益 = (7 + 2) ÷ 4 + 6 ÷ 2 = 9/4 + 3 = 21/4 = 5.25。

(4)不能。如果总是建议(让,让),每个人都有动力偏离到"冲"(得 7 大于 6)。相关均衡要求"听建议是最优的",总建议(让,让)违反了这一点。

常见错误: 以为中间人可以把"最好的结果"(让,让)直接定下来;必须让每个人自愿听从,所以要留一点概率给(冲,让)和(让,冲)。

题 14 解答

(a)错。 合作要靠"未来的影子"够长(δ 够大),还要有足够的信息和及时的惩罚。题 1(3)里,δ = 0.6 时,以牙还牙维持不了。

(b)对。 有限次重复,最后一轮是(背叛,背叛),倒推下去每一轮都是;当阶段博弈只有一个均衡时,这是唯一的子博弈完美均衡。(阶段博弈有多个均衡时可以不同,见题 2。)

(c)对。 演化稳定策略对自己是最佳回应(否则别人可以入侵),所以一定是纳什均衡;反过来,纳什均衡不一定演化稳定。

(d)错。 复制子动态可以绕圈(比如石头剪刀布),不收敛;也可能停在不稳定的点上不动。收敛时,如果收敛到一个内部的点,它是纳什均衡,可是不是每一个都收敛。

(e)错。 题 11:每一轮的出法一直在变,只是频率会靠近均衡。

(f)错。 反过来:纳什均衡是相关均衡的一种特殊情形(中间人的建议刚好是独立的随机)。相关均衡的集合更大。

做完之后

如果这一套错得多的地方是……

  • 题 1、2、3(触发策略、阶段均衡、民间定理):回到第 23、24 讲,重点是"偏离的得失"和"可行且不低于最低保障"。
  • 题 4、5(声誉、锦标赛):回到第 25 讲,重点是"贝叶斯更新"和"让努力占优的门槛"。
  • 题 6、7(噪声、零行列式):回到第 26 讲,重点是"长期平均"和"线性关系对任何对手成立"。
  • 题 8、9、10(演化稳定、复制子、阈值):回到第 27、28、29 讲,重点是"比例由什么决定"和"稳定与不动的区别"。
  • 题 11、12、13(虚拟博弈、遗憾匹配、相关均衡):回到第 30、31 讲,重点是"出法不稳定,频率却收敛"和"听建议是最优的"。

一个自我检验: 把题 13 的"(让,让)各 6"改成"各 5",你能不能不查书,判断"红绿灯"的最好版本是什么?