二分图与匹配市场

"稳定"的定义只有一句话：不存在这样一对人，他们都觉得对方比自己现在的伴侣更好。这样的一对叫"阻塞对"，有阻塞对的匹配迟早会私下散伙。盖尔和沙普利 1962 年证明：这样的稳定匹配一定存在，而且有一个非常简单的算法能找到它。算法就是反复求婚：每个还单着的人向自己名单上还没问过的最好的那位求婚，对方手上留最好的那个、退掉其余的，直到没人单着。第四行读数永远是 0——一个阻塞对都没有。这不是运气，是定理。现在看前两行，这才是这个算法真正有趣的地方。默认参数下：求婚方平均拿到第 2.900 名，被求方平均拿到第 3.700 名。把"谁主动求婚"切到另一边，两个数就对调。第三行把这件事直接摆出来：甲方主动时甲方拿 2.900，乙方主动时甲方只拿 3.700。同一批人、同一套偏好，只因为谁先开口，结果就差了将近一名。这就是"求婚方最优"定理：盖尔-沙普利给出的是所有稳定匹配中对求婚方最好、同时对被求方最差的那一个。这条性质在现实中有分量。美国的住院医师匹配系统（NRMP）从 1952 年起用的就是这个算法，而整整四十年里，求婚方是医院。1998 年在争议之下改成了"医学生主动"，因为大家终于意识到：算法没有偏见，但"谁主动"这个设定本身就是一个分配权力的决定。沙普利和罗斯因这项工作获得 2012 年诺贝尔经济学奖。接下来做一件很值得做的事：把"偏好有多一致"拖到 0。两边的排名变成 2.400 / 2.500——优势几乎消失了。再拖到 100%（所有人认同同一个排名）：5.500 / 5.500，优势完全消失。原因是：当所有人偏好完全一致时，稳定匹配是唯一的（第一名配第一名，第二名配第二名），既然只有一个解，谁先开口自然没有区别。而当偏好完全分散时，几乎每个人都能拿到第一志愿，也没什么好争的。求婚方的优势在中间最大——也就是"大体上有共识、但又有个人偏好"的时候。这恰好是绝大多数真实市场的样子。（还有一个常被忽略的点：这个算法是"防策略"的，但只对求婚方防。求婚方如实报偏好是最优策略；而被求方有时可以通过谎报偏好改善自己的结果。罗斯证明了：不存在对双方都防策略的稳定匹配机制。机制设计里几乎所有的漂亮结论，背后都跟着一个这样的不可能定理。）

7 个人 7 件事，每个人做每件事的成本都不一样，一人一件，怎么派？穷举要试 7! = 5040 种，而 n = 20 时是 2.4×10¹⁸ 种，宇宙年龄也算不完。但这个问题有精确解，而且只要 O(n³)。匈牙利算法（库恩 1955 年，基于两位匈牙利数学家的工作）给出的是严格的全局最优，不是近似。图上绿框就是它的答案。红虚框是贪心的选择：每次挑全表里最便宜的格子，占掉一行一列，再继续。默认参数下：最优 29.90，贪心 32.40，贵了 8.4%，7 行里有 3 行选得不同。贪心为什么会输？它抢走的那个"最便宜的格子"，往往是某一行唯一的便宜选项，而占用它的那一行本来还有别的出路。局部最优的每一步，都在悄悄拿走别人的退路。第三行读数是一个下界：每一行各取最小值加起来（27.30）。这个值通常达不到（因为会撞列），但它给了你一个"最好能到哪"的参照——最优解 29.90 离它只差 9.5%。在没有精确算法的场合，"算一个便宜的下界，看看自己的解离它多远"是判断解好不好的标准手段，整数规划里的分支定界整套框架就建立在这上面。现在换成"人岗匹配度"那一档。成本变成 |能力 − 难度|——贪心的结果变成 +0.0%，和最优一模一样。这不是巧合：当成本矩阵有这种"一维排序"的结构时（能力和难度都在一条线上），按顺序配对就是最优的，贪心恰好复现了这个顺序。数学上这类矩阵叫蒙日矩阵，它们的指派问题贪心就能解。这给出一条很实用的判断：贪心好不好使，不取决于问题的名字，取决于成本矩阵的结构。同一个指派问题，换一种成本来源，贪心从"完全正确"变成"贵 8.4%"。（把"成本里的随机成分"拖到 0 再看"人岗匹配度"：贪心贵 1.2%，而有 5 行选得不同——选得不一样但成本几乎一样，说明这时存在大量并列最优解。这也是评价启发式算法时容易犯的错：只看"和最优解选得一样不一样"会严重低估它，该看的是目标函数值。）

"演员—电影"是二分图，"演员—演员"是一张普通网络。从前者得到后者的办法叫投影：只要两个人参加过同一个项目，就在他们之间连一条边。合作网络、共同持股网络、共同引用网络几乎都是这样造出来的。而这一步会带来一个很大的、经常被忽略的失真。默认参数下：原来只有 90 条"人—项目"的连接，投影之后变成了 155 条"人—人"的边。聚集系数 0.6803，而同等密度的随机图只有 0.2087——3.3 倍。三角形 257 个对 84 个。这个高聚集是真的吗？是真的，但它不说明任何"人与人之间的偏好"。原因是：一个有 m 个人参加的项目，投影后会变成一个 m 人的完全图，凭空产生 C(m,3) 个三角形。一部 20 个演员的电影，一口气贡献 190 条边和 1140 个三角形，而这背后只是"他们演了同一部戏"这一件事。把"项目规模的不均匀程度"拖到 1.5 再看：聚集系数 0.7508，随机图 0.2738（2.7 倍），三角形 616 对 173，3.6 倍。项目越大，投影造的假三角形越多。这意味着什么？任何在投影网络上算出来的聚集系数、三角形数、局部模体统计，都不能直接和"随机图"比——必须和保持二分结构的零模型比：把同样一批人分配到同样规模的项目里，随机分，再投影，再算。纽曼等人 2001 年就明确指出了这一点，而大量关于"合作网络高度聚集"的结论并没有做这个对照。这和上一个专题里"模体分析用错零模型"是同一类错误的两个版本。还有一件更麻烦的事：投影会丢信息，而且丢得不对称。投影之后你看不出两个人是在一个项目里合作的、还是在五个项目里合作的（除非用加权投影），也永远还原不出原来的二分图。所以能不投影就不要投影——直接在二分图上定义中心性、社团、推荐，结论会干净得多。（把项目数从 20 拖到 30、每人参加的项目数不变：投影密度从 0.246 掉下去，因为项目变小、变多，每个项目造的完全图也变小了。这也说明：投影网络的密度基本上由项目规模决定，而不是由人的社交倾向决定。）

这是一个真的推荐算法，只有两句话。把用户看过的每件物品各放 1 单位"资源"；第一步，每件物品把资源平分给看过它的所有用户；第二步，每个用户再把手上的资源平分给自己看过的所有物品。两步之后，资源落得最多的物品就是推荐结果。这叫物质扩散（周涛等，2007），它只用了二分图的结构，没有任何评分、标签或者内容信息。评测用留一法：每个用户藏掉一条真实记录，看这条记录能不能被推进前 10。默认参数下的读数是：扩散 47.8%，按热度 51.3%，随机 13.3%。两个算法都远远打败随机，但按热度排竟然比物质扩散还高一点。这不是本页的失误，这是推荐系统里最著名的一个坑。看第三行读数，答案就在那里。扩散的覆盖率是 77.8%，按热度只有 18.9%。也就是说，"按热度"这个算法把 81% 的物品永远不会推荐给任何人，它只是在反复推那二十来个爆款。第二行读数也一致：它推的物品平均热度 20.5，比扩散的 18.1 更高。命中率这个指标本身是偏向热门的。因为用户藏起来的那条记录，本来就更可能是一件热门物品——于是"猜热门"这个毫无个性化的策略，在命中率上天然占便宜。这是评价指标选错方向的典型案例。真实的推荐系统如果只优化命中率／准确率，结果一定是：所有人看到同一批爆款，长尾彻底死掉，而线上指标看起来很漂亮。所以工业界的评价体系必须同时看覆盖率、新颖性、多样性、基尼系数，而不是只看一个准确率。现在把"物品流行度的偏斜"拖到 0（所有物品一样热）。读数变成：扩散 8.0%，热度 8.0%，随机 12.5%。两个算法全都掉到随机以下。因为这时既没有热度信号，人均只看过 6 件物品的共现信息也纯粹是噪声。这条对照说明了一件很重要的事：推荐算法的效果里，有多少来自算法，有多少来自数据本身的偏斜？拖到 1.5：扩散 65.8%，热度 70.2%，随机 17.5%。命中率翻了一倍多，而算法一行都没改。报告推荐效果时不报数据的流行度分布，和报告分形维数不报 x_min 是一样的问题。（把推荐列表长度 K 从 10 拖到 30：三者的命中率都大涨（69.0% / 72.6% / 35.4%），而随机涨得最快。K 越大，任何算法离随机就越近——所以命中率必须标明 K，不同 K 的数字不能互相比较。）