Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons

Abstract Deriving global rankings from noisy pairwise comparisons is a fundamental problem with applications in sports analytics, preference aggregation, and evaluation. A natural way to obtain a consistent ordering is to represent the comparisons as a weighted directed graph and remove a set of arcs that breaks all directed cycles, leaving a directed acyclic graph (DAG) whose topological order induces a ranking; this leads directly to the Minimum Weighted Feedback Arc Set (MWFAS) problem. In this paper, we develop a lightweight, learning-free heuristic pipeline for MWFAS-based ranking. The method combines (i) local-ratio-inspired cycle peeling to obtain an initial acyclic backbone with (ii) weight-prioritized edge reinsertion that selectively restores high-confidence comparisons while maintaining acyclicity. We then apply an order-preserving post-processing step that adjusts score magnitudes without changing the induced ranking, improving score-based losses while keeping the same ordering. Across standard benchmark datasets and upset-loss evaluation metrics used in prior work on ranking from pairwise comparisons, our pipeline matches or improves baseline losses and runs substantially faster end-to-end, making it practical for large graphs.