论文链接：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)