AAAINov, 2019

社会选择中超越两两比较的问题：一个基于集合的 Kemeny 聚合问题

PDF
TL;DR本文介绍使用集合竞赛来将一组输入排名汇总成一个输出排名，引入了 Kemeny 规则的一种泛化版本，其中将最小化 k-wise 不一致的数量作为目标，介绍了大多数图的 k-wise 对应物，并提供了 k-wise Kemeny 聚合问题的近似算法。
setwise contestskemeny rulemajority graphconsensus rankingspearman distance
发现论文，激发创造
  • 集合型 Kemeny 投票方案的最优多数规则和数量化的 Condorcet 特性

    该论文研究了基于 Kemeny 规则的选举中位数共识排名问题，并通过详细说明各种相对排序的实际应用，提出了解决 $3$-wise Kemeny 问题的一些技术方法，使得该问题具有了许多重要的性质和应用。

    Apr, 2023

  • 三元肯尼问题的空间缩减技术

    本文通过左式方法给 Kemeny's rule 一定的广义，探讨了 $3$-wise Kemeny voting scheme 的更多应用和优势，证明了这个方法的非常有用，时空复杂度相较于经典的 Kemeny rule 更优，并且可以防止更多的操纵。

    Apr, 2023

  • Kemeny 排名聚合的多样性：参数化方法

    研究表明，通过将方案多样性与参数化复杂性理论相结合，可以使用基于算法的框架解决实际相关问题，例如 Kemeny Rank 聚合问题。

    May, 2021

  • 不同 Kemeny 排名聚合的参数化方面

    Kemeny 方法是一种用于排名整合的热门工具，我们研究了在参数化复杂性条件下计算不同 Kemeny 排名的问题，并提供了已有的 FPT 算法和近似算法。

    Sep, 2023

  • SetRank：基于集合贝叶斯方法的隐式反馈协同排名

    本文提出了一种基于集合的贝叶斯方法 SetRank 用于协同排序，旨在最大化新颖的集合偏好比较的后验概率。同时作者还经过理论分析表明误差的上界与用户和产品数量成正比。最后，四个真实世界数据集的广泛实验清楚地验证了 SetRank 相对于各种现有技术基线的优越性。

    Feb, 2020

  • 顺序对抗排序聚合：理论与算法

    通过对强有力的潜在对手进行在线攻击，从博弈论的视角提出了一种关于排名聚合方法的对抗性操纵解决方案，并展示了如何通过顺序操纵策略在具有完全知识或不完全知识的 attackers 下实现最优效果。

    Jul, 2024

  • 简单、健壮且最优排名的配对比较

    本研究旨在通过成对比较的数据形式，使用 Copeland 计数算法实现对 n 个项目的排序，使其具有计算效率高，鲁棒性强，接近信息论极限等特点，并将结果扩展到汉明距离度量下的近似恢复问题和任意错误要求条件下的恢复问题。

    Dec, 2015

  • 通过谱方法改进的排名聚合的理论保证

    给定多个项目之间的成对比较，如何对它们进行排名，以使得排名与观察结果相匹配？本研究关注基于 Erdos-Renyi 异常值（ERO）模型的排名问题，在该问题中，每个成对比较都是真实分数差异的损坏副本。通过研究基于非归一化和归一化数据矩阵的谱排名算法，我们提供了每个项目从观察数据中恢复出其潜在分数的性能，并得出了非归一化 / 归一化数据矩阵的最大特征向量与其总体对应物之间的逐项扰动误差界限。通过留一法技术，我们提供了更精确的最大特征向量的 l∞范数扰动界限，并在只有 Ω(nlogn) 个样本的情况下导出了每个项目的最大偏移误差界限。理论分析在样本复杂度方面改进了现有技术的结果，并通过数值实验验证了这些理论发现。

    Sep, 2023

  • 基于配对比较的近似排名

    研究在机器学习中，基于两两比较对一组 n 个项目进行排名的问题，提出了一种基于置信区间的活跃排名算法，通过近似排序来减少比较次数。

    Jan, 2018

  • 统计排名与组合霍奇理论

    使用图 Helmholtzian 和组合 Hodge 理论，基于边缘流的成对排名可以解析为两个正交成分，其中一个表示 L2 最优全局排名，而另一个表示无旋转流，同时还可以通过线性最小二乘回归计算离散的 Hodge 分解。

    Nov, 2008