一、验证很快,寻找很慢
先看一个 3×3 的博弈。你选一行,小周选一列。每个格子里有两个数:第一个是你的收益,第二个是小周的收益。
| 小周:列 1 | 小周:列 2 | 小周:列 3 | |
|---|---|---|---|
| 你:行 1 | 1,5 | 8,9 | 3,3 |
| 你:行 2 | 6,0 | 7,2 | 1,6 |
| 你:行 3 | 3,9 | 5,0 | 4,5 |
我告诉你一个答案:你以 2/5、3/5 的概率出行 2、行 3(行 1 不出),小周以 1/2、1/2 的概率出列 1、列 3(列 2 不出)。 这是一个纳什均衡。
先别往下读。请你想一想:要证明我说得对,你要做多少工作?
不多。小周按 (1/2,0,1/2) 出,你每一行的期望收益是:
- 行 1:1 × 1/2 + 3 × 1/2 = 2;
- 行 2:6 × 1/2 + 1 × 1/2 = 3.5;
- 行 3:3 × 1/2 + 4 × 1/2 = 3.5。
你出的行 2、行 3 恰好并列最高,行 1 更低:你没有理由改。再看小周:你按 (0,2/5,3/5) 出,小周每一列的期望收益是列 1:0 × 2/5 + 9 × 3/5 = 5.4;列 2:2 × 2/5 + 0 × 3/5 = 0.8;列 3:6 × 2/5 + 5 × 3/5 = 5.4。小周出的列 1、列 3 并列最高,列 2 更低。两边都没有人想改,这是均衡。 检验只用了几次乘法。
可是如果我不告诉你答案,只给你这张表,让你自己找呢?
这一讲要讲的就是这件事:检验一个答案很容易,找一个答案却可能非常难。
二、最笨的办法:猜"谁在用哪些策略"
怎么找?一个朴素的办法是猜支撑:猜你用哪几行、小周用哪几列,然后按"让对方无差别"的办法解方程,最后检查没人想偏离。
比如猜你用行 2、行 3,小周用列 1、列 3。小周出列 1 的概率设为 y,出列 3 的概率是 1 − y。要让你对行 2 和行 3 无差别:
6y + 1 × (1 − y) = 3y + 4 × (1 − y),即 5y + 1 = 4 − y,y = 1/2。
同理,你出行 2 的概率设为 x,行 3 的概率是 1 − x。要让小周对列 1 和列 3 无差别:
0 × x + 9 × (1 − x) = 6x + 5 × (1 − x),即 9 − 9x = 5 + x,x = 2/5。
这正是上面那个答案。最后检查:行 1、列 2 没有更好。通过。
这样猜一轮,要解两个很小的方程。 那一共要猜多少轮?对一般的博弈,双方各用几个策略的个数是一样的。你用 k 行、小周用 k 列,行的选法有 C(3,k) 种,列的选法也有 C(3,k) 种,一共 C(3,k)² 种猜法。k = 1、2、3 加起来:
9 + 9 + 1 = 19 种猜法。
这个 3×3 的博弈,一共试了 19 次,找到三个均衡:
| 均衡 | 你的做法 | 小周的做法 | 你的收益 | 小周的收益 |
|---|---|---|---|---|
| 纯策略 | 行 1 | 列 2 | 8 | 9 |
| 用到 2 个策略 | 行 2、行 3:2/5、3/5 | 列 1、列 3:1/2、1/2 | 3.5 | 5.4 |
| 用到 3 个策略 | 行 1、2、3:23/54、17/54、7/27 | 列 1、2、3:7/29、9/29、13/29 | 约 4.07 | 约 4.46 |
注意均衡的个数是 3,奇数。(对"一般"的博弈,均衡的个数总是奇数个,上面的表只是一个例子。)
可是策略数增长,猜法的数量会怎么变?每一方有 n 个策略时,猜法的总数是 C(2n,n) − 1。
| n | 3 | 10 | 20 | 30 |
|---|---|---|---|---|
| 猜法个数 | 19 | 约 18 万 | 约 1.4 × 10¹¹ | 约 1.2 × 10¹⁷ |
即使一秒钟能检查一百万种猜法,n = 30 也要大约 3700 年。
这是最笨的办法。真正的问题是:有没有聪明得多的办法?
三、零和游戏:不用猜
两人零和游戏是个好消息。这里你不用猜支撑。
你的目标是让最坏情况下的收益尽量大(极大极小)。把它写成一个线性规划:变量是你出每个策略的概率,约束是"不管小周出哪一列,你的期望收益都不低于 v",目标是让 v 尽量大。线性规划可以在多项式时间里解出来:规模翻一倍,时间大约翻几倍,而不是翻成天文数字。这是一个很古老、很扎实的结论。
所以在零和游戏里,“找均衡"是一件有标准解法的事。这也是为什么下棋、打扑克的 AI,在两人零和的场合里特别可靠。
四、一般博弈:答案一定有,却可能要走很久
非零和的博弈,情况就不同了。为了说清楚难在哪里,要先区分两种"难”。
一种难:像数独
给你一张数独,让你填出来。检验一个填法很快,找一个填法可能很慢,而且数独还可能根本没有解。 这是计算机科学里叫 NP 一类的难(最难的叫 NP 完全)。
另一种难:一定有解,就是找不到
纳什均衡不一样:它一定存在(纳什定理)。所以"找均衡"不是"这题有没有解",而是"解一定有,你怎么找到它"。
这里有一个很直观的类比:一条被折叠进巨大迷宫的单行道。 入口是已知的。这条路的每一个路口都只有一进一出,没有岔路。那么你从入口走进去,一定会走到另一头,因为路没有岔,也没有别的出口可去。可是迷宫太大,这条路可能长到 2ⁿ 步(n 是迷宫的大小)。你知道终点一定在,可是不一定走得到。
这正是找纳什均衡的一种经典算法的样子。Lemke 和 Howson 在 1964 年(《工业与应用数学学会杂志》12 卷,413–423 页)给出了双人博弈找均衡的算法:从一个已知的起点出发,沿着一条路一步一步走,一定会走到一个均衡。这个算法同时是一个构造性的存在性证明,据一份综述的介绍,它还说明了:非退化的情形下,均衡的个数是奇数个(这也是上面表格里均衡有 3 个的原因)。
这条路有多长?Savani 和 von Stengel 在 2006 年(《计量经济学》74 卷第 2 期,397–429 页)构造了一类方形的双人博弈,据摘要:对其中的博弈,Lemke–Howson 算法,即使在最好的情形,也要走维数的指数那么多步。
这类难,有名字:PPAD
Papadimitriou 在 1994 年(《计算机与系统科学杂志》48 卷第 3 期,498–532 页)给这一类"靠奇偶性论证保证有解"的问题起了名字:PPAD。
后来的结论是:
- Daskalakis、Goldberg 和 Papadimitriou(《SIAM 计算杂志》39 卷第 1 期,195–259 页,2009 年):据摘要,三个人的博弈里找纳什均衡是 PPAD 完全的,通过归约到 Brouwer 不动点问题得到。
- Chen、Deng 和 Teng:两个人的博弈也是 PPAD 完全的(我看到的是 2007 年的预印本和更早的报告;期刊信息我没有核对)。
“PPAD 完全"是什么意思?意思是:找均衡,和 PPAD 这一类问题里最难的一个一样难。 如果有谁能找到一个对所有博弈都快的算法,那么整个 PPAD 类的问题就都快了。大家普遍相信不存在这样的算法,可是这是一个未被证明的信念,不是定理。
为什么不说它是 NP 完全?
因为均衡一定存在。据 Daskalakis 等人论文的介绍:如果能证明找纳什均衡是 NP 完全,就会推出 NP = coNP,这被认为几乎不可能。所以这类"总是有解"的问题,需要自己的难度分类,PPAD 就是其中最重要的一类(据同一论文,这类问题的更大的家族由 Megiddo 和 Papadimitriou 在 1980 年代提出)。
⚠️ 难点:这个"难”,说的是什么
这里第一次读,容易有三个误会。
误会一:“所有博弈都很难。” 不是。上面 3×3 的博弈,你拿一支笔就能解出来。PPAD 的难,说的是最坏的情形、规模变大。随便抽出来的一个具体博弈,可能很好解。
误会二:“PPAD 完全就是’不可能解’。” 也不是。它只是说:目前没有对所有博弈都快的算法,而且大家相信不会有。 在特殊的博弈里(零和、势博弈等),有快的办法。
误会三:“难,所以均衡不存在。” 存在和找到是两件事。均衡一定存在;难的是找。
五、再问细一点,就更难了
上面问的是"随便找一个均衡"。如果你问得更细,就会更难。
回到上面三个均衡的表:你更喜欢哪一个?第一个(纯策略,你得 8)。那问题就变成:给定一个博弈,有没有一个均衡,能让你至少得到 8? 或者:这个博弈有没有第二个均衡?有没有一个均衡,让每个人的收益都不低于某个数?
Gilboa 和 Zemel 在 1989 年(《博弈与经济行为》1 卷第 1 期,80–93 页)研究了这类问题。据摘要,主要发现是:这类问题对纳什均衡来说通常是 NP 困难的,而对相关均衡来说是容易的(多项式时间)。Conitzer 和 Sandholm 在 2008 年(《博弈与经济行为》63 卷第 2 期,621–641 页)用一个统一的归约改进了很多结果:据摘要,判断是否存在带有某些自然性质的纳什均衡是 NP 完全的,数一数有多少个纳什均衡是 #P 困难的;而且要求"最大化某些性质"的问题,除非 P = NP,否则连近似都做不到。
所以,“找到一个均衡"和"找到最好的均衡”、“数有几个均衡”,难度不在一个量级。
六、表示的问题:连把博弈写下来都写不下
还有一种难,和"算"无关。
假设一个博弈有 n 个玩家,每人只有 2 个选择。那么所有人的选择组合有 2ⁿ 个,每个组合下每个人一个收益,一共 n × 2ⁿ 个数才能把这个博弈写下来:
| n | 10 | 20 | 30 |
|---|---|---|---|
| 要写下的数 | 10,240 | 约 2100 万 | 约 322 亿 |
三十个玩家的博弈,光是把收益表写出来就要三百多亿个数。这样的博弈,在现实里不可能真的存在一张表。 现实里的博弈往往有结构:每个人的收益只和身边的邻居、或者和"走同一条路的人数"有关。这种用很短的描述写下来的博弈,叫简洁博弈(图博弈、拥堵博弈等)。
一个好消息:势博弈
拥堵博弈就是一类很重要的简洁博弈:每个人选一些资源,每个资源的代价只和用它的人数有关(上班时选哪条路就是)。它有一个很好的性质:存在一个叫势函数的量,每个人的每一次"改选对自己更好的路",都会让势函数下降。 所以只要大家轮流做对自己更好的改变,一定会停在一个纯策略均衡上。
用一个小例子说明(Rosenthal 在 1970 年代提出了势函数的办法,出处我没核对)。3 个司机,路 A 的耗时 = 走路 A 的人数,路 B 固定耗时 2。势函数:路 A 上每多一个人,累计加上"第 k 个人的耗时 k",路 B 上每个人加 2。
- 开始:3 个人全在路 A,每人耗时 3。势 = 1 + 2 + 3 = 6。
- 一个司机改到路 B:耗时从 3 变成 2,路 A 上剩 2 个人,耗时 2。势 = 1 + 2 + 2 = 5(下降了 1,正好是这个人省下的耗时)。
- 此时路 A 的人耗时 2,改到路 B 也是 2,没人想改。停在均衡上。
势函数下降,所以不会转圈。可是它没说要降多少步才停。据通行的说法,Fabrikant、Papadimitriou 和 Talwar 在 2004 年证明了:在拥堵博弈里找纯策略均衡,属于另一类叫 PLS 的难(这篇论文我没能核对)。所以"一定会停"和"停得快",不是一回事。
七、出路
既然最坏情形很难,人们在做什么?
1. 只要"差不多"的均衡
ε 近似均衡:允许每个人最多有 ε 的收益可以通过偏离多得。Lipton、Markakis 和 Mehta 在 2003 年给出了一个拟多项式时间的算法(据 Rubinstein 论文摘要)。Rubinstein(2016 年,arXiv:1606.04550)证明,在一个叫"PPAD 的指数时间假设"的猜想下,对双人博弈、近似误差是常数时,拟多项式的时间是必要的,这个下界几乎与 Lipton 等人的算法吻合(据摘要,会议和期刊出处我没核对)。
2. 换一个更宽松的概念:相关均衡
相关均衡不要求每人独立随机,而是有一个"推荐信号"(比如红绿灯)。它的条件是一组线性不等式:对每一个人,每一个被推荐的动作,听从推荐都不比换成别的动作差。变量是"每一个整体结果出现的概率",约束也是线性的。所以找相关均衡是一个线性规划,可以高效解决。
规模有多大?两个人、每人 k 个动作:变量 k² 个,不等式 2k(k − 1) 个。k = 3:9 个变量,12 个不等式;k = 100:1 万个变量,19,800 个不等式。这对计算机来说都不大。
对有很多人的简洁博弈,Papadimitriou 和 Roughgarden 在 2008 年(《ACM 会刊》55 卷)给出了多项式时间的算法,适用于图博弈、拥堵博弈等很多类别;据后来的文献,原来的算法在严格意义上有漏洞,被后续工作(Stein 等人,Jiang 和 Leyton-Brown)修补过。
还有一个重要的事实:让每个人用"后悔最小化"的办法反复学习,大家的历史行为的整体分布,会趋向一类叫粗相关均衡的集合。 这是一条"不用解题,让大家学着玩,就能走到某种均衡"的路。(这是通行的结论,这里不另给出处。)
3. 找有结构的博弈
零和游戏(线性规划)、势博弈(沿着"改得更好"走一定停)等,都有各自的快办法。
八、证据:理论与现实
理论预测:
- 两人零和:多项式时间。
- 一般博弈:找一个均衡是 PPAD 完全的(三人以上,据 Daskalakis 等;两人,据 Chen 等)。
- 对均衡提更细的要求(至少多好、有几个):NP 困难或更难。
- 相关均衡:线性规划,容易。
证据(我核对的是出处和摘要层,没有读论文全文):
- Lemke 和 Howson 1964;Savani 和 von Stengel 2006(Econometrica 74(2):397–429)。
- Papadimitriou 1994(JCSS 48(3):498–532);Daskalakis、Goldberg 和 Papadimitriou 2009(SICOMP 39(1):195–259);Chen、Deng 和 Teng(2007 年预印本)。
- Gilboa 和 Zemel 1989(GEB 1(1):80–93);Conitzer 和 Sandholm 2008(GEB 63(2):621–641)。
- Rubinstein(arXiv 2016);Papadimitriou 和 Roughgarden 2008(JACM 55)。
局限:
- 这些结论全是最坏情形的。具体的、有结构的博弈,往往很好解。
- 复杂度类别之间的关系(比如 PPAD 是否等于 P)没有被证明。
- 现实中人和市场不是靠解题找均衡的,而是靠学习、模仿、试错。
分歧(这里更多是方法论的分歧,而不是价值的分歧):
- 一种观点:如果连一台计算机都找不到均衡,我们为什么相信市场或人能走到均衡?这句话据传出自 Kamal Jain,我没核对出处。这是对"均衡当作预测"的一个质疑。
- 另一种观点:最坏情形的难,不等于典型情形的难;而且人和市场并不是在求解均衡,而是在学习,学习的终点往往是更宽松的概念(比如相关均衡),或者博弈本身有结构。
- 怎么看:这是一个关于理论该怎么用的争论。它不改变上面的数学结论,但会改变你用均衡去预测现实时的谨慎程度。
九、常见的误用
- “均衡很难找,所以博弈论没用。” 难的是最坏情形和大规模;很多重要的博弈(零和、势博弈、小规模博弈)有快的办法。
- “PPAD 完全,就是 NP 完全。” 不是同一类。PPAD 是"一定有解"的问题,NP 完全是"可能没解"的问题。
- “算法找不到,现实里的人也找不到。” 人不是在做最坏情形的求解。
- “均衡找不到,那就不存在。” 均衡一定存在;难的是找。
- “相关均衡容易,所以它更好。” 容易是计算上的优点;它是不是合适的预测,要看具体问题。
十、小结
- 检验容易,寻找难:3×3 的博弈,检验一个均衡只需几次乘法;找所有均衡要试 19 种"谁在用哪些策略"。
- 猜法的个数是 C(2n,n) − 1;n = 30 时约 1.2 × 10¹⁷,一秒查百万个也要约 3700 年。
- 零和:线性规划,多项式时间。
- 一般博弈:找一个均衡是 PPAD 完全的:答案一定有,像一条折叠进大迷宫的单行道,终点一定存在,路可能长到指数。
- Lemke–Howson 沿路径走;Savani 和 von Stengel 构造出一类博弈,让它即使在最好的情形也要走指数那么多步。
- 不是 NP 完全:否则会推出 NP = coNP。
- 更细的问题更难:找最好的、数个数,NP 困难或 #P 困难。
- 表示的问题:n 个玩家各 2 个选择,要写 n × 2ⁿ 个数;n = 30 约 322 亿。
- 势博弈:每次改得更好,势函数下降,一定停在纯策略均衡;不保证停得快。
- 出路:近似均衡(拟多项式,Rubinstein 说几乎不能再快);相关均衡是线性规划;找有结构的博弈。
- 分歧:最坏情形的难,是否削弱均衡作为预测,是方法论的争论。
回到那张 3×3 的表。下次你听说"这个问题的均衡解出来了",请想一想:这是一个小博弈,还是一个有结构的大博弈?是求的一个均衡,还是最好的均衡?是靠求解,还是靠学习走到的?
思考题
- 在文中的 3×3 博弈里,验证第一个均衡:你出行 1、小周出列 2。你想改行吗?小周想改列吗?(比较它们的收益。)
- 双方各有 4 个策略时,需要检查多少种"支撑"的猜法?(提示:C(4,1)² + C(4,2)² + C(4,3)² + C(4,4)²。)
- 一个 2×2 的博弈:你的收益 行 1:(3,0),行 2:(1,2);小周的收益 行 1:(2,1),行 2:(0,3)(每个括号里依次是列 1、列 2)。找出所有纯策略均衡,再用"让对方无差别"的办法找出混合均衡。均衡一共几个?是奇数吗?
- 一个有 20 个玩家、每人 2 个选择的博弈,要写下收益表需要多少个数?30 个玩家时是 322 亿,40 个玩家时大约是多少?
- 拥堵博弈:4 个司机,路 A 的耗时 = 走路 A 的人数,路 B 固定耗时 2.5。从 4 个人全在路 A 开始,每次让一个"改了就更好"的司机改路。要改几次才停?每次改完势函数是多少?最后的均衡是什么?
- 有人说:“既然找均衡这么难,市场里的人当然不会处在均衡上。“请你分别从"最坏情形"和"学习"两个角度,说说这个说法有哪些地方站得住、哪些地方站不住。哪些是事实问题,哪些是方法论问题?
思考题提示
- 行 1、列 2 的收益是 (8,9)。你想改行吗?小周出列 2:行 2 得 7,行 3 得 5,都低于 8,不想改。小周想改列吗?你出行 1:列 1 得 5,列 3 得 3,都低于 9,不想改。所以是均衡。
- 16 + 36 + 16 + 1 = 69(也等于 C(8,4) − 1 = 70 − 1)。
- 纯策略:(行 1,列 1)收益 (3,2):你改行 2 得 1,小周改列 2 得 1,都不想改,是均衡。(行 2,列 2)收益 (2,3):你改行 1 得 0,小周改列 1 得 0,是均衡。(行 1,列 2)(0,1),你改行 2 得 2,不是。(行 2,列 1)(1,0),不是。混合:设小周出列 1 的概率为 y,你对行 1、行 2 无差别:3y = y + 2(1 − y),y = 1/2。设你出行 1 的概率为 x,小周对列 1、列 2 无差别:2x = x + 3(1 − x),x = 3/4。一共 3 个,奇数。
- 20 × 2²⁰ = 20,971,520(约 2100 万)。40 × 2⁴⁰ ≈ 40 × 1.1 × 10¹² ≈ 4.4 × 10¹³(约 44 万亿)。
- 势 = (路 A 上 1 + 2 + … + 人数) + 2.5 × (路 B 上人数)。开始:1 + 2 + 3 + 4 = 10,每人耗时 4。第一次:一个人改到 B(4 变成 2.5),路 A 剩 3 人,势 = 1 + 2 + 3 + 2.5 = 8.5。第二次:路 A 的耗时是 3,改到 B 是 2.5 更好,再改一个:路 A 剩 2 人,势 = 1 + 2 + 2.5 + 2.5 = 8。此时路 A 的人耗时 2,改到 B 是 2.5 更差;路 B 的人耗时 2.5,改到 A 是 3 更差:均衡。一共改 2 次,均衡是路 A 2 人,路 B 2 人。
- 开放题。站得住:最坏情形下,没有已知的快速算法;站不住:现实中的人不是在求解,而是在学习和模仿;很多博弈有结构,更容易;相关均衡也可以快速算出。事实问题:现实里的人和市场是否真的接近均衡,要靠数据;方法论问题:均衡该不该当作预测,取决于你怎么使用这个理论。