一、你不知道对手怎么玩
你和同事小周在休息室里天天玩石头剪刀布,每天几十局。没有人告诉你小周是怎么出招的,你只能看着。
你注意到小周似乎偏爱出石头。你该怎么办?显然,多出布。可是"多多少"?小周要是察觉了,也会改变做法,这时你又该怎么办?
先别往下读。请你想一想:如果你一直这样观察、调整,小周也一直这样观察、调整,最后会稳定在什么局面?是各自出招的比例稳定下来,还是永远追来追去?
这一讲看两种很朴素的"学习规则",它们都只用对方过去做了什么,不需要知道对方的收益,也不需要一步到位地算出均衡。
二、虚拟博弈:按过去的频率出最佳回应
虚拟博弈(fictitious play)的规则只有一句:
假设对方以后出招的比例,就是 TA 到目前为止出招的比例;然后,对这个比例出最佳回应。
用石头剪刀布走几步(石头 R 赢剪刀 S,剪刀赢布 P,布赢石头;赢得 1,输得 −1,平局 0)。设第 1 局,你出石头,小周出布(你输)。
- 第 2 局:你看小周:出过 1 次布。对布,最好的回应是剪刀(剪刀赢布)。小周看你:出过 1 次石头。对石头,最好的回应是布。结果:你出剪刀、小周出布(你赢)。
- 第 3 局:你看小周:布出过 2 次,最好的回应仍是剪刀。小周看你:石头 1 次、剪刀 1 次。算一下小周各出法的平均收益:出石头,对你的石头平,对你的剪刀赢,合计 +1;出布,对石头赢、对剪刀输,合计 0;出剪刀,对石头输,对剪刀平,合计 −1。最好的是石头。结果:你剪刀、小周石头(你输)。
这样一局一局算下去(我用程序算前 12 局,平局时按石头、布、剪刀的顺序取第一个),出招是:
(石头, 布)(剪刀, 布)(剪刀, 石头)(布, 石头)(布, 石头)(布, 剪刀)(布, 剪刀)(布, 剪刀)(石头, 剪刀)(石头, 剪刀)(石头, 剪刀)(石头, 布) ……
注意看:实际的出招不是随机的,而是一长串一长串地重复:连着出布,连着出石头,再连着出剪刀。可是把时间拉长,各个动作出现的比例,会趋向 1/3:
| 到目前为止玩了 | 你出 石头 / 布 / 剪刀 的比例 |
|---|---|
| 30 局 | 0.23 / 0.40 / 0.37 |
| 300 局 | 0.31 / 0.34 / 0.35 |
| 3000 局 | 0.345 / 0.333 / 0.322 |
比例慢慢靠近了 (1/3, 1/3, 1/3),恰好就是石头剪刀布的均衡(各出三分之一)。
这不是巧合。Robinson 1951 年证明:在零和博弈里(一方赢多少,另一方就输多少),虚拟博弈里双方出招的比例,会收敛到均衡。(我据二手转述,没有核对原文。)有意思的是:每一局的出招都在循环,但长期的比例却是均衡的比例。
换一个博弈,就不收敛了
那么对所有博弈都成立吗?不是。Shapley 1964 年给了一个 3×3 的反例:把石头剪刀布改成一个非零和的博弈,虚拟博弈永远不收敛。
下面是这个博弈的一种写法(左边是行玩家的收益,右边是列玩家的收益)。这是 Shapley 经典例子的一种写法,我没有核对原文,只是用程序验证了它确实不收敛:
| 第 1 列 | 第 2 列 | 第 3 列 | |
|---|---|---|---|
| 第 1 行 | 1,0 | 0,1 | 0,0 |
| 第 2 行 | 0,0 | 1,0 | 0,1 |
| 第 3 行 | 0,1 | 0,0 | 1,0 |
行玩家想让自己的行号和列相同;列玩家想让自己的列号等于行号加 1(循环的)。两边都用虚拟博弈。到目前为止,行玩家出第 1 行的比例,我算到的是:100 局时 0.56,200 局时 0.28,400 局时 0.14,800 局时 0.49,1600 局时 0.39,3200 局时 0.19,5000 局时 0.15。一次次大幅摆动,摆动的周期越拉越长,从不稳定。
⚠️ 这里第一次读会觉得别扭。 你会想:每个人都在"按最佳回应"做事,怎么会永远追不上对方?
因为"最佳回应"是针对过去的频率,而对方在同时也在针对你的过去做回应。两个人像是在追着对方的影子跑:你刚调整到对方过去的样子,对方已经变了。零和博弈里,一个人的好处恰好是另一个人的坏处,这种"追逐"会有一个自然的平衡;非零和博弈里没有这种约束,追逐可以一直转圈。
三、遗憾匹配:谁让我后悔得多,就多换成谁
虚拟博弈有一个特点:它要你记住对方每一次做了什么,并且在每一步都出一个确定的动作。下面这种规则不一样,它只看自己的后悔。
先说什么叫遗憾(regret)。到目前为止,你出了一串招,拿了一些分。事后看,如果你当初每一局都出石头,会多赚(或少赚)多少?这个差,就是你对"石头"的遗憾。对"布"和"剪刀",同样算一遍。遗憾是正的,意思是"早知道多出它就好了"。
遗憾匹配(regret matching)的规则是:
下一局,以和"正的遗憾"成正比的概率,出每一个动作。 没有正的遗憾的动作,不出。如果所有遗憾都不是正的,就随便出(各 1/3)。
手算两局。第 1 局:你出石头,小周出布(你输,得 −1)。
- 对石头的遗憾:如果当初出石头,对布输 −1,和实际一样,遗憾 = −1 − (−1) = 0。
- 对布的遗憾:出布对布平,0,比实际的 −1 多 1,遗憾 = +1。
- 对剪刀的遗憾:出剪刀对布赢 +1,比实际多 2,遗憾 = +2。
下一局,你以 1/3 的概率出布,2/3 的概率出剪刀。
第 2 局:设你出了剪刀,小周又出布(你赢,得 +1)。各动作的遗憾要累计起来:
- 石头:这一局,出石头对布输 −1,比实际的 +1 少 2,−2。累计 0 + (−2) = −2。
- 布:出布对布平 0,比实际少 1,−1。累计 1 + (−1) = 0。
- 剪刀:就是实际出的,0。累计 2 + 0 = 2。
只有剪刀的遗憾是正的(2),所以下一局你只出剪刀。
对一个一直出布的对手,两局以后你就锁定了正确的回应。 这是遗憾匹配的一个好处:对一个有规律的对手,它很快学会占便宜。
它保证了什么
我模拟了几件事。
对手有偏向(石头 50%、布 30%、剪刀 20%,每局独立):遗憾匹配几乎全出布(布对石头赢 0.5,对剪刀输 0.2,平均 +0.3),10 万局后平均每局赚 0.297,非常接近能赚的最多(0.3)。
两个人都用遗憾匹配玩石头剪刀布:长期出招的比例是 (0.335, 0.336, 0.329) 和 (0.333, 0.333, 0.334),都接近 1/3。
遗憾本身:平均每轮的后悔,一路下降:10 局时 0.3,100 局时 0.13,1000 局时 0.04,1 万局时 0.012,10 万局时约 0.004,大致按"1 ÷ 轮数的平方根"的速度。
这件事有一个名字:无遗憾(no regret)。意思是:不管对手怎么出招(哪怕是故意和你作对),时间足够长,你的平均遗憾都会趋向于 0,也就是你的平均收益,不会比"一直固定出某个动作"差。
Hart 和 Mas-Colell 在 2000 年提出了遗憾匹配这一类规则。我上面讲的是它的简化版(比较的是"一直出某个动作"的遗憾);他们原来的版本,比较的是"每次把动作 A 换成动作 B"的遗憾。据摘要,原版有一个结论:当所有玩家都用它时,出招的联合分布会收敛到一类叫"相关均衡"的集合(它比纳什均衡宽松)。简化版保证的是平均遗憾趋于 0。
要注意一点:无遗憾不等于收敛到纳什均衡。 Hart 和 Mas-Colell 2003 年还证明了一个更深的结果:据二手转述,不存在这样一种"每个人只看自己的情况"的学习规则,能在所有博弈里都保证收敛到纳什均衡。 所以"学习"不一定把你带到纳什均衡,能保证的是更弱的东西(比如无遗憾)。
四、人是怎么学的
人不是严格按虚拟博弈,也不是严格按遗憾匹配。更像是几种学习的混合:
- 强化学习:某个动作带来了好结果,就更倾向再出它。
- 信念学习(类似虚拟博弈):根据对方的历史,猜它以后怎么出,再回应。
- 经验加权吸引:Camerer 和 Ho 1999 年提出(Econometrica,67 卷 4 期,827–874 页),把强化学习和加权的虚拟博弈作为两个特例包含在内。据摘要,在他们用的三组实验数据上,两个特例通常被拒绝,而更一般的模型更好;不过在某些常和博弈里,信念类模型表现更好。
再看一个现实应用:扑克的人工智能。Bowling、Burch、Johanson 和 Tammelin 2015 年在《科学》(Science,347 卷 6218 期,145–149 页)宣布,两人有限注德州扑克已被"基本上解决",所用的是一种基于遗憾的算法(据报道,是反事实遗憾最小化的改进版)。简单说:让程序自己和自己对打,每一局之后按遗憾调整,打到足够多的局数,平均策略接近均衡。
五、证据:学习规则的实测
理论预测。 零和博弈里,虚拟博弈的出招比例收敛到均衡;非零和博弈里不一定;遗憾匹配保证平均遗憾趋于 0,所有人都用时,联合分布收敛到相关均衡。
证据。
- 虚拟博弈。 Brown 1951 年提出,Robinson 1951 年证明零和博弈里收敛,Shapley 1964 年给出非零和的反例。(我只看到二手转述,没有核对原文。)
- 遗憾匹配。 Hart 和 Mas-Colell 2000 年在《计量经济学》(Econometrica,68 卷 5 期,1127–1150 页)。据摘要:当各方都用遗憾匹配时,出招的联合分布以概率 1 收敛到相关均衡的集合。
- 不收敛的结论。 Hart 和 Mas-Colell 2003 年在《美国经济评论》(American Economic Review):不存在在一般博弈里保证收敛到纳什均衡的"非耦合"学习规则。(只核对到二手转述,没核对到卷期页。)
- 人的学习。 Camerer 和 Ho 1999 年(见上节)。
- 应用。 Bowling 等 2015 年(见上节)。
局限。 这些规则都是简化的模型。真实的对手会观察你、预测你,也会故意"带偏"你的学习;真实的博弈远比石头剪刀布复杂,收益也不是已知的。模拟里的数字,是我用特定的随机种子算出来的,数值会有波动。
分歧。 人们在多大程度上像这些规则那样学习,是事实问题,实验结果各不相同。至于"没有遗憾"是不是一个合理的目标(有人认为它太弱,有人认为它是在不知道对手的情况下能做到的最好的),则是一种取舍:你要的是在最坏的对手面前也不吃亏,还是在合作的对手面前也能达成好结果?这取决于你的处境。
六、常见的误用
- “虚拟博弈的出招是随机的。” 不对。它的每一步都是确定的,只是长期比例可能是均衡的比例。
- “学习一定会走到均衡。” 不对。非零和博弈里,虚拟博弈会绕圈;没有任何学习规则能在所有博弈里保证到达纳什均衡。
- “无遗憾就是最优。” 不对。它只保证"不比固定出一个动作差",并不保证拿到最高的收益。
- “遗憾匹配需要知道对手的收益。” 不需要。它只要你能算出:如果当初出另一个动作,会得多少(需要知道对手出了什么)。
- “收敛的是每一局的出招。” 不对。收敛的是比例,每一局的出招可能一直在变。
七、小结
- 虚拟博弈:假设对方以后的出招比例等于过去的比例,对它出最佳回应。零和博弈里比例收敛到均衡(石头剪刀布:30 局、300 局、3000 局,比例逐步靠近 1/3);非零和博弈里可能永远绕圈。
- 遗憾:事后看,当初换成另一个动作会多赚多少。
- 遗憾匹配:以和正的遗憾成正比的概率出招。对有规律的对手,两局就锁定回应;两人都用时,长期比例接近均衡。
- 无遗憾:不管对手是谁,平均遗憾趋于 0(量级是 1 ÷ 轮数的平方根)。
- 所有人都无遗憾:联合分布收敛到相关均衡的集合,但不一定是纳什均衡。
- 证据:Robinson、Shapley、Hart 和 Mas-Colell;人的学习是几种规则的混合。
回到休息室里的石头剪刀布。下次你面对一个"不知道对方怎么玩"的局面,请想一想:你是在按对方的历史做回应,还是在按自己的后悔调整?你是在追对方的影子,还是在保证自己不吃亏?
思考题
- 石头剪刀布,虚拟博弈,第 1 局两人都出石头。写出第 2 局和第 3 局两人的出招。(平局时按石头、布、剪刀的顺序取第一个。)
- 遗憾匹配:第 1 局你出布,小周出石头(你赢,得 +1)。算出你对三个动作的遗憾,并写出下一局三种出法的概率。
- 遗憾匹配:第 1 局你出剪刀,小周出石头(你输)。算出遗憾和下一局的概率。若第 2 局你出了布、小周又出石头(你赢),累计遗憾和下一局的概率是多少?
- 对手固定以石头 50%、布 30%、剪刀 20% 出招。算出你出石头、布、剪刀各自的平均收益,并说明遗憾匹配长期会怎么出。
- 平均遗憾大致按"1 ÷ 轮数的平方根"下降。如果想把平均遗憾再降到现在的十分之一,大致需要多少倍的轮数?
- 想一个生活里"事后后悔"推动调整的例子(路线选择、股票持仓、餐厅选择……),说说"按后悔成正比地换"会怎么做,又可能错在哪。
思考题提示
- 第 1 局 (石头, 石头)。第 2 局:两人都看到对方出过 1 次石头,最好的回应是布,所以 (布, 布)。第 3 局:你看小周:石头 1 次、布 1 次。出石头:对石头平 0、对布输 −1,合计 −1;出布:对石头赢 +1、对布平 0,合计 +1;出剪刀:对石头输 −1、对布赢 +1,合计 0。最好的是布;小周同理,所以 (布, 布)。
- 你出布,小周出石头,得 +1。对石头:出石头对石头平 0,比实际 +1 少 1,遗憾 −1;对布:就是实际,0;对剪刀:出剪刀对石头输 −1,比实际少 2,遗憾 −2。没有正的遗憾,所以下一局三种各 1/3。
- 第 1 局你出剪刀、小周出石头,你得 −1。对石头:出石头对石头平 0,比实际多 1,遗憾 +1;对布:出布对石头赢 +1,比实际多 2,遗憾 +2;对剪刀:0。下一局:石头 1/3、布 2/3、剪刀 0。第 2 局你出布,小周出石头,得 +1:石头的增量 0 − 1 = −1,累计 1 − 1 = 0;布的增量 0(实际),累计 2;剪刀的增量 −1 − 1 = −2,累计 0 − 2 = −2。只有布是正的,下一局只出布。
- 出石头:对石头平 0,对布输 −1 × 0.3,对剪刀赢 +1 × 0.2,合计 −0.1。出布:对石头赢 +1 × 0.5,对布平,对剪刀输 −1 × 0.2,合计 +0.3。出剪刀:对石头输 −1 × 0.5,对布赢 +1 × 0.3,对剪刀平,合计 −0.2。所以遗憾匹配长期几乎只出布,平均每局约 +0.3。
- 平均遗憾和"轮数的平方根"成反比。想降到十分之一,轮数要乘以 10 × 10 = 100 倍。
- 开放题。例:每天选上班路线。每天事后看,如果当时走了另一条路,会节省多少时间,把这个差累计起来,下次更倾向于累计省得最多的那条路。可能错的地方:当天的路况是随机的,累计的差可能是运气;而且如果很多人都按同样的方式调整,大家会一起涌向"昨天最快的路"。