Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons
This work addresses the Ranking Problem for applications relying on pairwise comparisons, offering a novel, learning-free approach that improves upon recent learning-based methods.
The paper tackled the Ranking Problem by developing efficient combinatorial algorithms for the Minimum Weighted Feedback Arc Set (MWFAS) problem, resulting in algorithms that significantly outperform learning-based methods in speed and generally achieve superior ranking accuracy.
The Minimum Weighted Feedback Arc Set (MWFAS) problem is fundamentally connected to the Ranking Problem -- the task of deriving global rankings from pairwise comparisons. Recent work [He et al. ICML2022] has advanced the state-of-the-art for the Ranking Problem using learning-based methods, improving upon multiple previous approaches. However, the connection to MWFAS remains underexplored. This paper investigates this relationship and presents efficient combinatorial algorithms for solving MWFAS, thus addressing the Ranking Problem. Our experimental results demonstrate that these simple, learning-free algorithms not only significantly outperform learning-based methods in terms of speed but also generally achieve superior ranking accuracy.