一、两个都在学习的程序

你写了一个程序,替你玩猜硬币。小周也写了一个,替小周玩。两个程序对玩,规则你很熟悉:

  • 双方同时亮出硬币的一面。两面相同,你赢 1,小周输 1;两面不同,小周赢 1,你输 1。
  • 你的程序只有一个"旋钮":出正面的概率 p。小周的程序也只有一个:出正面的概率 q。
  • 均衡你知道:双方都出 1/2,谁也占不到便宜。

两个程序的学法也很朴素:每一步,看看我的概率往哪个方向挪一点点,能让我的期望收益更高,就往那个方向挪一小步。 这是机器学习里最常见的做法,叫梯度上升。

先别往下读。请你想一想:两个程序都从接近均衡的地方出发(比如你出正面的概率 0.55,小周 0.5),各自这样学下去,会越来越接近 1/2 吗?

多数人的直觉是:会。两个都在往"对自己更好"的方向走,终点应该是均衡。

可是答案是:不会。越转越远。

算一算。你的期望收益是 (2p − 1)(2q − 1):双方都出正面,或者都出反面,你赢。你这一步该怎么挪?小周出正面的概率 q 大于 1/2,你就该多出正面(p 增大);q 小于 1/2,你就该多出反面。小周的程序同理,只是方向相反:你出正面的概率 p 大于 1/2,小周就该多出反面(q 减小)。

把离开均衡的距离记作 x = p − 1/2,y = q − 1/2。步长取 0.05,每一步的更新是:

  • x 变成 x + 0.2 × y;
  • y 变成 y − 0.2 × x。

这是一个旋转,而且每一步,离中心的距离会乘以 √(1 + 0.2²) = √1.04 ≈ 1.0198。每一步只多一点点,可是会累积:

步数 0 50 100
离均衡的距离 0.05 0.13 0.36

到了一百多步,概率已经撞到了边界(0 或 1),之后在外围打转,再也回不到中心。

两个都在学习的程序:最朴素的学法会越转越远

为什么?因为每个程序都在追对方上一步的位置。你根据小周现在的 q 调整 p,小周根据你现在的 p 调整 q。你往小周那边挪,小周又往另一边挪,追来追去,轨迹是一个越转越大的螺旋。

修正:多看一步

有一个不起眼的修正:不只看现在的方向,再把上一步的方向也考虑进去,当作对"对方下一步会怎么走"的预判,这叫乐观梯度(optimistic gradient)。同样的步长、同样的出发点:

步数 20 50 100 300
离均衡的距离 0.034 0.018 0.006 0.0001

右边的图:一圈一圈转进中心。(另一种修正,叫外推梯度:先试探着走一步,再用试探点处的方向正式走一步,结果非常接近。)

这件事不只是玩具。生成对抗网络(GAN)的训练,就是两个模型在玩这样一个游戏:Goodfellow 等人 2014 年(《神经信息处理系统大会》,2672–2680 页)把它写成一个两人的极小极大博弈:生成器努力造出以假乱真的样本,判别器努力分辨真假。据二手介绍,在理想条件下,最优点是生成器完全模仿真实数据、判别器处处输出 1/2。可是训练一个这样的网络,常常不稳定。Daskalakis、Ilyas、Syrgkanis 和 Zeng 在 2018 年(ICLR)的论文,据摘要,证明了:在双线性的零和博弈里(我们的猜硬币就是),乐观版本的最后一步会收敛到均衡,而普通的梯度下降注定会绕圈;作者还把乐观版本用到了 GAN 的训练上。

⚠️ 难点:均衡存在,不等于学得到

这里第一次读,容易有一个误会:“博弈论说均衡存在,所以聪明的程序最终会走到均衡。”

不是。均衡是一个"终点"的描述,没有说怎么走过去。 两个程序都在学,对每一个程序来说,对手都是一个会变的目标:你学得越快,小周的"最优"就变得越快。能不能学到,取决于学的办法。

还有一个细节要分清:最后一步和平均是两回事。上面左图里,每一步的位置越转越远;可是把 300 步里的位置取平均(也就是按"过去一直在做什么"的频率来看),平均是 (0.508,0.495),很靠近均衡。在零和游戏里,很多学习方法有这样的性质:平均会收敛,最后一步不一定。 如果你要部署一个程序去对付真实的对手,你应该部署哪一个?这个问题放在思考题里。

二、两人零和:自博弈为什么可靠

这一节讲一件好事。

自博弈(self-play)是 AI 训练里一个简单而有力的办法:让程序和自己的副本对打,一边打一边改进。 没有人类的棋谱,没有人类的指导。据摘要,AlphaZero(Silver 等人 2018 年,《科学》362 卷,1140–1144 页)就是这样:从随机的下法出发,只知道规则,在国际象棋、日本将棋和围棋上,打败了各自当时的世界冠军程序。

为什么在这类游戏里有效? 因为两人零和游戏有一个很好的性质:均衡策略有保证。 你只要走均衡策略,不管对手怎么玩,你至少拿到游戏的"值"。所以你可以问:一个策略离均衡还有多远? 衡量办法叫可被利用度(exploitability):一个最会针对你的对手,能比"均衡的结果"多赢你多少?

用石头剪刀布(赢 1,输 −1,平 0)算几个例子:

你的策略(石头,布,剪刀) 最会针对你的对手 可被利用度
(1/3,1/3,1/3) 怎么出都一样,0 0
(0.4,0.3,0.3) 出布:赢 0.4,输 0.3 0.1
(0.5,0.5,0) 出布:赢 0.5 0.5

可被利用度是 0,就是均衡;越大,离均衡越远,越容易被针对。自博弈的训练,目标就是把这个数压到接近 0。

离开了"两人零和"呢

多于两个人的博弈,或者不是零和的博弈,这个保证就没有了。 Brown 和 Sandholm 做的六人无限注德州扑克程序 Pluribus(《科学》2019 年),据该论文的正文,所用的技术在两人零和之外,并不能保证收敛到纳什均衡;作者的论点是,尽管没有已知的强理论保证,这些方法在更广的情形里仍然能做出超过人类水平的策略。

这是一个很诚实的区分:实践上有效,不等于理论上有保证。 为什么没有保证?下一节用一个很小的例子说明。

三、合作:自博弈学出"只有自己人懂"的约定

再看一个不是零和的游戏:协调。两辆车迎面相遇,都靠左,或都靠右,才能顺利通过;一个靠左一个靠右,就撞了。这个游戏有两个均衡(都靠左,都靠右),哪个都一样好。

假设有两对程序,每一对内部用自博弈反复练习。练着练着:

  • 第 1 对程序随机地练成了都靠左;
  • 第 2 对程序随机地练成了都靠右。

自博弈学出的私有约定:换个搭档就不灵

每一对内部配合得完美,自博弈的成绩无可挑剔。可是让第 1 对里的一个程序,去和第 2 对里的一个程序配合:一个靠左,一个靠右,撞车。如果每一对都是随机定下一种约定,两对约定不同的概率是 1/2;如果有 4 种同样好的约定,不同的概率是 3/4。

自博弈学到的,是"和自己配合的办法",它里面可能包含大量任意的、只有自己人才懂的约定。

Hu、Lerer、Peysakhovich 和 Foerster 在 2020 年(ICML,119 卷,4399–4410 页)把这个问题叫零样本协调:AI 要和从没一起训练过的搭档(比如一个人)配合。据摘要,普通的自博弈会形成很窄的、不能迁移的约定。他们提出的**“其他玩法”(other-play)的想法是:训练时,把"本来等价"的约定随机互换(比如把"左"和"右"在训练中随机对调),逼程序只学不依赖任意约定的做法**。在合作纸牌游戏 Hanabi 里,用这个办法训练的程序,和独立训练出的程序搭档时得分更高;据摘要,还有一个初步的真人实验:这类程序平均得分高于当时最好的自博弈程序。

回头想一想:为什么两人零和里没有这个麻烦?因为在零和游戏里,所有的均衡都等价:你走均衡里的一个策略,对方走另一个均衡里的策略,结果仍然是均衡的结果。可是在协调游戏里,你走左边均衡的一半,对方走右边均衡的一半,就撞了。 这是"为什么在多人、非零和的游戏里,没有保证"的最小例子。

四、AI 定价:没有一句话,也能默契抬价

最后一个例子,在现实里已经有争论。

两家公司,每天都给同一种商品定价,各自让一个会学习的定价程序来定。这两个程序不交换任何信息,只看到市场的价格和自己的利润。

用一个小游戏说明。每家公司每天定高价或低价(数字是为说明而编的):

对方高价 对方低价
你高价 10,10 0,16
你低价 16,0 4,4

一天的博弈里,低价是占优的(囚徒困境):4,4。可是每天都在重复。如果一方偷偷降价,赚 16,之后对方回击,两家都陷入 4,4。把"对方一降价,就永远降价"(冷酷触发)当作惩罚:不降价的收益是每期 10,降价是这期 16,往后每期 4。只要对未来的看重程度 δ 至少是 (16 − 10) ÷ (16 − 4) = 1/2,两家就愿意一直定高价。

这是重复博弈里的标准结论(δ 表示对未来的看重程度:下一期的收益,折算到现在只值 δ 倍)。有意思的是:算法不需要"懂"这个理论。 Calvano、Calzolari、Denicolò 和 Pastorello 在 2020 年(《美国经济评论》110 卷第 10 期,3267–3297 页)的模拟里,据摘要:Q 学习(一种强化学习)的定价算法,在一个重复的寡头价格竞争模型里,不交流,最终的定价却高于竞争水平;作者认为,这是因为算法学出了奖励与惩罚的策略:偏离了就惩罚,之后又慢慢回到合作。据摘要,这个结果在成本或需求不对称、参与者人数不同、以及各种不确定性之下,仍然成立。

现实里有证据吗?Assad、Clark、Ershov 和 Xu 在 2024 年(《政治经济学杂志》132 卷第 3 期,723–771 页)研究了德国的零售汽油市场:定价软件在 2017 年左右被广泛使用。据摘要,采用算法定价提高了利润率,但只在非垄断的加油站;在双寡头、三寡头市场里,只有所有加油站都采用,利润率才上升。

⚠️ 难点:这是"事实",还是"该不该管"?

这里有两个不同的问题,要分开。

  • 事实问题:学习算法能不能稳定学到默契抬价?现实市场里有多普遍?Calvano 等人是模拟,设定了特定的模型;Assad 等人是观察数据,只说采用与利润率上升有关,而且集中在特定条件下。两者都不是"AI 一定合谋"。
  • 价值和法律问题:没有任何协议,只是各自的算法"学"到了高价,算不算违法? 反垄断的法律在不同地方的规定不同,我没有逐一核对。这既要看法律怎么写,也要看你认为"竞争"应当意味着什么,博弈论不能替你回答。

五、一个混合的场景:合作、竞争,加上说话

最后看一个更接近现实的例子:外交(Diplomacy)这个七人的桌游,参与者既要结盟,又要背叛,还要靠自然语言的谈判。Meta 的研究团队 2022 年(《科学》)发表了 Cicero。据摘要,它把语言模型和规划、强化学习结合在一起:从谈话里推断其他玩家的信念和意图,再生成服务于自己计划的对话。在一个匿名的线上外交联赛的 40 场比赛里,据摘要,Cicero 的得分是人类平均得分的两倍多,并排在玩过不止一场的参与者的前 10%。

这个例子说明:当博弈里既有合作、竞争,又有话可以说(也可以说谎)时,光靠自博弈不够,还需要推断别人的想法。 这又回到了前面几节的难点:约定要和别人对得上,话要让别人相信。

六、证据:理论与现实

理论预测:

  • 两个朴素的学习程序对玩零和游戏,最后一步会绕圈而不是收敛;改进的办法能收敛。
  • 两人零和里,自博弈有保证;多人或非零和里没有保证,可能学出不能迁移的约定。
  • 重复的价格竞争里,只要足够看重未来,默契的高价可以成为均衡;学习算法可能学到这一点。

证据(我核对的是出处和摘要层,没有核对论文里的具体细节):

  • GAN:Goodfellow 等 2014(NeurIPS);Daskalakis 等 2018(ICLR):乐观版本的最后一步收敛,普通梯度下降绕圈。
  • 自博弈:Silver 等 2018(Science 362:1140–1144)。
  • 多人:Brown 和 Sandholm 2019(Science):正文中承认两人零和之外没有收敛保证。
  • 协调:Hu 等 2020(ICML):Hanabi;真人实验只是初步的。
  • 定价:Calvano 等 2020(AER 110(10):3267–3297,模拟);Assad 等 2024(JPE 132(3):723–771,观察数据)。
  • 混合:Meta 的 Cicero(Science 2022,摘要)。

局限:

  • 本讲的数字都是小例子,只用来演示机制,不是对现实的估计。
  • 摘要里的结果,往往有很多前提:模型的设定、学习的参数、训练的时间。这些我没有逐个核对,请不要把它们读成一般性的结论。
  • 现实中的 AI 系统,有人设定目标、有人监督、有法律的约束,不是一个孤立的"程序对程序"的博弈。

分歧(事实问题和价值问题要分开):

  • 事实问题:算法默契抬价在现实里有多普遍?自博弈出来的程序,和真人搭档的表现究竟怎样?这些要靠更多的数据和实验。
  • 价值问题:该不该规制没有协议的算法默契? 规制的成本和收益怎么算?这些是政策与法律的问题,取决于你怎么权衡竞争、效率和监管的代价。

七、常见的误用

  1. “AI 学会了均衡。” 一个程序打赢了,不等于它走到了均衡;要看可被利用度,或者它面对没见过的对手时的表现。
  2. “自博弈训练出来的,就是最强的。” 在两人零和里,它有强的保证;在合作和多人的游戏里,没有。
  3. “算法一定会合谋。” 模拟说明可能,观察数据说明在某些条件下与利润率上升有关;不是"一定"。
  4. “没有协议的默契,就是违法的合谋。” 这是一个法律和价值的问题,不能由博弈论直接回答。
  5. “把玩具例子当成现实的预测。” 例子里的 0.05、10、16,只是为了让你看清机制。

八、小结

  • 两个朴素学习程序对玩猜硬币:每一步离均衡的距离乘以约 1.0198,0.05 → 0.13 → 0.36,越转越远;乐观梯度修正后,0.05 → 0.018 → 0.006,转进中心。
  • GAN 是两人的极小极大博弈,训练的不稳定和这个现象有关。
  • 最后一步和平均:平均可以收敛,最后一步不一定。
  • 可被利用度:最会针对你的对手能多赢多少。均衡的可被利用度是 0。例:(0.4,0.3,0.3) 的石头剪刀布策略是 0.1,(0.5,0.5,0) 是 0.5。
  • 自博弈:两人零和里有保证(AlphaZero);多人、非零和里没有(Pluribus 的正文承认)。
  • 私有约定:每一对自博弈内部配合完美,换搭档会撞车:两种约定时概率 1/2,四种时 3/4。其他玩法:把等价的约定随机互换。
  • AI 定价:低价是占优的,但重复博弈里 δ 不小于 1/2 时,默契的高价可以成为均衡;Calvano 等的模拟中,Q 学习的算法学出了高于竞争水平的价格;Assad 等的观察数据显示,德国汽油市场里采用算法定价与利润率上升有关。
  • 混合场景:Cicero 要同时处理合作、竞争和自然语言。
  • 分歧:算法默契是否普遍是事实问题;是否该规制是价值问题。

回到你和小周的两个程序。下次你听说"某个 AI 学会了博弈",请想一想:它学会的是"打败自己",还是"和陌生人配合"?它面对的是一个会变的对手,还是一个固定的对手?它的"赢",有没有一个像可被利用度这样的尺子?

思考题

  1. 猜硬币,两个程序用普通的梯度上升,步长 0.05。从 (p,q) = (0.6,0.5) 出发,走一步之后 (p,q) 是多少?离中心的距离从多少变成多少?这个增长倍数和 √1.04 一致吗?
  2. 石头剪刀布,你的策略是 (石头,布,剪刀) = (0.5,0.25,0.25)。最会针对你的对手出什么?它的可被利用度是多少?
  3. 价格竞争的例子,改成:双方高价 10,10;一方偷偷降价,降价的一方赚 20,另一方赚 0;双方都降价,各赚 5。用冷酷触发,δ 至少多大,两家才愿意一直定高价?
  4. 协调游戏里,如果有 n 种同样好的约定,两对独立训练的程序,各自随机定下一种约定,约定不同的概率是多少?n = 2、3、4 各是多少?
  5. 猜硬币,你只能部署一个策略去对付一个会针对你的对手。普通梯度上升走到后来,p 在某些时刻会非常接近 1(几乎总出正面);而把所有步数的 p 取平均,p ≈ 0.51。这两个策略各自的可被利用度是多少?(提示:出正面的概率为 p 时,可被利用度是 |2p − 1|。)你应该部署哪一个?
  6. 想一个你生活里"算法和算法互动"的场景(网约车和外卖的动态价格、电商平台的竞价、推荐系统和商家的互相适应……)。你觉得它更像零和、协调,还是价格竞争?哪些部分是事实问题,哪些部分是价值问题?

思考题提示

  1. 梯度:你的是 2(2q − 1) = 0(q = 0.5),小周的是 −2(2p − 1) = −0.4。一步之后:p = 0.6 + 0.05 × 0 = 0.6,q = 0.5 + 0.05 × (−0.4) = 0.48。距离:从 0.1 变成 √(0.1² + 0.02²) = 0.102。倍数 0.102 ÷ 0.1 ≈ 1.02,和 √1.04 ≈ 1.0198 一致。
  2. 对手出布:赢 0.5(你出石头),输 0.25(你出剪刀),平 0.25:期望 0.25。出剪刀:赢 0.25(你出布),输 0.5(你出石头):−0.25。出石头:赢你的剪刀 0.25,输你的布 0.25:0。最好是出布,可被利用度 0.25。
  3. 条件:高价的持续收益 10 ÷ (1 − δ) 不小于偷偷降价的收益 20 + 5δ ÷ (1 − δ)。整理得 δ 不小于 (20 − 10) ÷ (20 − 5) = 2/3。
  4. 约定相同的概率是 1/n,所以不同的概率是 1 − 1/n:n = 2 是 1/2,n = 3 是 2/3,n = 4 是 3/4。
  5. p ≈ 1:可被利用度 |2 × 1 − 1| = 1(对手永远出反面,你每次都输 1)。平均 p ≈ 0.51:|2 × 0.51 − 1| = 0.02。应该部署平均的策略,或者从历史里随机抽一个策略出来用:最后一步的策略很极端,很容易被针对。
  6. 开放题。例如网约车动态价格:不同平台的算法互相适应,可能更像价格竞争;事实问题:是否真的抬高了价格;价值问题:如果抬高了,是否该管,怎么管。