Metric Distortion of Social Welfare Functions

在决策的世界里，从招聘一名新员工到为小组之夜选择一部电影，我们经常依赖人们来排列他们的偏好。我们会问：“谁是你的最爱？”或者“你的首选是什么？”并利用这些答案来进行集体决策。几十年来，研究人员一直在研究当人们不知道每个人对每个选项的价值确切程度时，这些排名如何转化为良好的结果。他们发现，即使不知道一个人情感的精确强度，仅仅知道他们的偏好顺序就能带来令人惊讶的公平结果。然而，这项工作的重点大多集中在挑选单一赢家上，比如一位总统或一位最佳候选人。现实生活通常更加复杂。我们经常需要创建一个完整的列表，将所有人从第一名到最后一名进行排序，例如大学录取等待名单或产品推荐列表。在这些场景中，位置至关重要。排名第一可能至关重要，而排名第十可能与排名垫底几乎没有区别。问题在于：如果我们只知道人们偏好的顺序，但不知道他们对第一名和第二名之间的差异有多在意，我们该如何构建一个让每个人都满意的完整列表？

一组研究人员现在解决了这一特定挑战，探索了在选民对不同位置有不同重视程度的情况下，如何构建一个完整的排名。他们设想了一个场景：每个人都有一个隐藏的价值尺度，决定了他们对顶端位置与底端位置的重视程度。有些人可能只关心第一个推荐，而另一些人则可能愿意在找到合适的选项之前浏览多个选项。研究人员想知道，即使在看不到这些隐藏尺度的情形下，一种投票系统是否能创建一个公平、高质量的排名。他们发现，答案完全取决于系统被允许使用哪些信息。如果系统准确知道每个人对每个位置的价值，它就可以构建出一个质量最高的排名，实现为 3 的最优失真（optimal distortion）。如果系统不知道具体的价值，但知道每个人共享相同的隐藏尺度，它仍然可以做得很好，其结果的质量取决于该共享尺度的变化程度。

最困难的情况出现在系统对权重一无所知，且每个人都有自己独特的、隐藏的尺度时。在这种情况下，研究人员证明，无论投票规则多么巧妙，结果的质量都不可避免地会随着候选人数量的增加而下降。他们表明，结果中的误差会随着被排名的候选人数量呈线性增长。简单来说，如果你是在为一个小群体进行排名，系统可以做得不错；但如果你是在为一个庞大的群体进行排名，由于缺乏关于人们对特定位置有多在意的相关信息，想要保证一个好的结果是不可能的。这一发现凸显了一个基本限制：如果不了解选民如何衡量列表不同位置的权重，为大型群体提供完美的排名是无法实现的。

研究人员通过建立一种逐步创建这些排名的方法来测试他们的想法。想象一下正在逐一填充列表，从顶端开始。在每一步中，系统根据当前的偏好为该特定位置挑选出最佳的可用候选人。他们发现，如果系统知道权重，这种简单的逐步法依然是最优的，能够实现为 3 的最佳失真。他们使用了一种特定的、复杂的挑选每步获胜者的算法，这使得他们能够证明，在这些约束条件下，最终生成的列表将与理论上的最佳列表一样优秀。这是一个重要的发现，因为它表明，只要系统拥有正确的信息，创建一个完整的列表并不需要牺牲质量来对比仅挑选单一赢家的做法。

当权重是隐藏且由所有人共享时，研究人员发现同样的逐步法仍然有效，但结果的质量会根据共享尺度的形状而变化。如果每个人对每个位置的重视程度大致相同，系统的失真度为 1，这意味着结果与最优社会福利完美契合。如果每个人都只在意顶端位置，系统的表现将与仅挑选单一赢家时的表现完全一致。其性能在两者之间平滑过渡。研究人员提供了一个精确的性能公式，展示了群体的价值差异是如何影响最终结果的。

然而，当权重既隐藏又因人而异时，故事发生了彻底的变化。研究人员证明，在这种混乱的环境下，系统无法避免质量的大幅下降。他们构建了特定的案例，显示出在不知道权重的情况下，任何投票规则所能产生的最佳排名都远逊于理论上的最佳排名。他们证明，最佳结果与实际结果之间的差距会随着候选人数量的增加而直接增长。对于十个候选人的列表，误差很小；对于一百个候选人的列表，误差则大得多。这一结果排除了通过更巧妙的算法来解决问题的希望。它建立了一个硬性边界：要为大型群体获得高质量的排名，你必须要么了解人们如何衡量位置的权重，要么接受结果是不完美的。

研究还考察了人们进行数值归一化的两种不同方式。在一种情景中，每个人都在整个列表中分配固定总量的价值，就像在所有位置之间分配一美元一样。在另一种情景中，每个人都给顶端位置设定固定的值为 1，而不论他们如何看待其余位置。研究人员发现，在这两种现实场景中，隐藏且不同的权重问题都会导致误差的线性增长。无论选民如何构建他们的内部尺度，如果系统无法看到这些尺度且它们因人而异，排名的质量都会随着列表变长而退化。这为推荐系统设计者或招聘委员会提供了一个明确的警告：如果你处理的是一个具有不同优先级的多样化群体，你不能依靠简单的排名方法来产生完美的列表，而不去收集更多关于他们偏好的具体数据。

最终，这项工作阐明了我们在信息有限的情况下所能达到的极限。它表明，通往良好集体决策的路径在很大程度上取决于可用信息的结构。当我们知道权重时，我们可以实现为 3 的最优失真。当我们知道权重对所有人都是一致时，如果权重是均匀的，我们可以实现为 1 的失真；或者根据变化程度，实现一个介于 1 与单一赢家界限之间的结果。但当权重既隐藏又因人而异时，我们会撞上一堵墙，即群体的规模将决定结果的质量。研究人员不仅提出了一种新的投票方式，他们还绘制了可能性的边界，清晰地展示了当信息缺失时，公平与效率的规则在哪里失效。他们的发现为任何试图将偏好聚合为完整排名的人提供了实践指南，提醒我们：任务的复杂程度随参与者的多样性而增长。