一、一堆石子

你和小周玩一个小游戏。桌上有 15 颗石子,轮流取,每次取 1、2 或 3 颗,取走最后一颗的人赢。你先取。

先别往下读。请你想一想:你第一步取几颗? 你为什么觉得这个数好?

这个问题和"同时行动"的博弈有一点本质的不同:这次你们轮流行动,而且每个人都看得见对方刚才做了什么。你的每一步,都会改变小周接下来面对的局面。要想清楚第一步,你得先想清楚:小周下一步会怎么走,再下一步呢? 一路想到游戏结束。

二、从终点倒着想

直接从 15 颗往后想,分支太多。有一个更聪明的办法:从游戏的终点往回推。

我们把"轮到某个人取的时候,桌上还剩几颗"叫作一个局面,问:轮到你取的时候,你是赢还是输(假设对手不犯错)?

  • 剩 0 颗: 轮到你时,对手已经取走了最后一颗。你输。
  • 剩 1、2、3 颗: 你一次取光,你赢。
  • 剩 4 颗: 你取 1 颗,对手面对 3 颗,一次取光;你取 2 颗,对手面对 2 颗;你取 3 颗,对手面对 1 颗。不管你取几颗,对手都能取光,你输。
  • 剩 5、6、7 颗: 你取 1、2、3 颗,把 4 颗留给对手,对手就输了。你赢。
  • 剩 8 颗: 不管你取几颗,都把 5、6、7 颗留给对手,对手赢。你输。

规律出来了:4 的倍数是"谁轮到谁输"的局面,其余的局面是"谁轮到谁赢",办法是把剩下的石子取到 4 的倍数。

取石子

回到你的问题:15 颗,你先取。15 除以 4 余 3,所以你取 3 颗,把 12 颗留给小周。之后无论小周取几颗,你都取"4 减小周取的数",永远把 4 的倍数留给小周,最后你取走最后一颗。

两点值得停下来想想:

  • 倒着想把一个看上去分支很多的问题,变成了一个一目了然的规律。 如果你一开始正着想,会觉得"我取 1,小周取 2,我再取……",很快就乱了。
  • 在这个游戏里,开局的石子数就决定了谁赢(只要双方都不犯错)。如果开始是 20 颗,先手一上来就落在"谁轮到谁输"的局面里,输(只要后手不犯错);如果小周不知道这个规律,先手仍有机会。

三、博弈树与逆向归纳

3.1 博弈树

取石子的每一步,都可以画成一棵博弈树:

  • 节点(圆圈): 某个人要做选择的地方,圈里写着是谁。
  • 枝: 这个人可以做的选择。
  • 叶子(最底端): 游戏结束,写着每个人的收益。

这里的博弈有一个重要特点:完全信息,也就是每个人在做选择的时候,都知道之前所有人做了什么。

3.2 逆向归纳

倒着想的办法,在博弈树上叫逆向归纳。步骤是:

  1. 找到最后一批要做选择的节点。 在那里,那个人只需要选对自己最好的。
  2. 把这个节点,替换成 TA 选定之后的结果。 树就矮了一层。
  3. 重复:在新的最后一层,再选对自己最好的,再替换。
  4. 一直到树根。

用一棵具体的树来做一遍。你先选 L 或 R;然后小周选 u 或 d;在某个位置上你还要再选一次 x 或 y。收益写在叶子上(你的,小周的):

从叶子往根倒着想

第一步: 最底下的节点是你选:x 得 4,y 得 0,你选 x,这个节点就替换成(4,1)。

第二步: 右边的小周:选 u,结果是(4,1),小周得 1;选 d,结果是(2,3),小周得 3。小周选 d,这个节点替换成(2,3)。

第三步: 左边的小周:选 u 得 2,选 d 得 4,选 d,这个节点替换成(1,4)。

第四步: 树根,轮到你:选 L,得到(1,4),你得 1;选 R,得到(2,3),你得 2。你选 R。

结果是:你选 R,小周选 d,收益(2,3)。

⚠️ 这里第一次读会觉得别扭: 你在树根选 R,是因为你预演了小周后面的每一步,包括小周在右边会选 d 而不是 u。你并没有选"上面看上去最好的叶子":(4,1)里你得 4,是整棵树里你最高的收益,可是它不会出现,因为小周不会走到那一步。你的选择,永远是对小周的反应的回应,而不是对叶子的挑选。

四、信任博弈:为什么好事做不成

一个更有现实味道的例子。你有 10 元,小周是一个你不太熟的人。

  • 你可以不信任:自己留着 10 元,小周得 0。结果(10,0)。
  • 你可以信任:把 10 元交给小周。这笔钱在小周手里会变成三倍,也就是 30 元。然后小周决定:
    • 分享:两个人平分,各 15 元。结果(15,15)。
    • 独吞:小周自己留着 30 元。结果(0,30)。

按逆向归纳:

  • 在最后一步,小周选分享得 15,选独吞得 30。小周选独吞。
  • 你预演到这一点:信任,得到 0;不信任,得到 10。你选不信任。

结果是(10,0)。可是(15,15)对两个人都更好。 它没有出现,是因为小周事先没法让你相信,TA 会分享:到了最后一步,独吞对 TA 更划算。这就是"信任"为什么难:好事需要一方先冒险,而对方在最后一刻没有动力回报。

这个结论依赖一个前提:小周完全按自己的收益做选择。如果小周愿意分享的概率是 q,你信任的期望是 15 × q,要比 10 大,就要 q 大于 2/3。

怎么让(15,15)发生?改变收益:比如签一份合同,独吞要赔偿 d 元。小周独吞的收益变成 30 − d,如果 d 大于 15,独吞就不如分享了,小周会分享;你预演到这一点,会选信任。结局变成(15,15)。同样的人,同样的钱,加了一份有约束力的合同,结局变了。 声誉、重复交往、道德,也能起到类似的作用。

五、先动,不一定占便宜

你可能会想:先走的人占便宜。看看这两个例子:

取石子: 15 颗,先手赢;20 颗,先手输。先动是好是坏,取决于局面,和先动本身没有关系。

石头剪刀布: 假设你先出,小周看到你出什么之后再出。小周只要出能赢你的那个,必胜。后动的人占了便宜,因为后动的人多看到了信息。如果两个人同时出,就公平了。

所以"先动"和"后动"各有各的账:先动的好处,是可以承诺(让对方的选项变少);先动的坏处,是暴露了自己的选择。哪一种更重,要看具体的博弈。

六、逆向归纳给出的是一个"完整计划"

逆向归纳不只告诉你最终发生什么,它给每一个节点都指定了一个选择,包括根本不会走到的节点。

在信任博弈里,小周的"计划"是:“如果你信任,我就独吞。“这个计划里,小周会做什么写得清清楚楚,哪怕你根本没有信任,这一步从来没发生过。它重要,是因为:你之所以选不信任,正是因为你读懂了小周在那个没发生的节点上会怎么做。 没走到的节点,影响着已经发生的选择。

七、它有多一般

Zermelo 在 1913 年给出了关于国际象棋的一个著名结论。按通行的说法:对于有限的、完全信息、没有随机的二人对弈,要么一方能强制获胜,要么双方都能强制至少平局。它的思路和我们的倒着想是同类的。后来 Kuhn 在 1953 年的文章里把这个想法推广,通常的说法是:任何有限的完全信息博弈,逆向归纳都能给出一个均衡(纯策略的,也就是不需要随机)。

现实里的限制在于:国际象棋的树大得没法穷举,所以我们并不知道开局到底是先手赢、后手赢还是和棋。逆向归纳在小的树上很好使,在大的树上,只是一个理想。

八、证据:人们会倒着想吗

理论预测什么? 在轮流行动的博弈里,理性的玩家从后往前推,在取石子这类游戏里,只要意识到"4 的倍数”(或类似的规律),就能稳赢。

证据怎么说?

  • Dufwenberg、Sundaram 和 Butler(2010)研究了一个和取石子同类的两人游戏(“21 游戏”)。据其摘要,这个游戏简单到可以用数学解出来,又复杂到大多数参与者一开始都做不好。关键是参与者有没有一个顿悟:意识到存在一个最优的玩法。
  • Berg、Dickhaut 和 McCabe(1995)用一个一次性的"投资游戏"做了实验,结构类似上面的信任博弈:每人先有 10 美元,匿名、一次性。据其摘要,互惠似乎是行为的基本要素,它体现在对一个匿名搭档的信任上。也就是说,不是所有人都像理论预测的那样"不信任、独吞”。

局限在哪? 实验里的游戏都很简化,参与者多是学生;这里引用的是摘要层面的结论,具体的数字需要读原文。

分歧是什么? 人们在取石子这类游戏里一开始做不好,是认知上"没想到",还是不相信对方会这样走?在信任类游戏里,回报是出于对公平的偏好、对声誉的在意,还是对规则的误解?研究者各有看法。

九、常见的误用

  • “逆向归纳说明,对方一定理性。” 它假设每个节点上的人都按自己的收益做最优选择,并且大家都知道这一点。如果你怀疑对方会犯错(或者在乎别的东西),算出来的就不一样。
  • “逆向归纳是对一个节点的预测。” 不对。它给每个节点都指定了行动,而你实际看到的只是其中一条路。
  • “树太大,所以没法用。” 在小问题上它是一把好刀。大问题可以抓住最关键的几步,不用把整棵树画出来。
  • “先动总比后动好。” 不对。要看先动的"承诺"价值和后动的"信息"价值,哪个更重。
  • “收益稍微变一点,结论还是一样。” 不一定。信任博弈里,小周独吞得 30、分享得 15,如果独吞只能得到 14(比分享的 15 还少),结论就整个变了。逆向归纳对收益数字很敏感,尤其是并列的时候(需要事先说清,并列时怎么选)。

十、小结

  • 博弈树:节点(谁选)、枝(选项)、叶子(收益)。完全信息:每个人都知道之前发生了什么。
  • 逆向归纳:从最后一批节点开始,每个节点选对自己最好的,把节点替换成结果,一层一层推到树根。
  • 取石子:4 的倍数是"谁轮到谁输",取到 4 的倍数就赢。
  • 信任博弈:逆向归纳得出"不信任、独吞",比(15,15)差;合同、声誉可以改变这个结局。
  • 先动不一定有利:看承诺的价值和信息的价值哪个更大。
  • 逆向归纳给出的是一个完整的计划,没发生的节点上的选择,会影响已经发生的选择。
  • 它适用于有限的完全信息博弈,大的树无法穷举。

回到那堆石子:下次你遇到"轮流行动"的局面,不妨先问:这个游戏的终点是什么?从终点往回推,每一步该是什么样?

思考题

  1. 取 1 到 3 颗,开始有 20 颗,你先取。如果小周不犯错,你有办法赢吗?如果你想试试运气,该取几颗?
  2. 每次取 1 到 4 颗,取走最后一颗的赢,开始有 22 颗。你先取,该取几颗?谁轮到谁输的局面是哪些数?
  3. 规则改成 取走最后一颗的人输(每次取 1 到 3 颗),开始有 15 颗,你先取。该取几颗?
  4. 下面这棵树:你先选 A 或 B。选 A 后,小周选 c 或 d:c 得(2,2),d 得(0,3)。选 B 后,小周选 e 或 f:f 得(2,0);选 e 之后,轮到你选 g 或 h:g 得(3,1),h 得(1,4)。用逆向归纳求出结果,并说明你是怎么一步一步得到的。
  5. 信任博弈里,如果加一份合同:独吞要赔偿 d 元。d 至少多大,你才愿意信任?
  6. 信任博弈里,你认为小周会分享的概率是多少,才值得你信任?(提示:比较期望收益。)

思考题提示

  1. 20 颗是 4 的倍数,先手"轮到谁谁输"。如果小周不犯错,你没有办法赢。想试运气:取 1 颗,把 19 颗留给小周,希望小周没发现规律、不会取到 4 的倍数。
  2. 每次最多取 4 颗,“谁轮到谁输"的局面是 5 的倍数(0、5、10、15、20……),因为不管你取 1 到 4 颗,对手都能取到 5 的倍数。22 除以 5 余 2,所以先手取 2 颗,把 20 颗留给对手。
  3. 取走最后一颗的人输:剩 1 颗时,轮到你只能取走它,你输。剩 2、3、4 颗:你取到只剩 1 颗,你赢。剩 5 颗:不管你取几颗,对手都能把 1 颗留给你,你输。所以"谁轮到谁输"的局面是 1、5、9、13……(除以 4 余 1)。15 颗时,取 2 颗,留 13 颗。
  4. 最底下(B 之后、e 之后):你选 g(3)还是 h(1),选 g,替换成(3,1)。B 之后的小周:e 得 1,f 得 0,选 e,(3,1)。A 之后的小周:c 得 2,d 得 3,选 d,(0,3)。树根:选 A 得 0,选 B 得 3,选 B。结果:你选 B,小周选 e,你选 g,收益(3,1)。
  5. 小周独吞的收益是 30 − d,分享是 15。要让小周分享,需要 30 − d 小于 15,即 d 大于 15(d = 15 时小周无差别)。你预演到小周会分享,信任得 15,比不信任的 10 好。
  6. 信任的期望是 15 × q + 0 × (1 − q) = 15q;不信任是 10。15q 大于 10,q 大于 2/3,约 67%。你至少要有三分之二的把握,认为小周会分享,才值得信任。