论文链接：https://arxiv.org/abs/2010.13020
常用投票规则下的优胜者决定问题（winner determination）的计算复杂性是计算社会选择（computational social choice）领域中历史悠久的基本问题。从实际应用的角度出发，我们往往希望优胜者决定问题的计算复杂性比较低。然而对于一些经典投票规则例如 Kemeny，Slater 等，其优胜者决定问题在最坏情况（worst-case）下已被证明是 NP-hard 的，即对于大规模问题实例，目前暂不存在高效的算法来确定优胜者。平均情况（average-case）分析虽然比最坏情况分析稍微实际一些，但是其对于输入实例的分布假设相当敏感：例如在计算社会选择理论中被称为 Impartial Culture 的假设，要求投票者对于候选者的排序服从独立的均匀随机分布。许多经验性证据表明这类分布假设并不贴近现实。
Spielman and Teng（2004）引入了平滑分析（smoothed analysis），拓展并结合了最坏情况分析与平均情况分析。其主要想法是算法的输入数据往往是真实值（ground truth）的微小扰动之后的值。对于任何确定的问题实例，自然会在上面加一个诸如高斯噪音的小扰动形成概率分布，而算法的运行时间是该分布下的期望运行时间。由此，算法的平滑运行时间定义如下图所示：
通过改变扰动的幅度，平滑运行时间完美地架起了最坏情况运行时间与平均情况运行时间之间的桥梁。可以看出，当扰动趋于零时，平滑运行时间等价于最坏情形运行时间，而当扰动非常大时，平滑运行时间等价于均匀分布下的算法运行时间。对于适当的扰动幅度，平滑分析能够结合两者优点，提供接近真实数据与现实应用场景的算法分析。
平滑分析最著名的应用是线性规划问题，它为最坏情况下需要指数多步骤的单纯形法为什么在实际中的运行速度非常快提供了有力且令人信服的解释。在机器学习，均衡分析，组合优化等领域，平滑分析也得到了广泛应用。例如纳什均衡计算的平滑复杂度是PPAD-complete的。然而，常用投票规则下的优胜者决定问题，乃至任何计算社会选择领域内的计算问题的平滑复杂性却没有任何结果。
实际上，这个问题不仅仅是计算社会选择领域内的理论问题。由于投票机制是自动决策系统中的重要一环，平滑复杂性的研究对于人工智能中也有实际意义。考虑如下例子：当一个智能系统的开发者为了群体决策想要实现一种投票规则例如 Kemeny 来达到共识。这个系统需要估计计算 Kemeny 优胜者的运行时间，来决定分配多少计算资源以获得及时的决策。它可以通过智能体过往的行为来学习并预测其偏好，但是只能得到关于偏好排序的概率分布。这个概率分布可以刻画成真实偏好排序加上随机噪音后的结果。在这种情况下，是否存在一种期望运行时间是多项式的算法呢？
本文首次提供了如下公开问题的理论结果：常用投票机制下的优胜者决定问题的平滑复杂性是什么？
我们采用了单人偏好模型（single agent preference model, Xia (2020)）来分析这个问题。在此模型下，每个投票者可以选择集合中的任何一个偏好概率分布（等价于存在一个恶意对手为每个投票者选择任意相关的真实偏好，然后自然为每个投票者加上独立的扰动）。我们证明了如下定理：
[定理]：对于满足一定条件的单人偏好模型，如果存在平滑运行时间为多项式的计算 Kemeny 或者 Slater 的算法，那么 NP=RP。
定理中对于单人偏好模型的假设覆盖了一大类计算社会选择领域内已知的统计模型，而 NP=RP 一般被认为是不成立的（常见的复杂性理论假设）。因此，该定理指出在平滑分析框架下，Kemeny 和 Slater 规则的优胜者决定问题依旧是困难的。虽然如此，我们得到关于参数化一般情形平滑复杂性的部分正面结果：对于一大类基于计算社会选择中经典的 Mallows 统计模型的单人偏好模型，原有的动态规划算法对于参数规模受限问题实例以高概率在多项式时间内输出结果。
图文 | 郑炜强
Distributed and Automated Games and Managerial Economics (daGAME)
