Learning-Free Ranking from Pairwise Comparisons via Feedback-Arc-Set Pruning and Add-Back

Learning-Free Ranking from Pairwise Comparisons via Feedback-Arc-Set Pruning and Add-Back | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Learning-Free Ranking from Pairwise Comparisons via Feedback-Arc-Set Pruning and Add-Back Soroush Vahidi This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-9281720/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Deriving global rankings from noisy and incomplete pairwise comparisons is a fundamental problem with applications in sports analytics, preference aggregation, and evaluation. Many recent approaches rely on learning-based models, but in practice ranking systems are often required to operate under strict constraints on training cost, runtime, and reproducibility. We study a scalable, training-free alternative that constructs rankings directly from weighted directed comparison graphs. Our approach represents pairwise comparisons as a weighted digraph and leverages the connection between ranking inconsistency and feedback-arc-set removal to build an acyclic comparison backbone. The proposed pipeline is time-bounded and consists of three stages: a local-ratio-style cycle-breaking heuristic, a stable weight-prioritized add-back procedure with up to three passes while preserving acyclicity, and an optional bounded score-refinement stage under upset-based objectives used in recent ranking benchmarks. The resulting method outputs a real-valued score vector whose induced order is consistent with the recovered acyclic structure. Across the benchmark suite used in recent ranking-from-comparisons work, the proposed method is competitive with strong classical baselines and delivers substantial runtime advantages over training-based GNNRank configurations under fixed wall-clock budgets. These results position the method as a practical, deterministic, and scalable alternative for ranking on large pairwise-comparison graphs when training cost and deployment efficiency are important. Ranking Pairwise comparisons Feedback arc set Directed graphs Training-free methods Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-9281720","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":617470727,"identity":"37ef563e-a64e-4530-b758-54bfa4d3b74f","order_by":0,"name":"Soroush Vahidi","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAqElEQVRIiWNgGAWjYFAC5oMPPjCw8YCYEkRqYUs2nAHUwkOCFh4zYZBy4rXIz8gxY7bdwSdjD3ThbR5itBjcSCt7nHsG5DC2ZGvitPAc3m6c2wbSwmMmTZQW+Z4DZtKWYC3834jTwnC8xUyaEWILG3FaDI63JRv2grQcZjO2nEOUw5qBUfmz7Zg9e3vzwxtviHIYBBwDpgISlINADYnqR8EoGAWjYEQBAEmDJlnRWbXtAAAAAElFTkSuQmCC","orcid":"","institution":"New Jersey Institute of Technology","correspondingAuthor":true,"prefix":"","firstName":"Soroush","middleName":"","lastName":"Vahidi","suffix":""}],"badges":[],"createdAt":"2026-03-31 15:08:59","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-9281720/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-9281720/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":107459375,"identity":"7a4c4b03-3be2-4520-92f9-c462d92a33a6","added_by":"auto","created_at":"2026-04-21 16:29:21","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":267077,"visible":true,"origin":"","legend":"","description":"","filename":"ScalableandTrainingFreeRankingfromPairwiseComparisonsviaAcyclicGraphConstruction.pdf","url":"https://assets-eu.researchsquare.com/files/rs-9281720/v1_covered_5659e26b-10b9-4845-9ea9-4de4509a5638.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Learning-Free Ranking from Pairwise Comparisons via Feedback-Arc-Set Pruning and Add-Back","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":true,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Ranking, Pairwise comparisons, Feedback arc set, Directed graphs, Training-free methods","lastPublishedDoi":"10.21203/rs.3.rs-9281720/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-9281720/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Deriving global rankings from noisy and incomplete pairwise comparisons is a fundamental problem with applications in sports analytics, preference aggregation, and evaluation. Many recent approaches rely on learning-based models, but in practice ranking systems are often required to operate under strict constraints on training cost, runtime, and reproducibility. We study a scalable, training-free alternative that constructs rankings directly from weighted directed comparison graphs.\nOur approach represents pairwise comparisons as a weighted digraph and leverages the connection between ranking inconsistency and feedback-arc-set removal to build an acyclic comparison backbone. The proposed pipeline is time-bounded and consists of three stages: a local-ratio-style cycle-breaking heuristic, a stable weight-prioritized add-back procedure with up to three passes while preserving acyclicity, and an optional bounded score-refinement stage under upset-based objectives used in recent ranking benchmarks. The resulting method outputs a real-valued score vector whose induced order is consistent with the recovered acyclic structure.\nAcross the benchmark suite used in recent ranking-from-comparisons work, the proposed method is competitive with strong classical baselines and delivers substantial runtime advantages over training-based GNNRank configurations under fixed wall-clock budgets. These results position the method as a practical, deterministic, and scalable alternative for ranking on large pairwise-comparison graphs when training cost and deployment efficiency are important.","manuscriptTitle":"Learning-Free Ranking from Pairwise Comparisons via Feedback-Arc-Set Pruning and Add-Back","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-04-21 16:29:12","doi":"10.21203/rs.3.rs-9281720/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"36cdfa53-4c2e-4ce7-8275-7141bafdf077","owner":[],"postedDate":"April 21st, 2026","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2026-04-21T16:29:12+00:00","versionOfRecord":[],"versionCreatedAt":"2026-04-21 16:29:12","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-9281720","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-9281720","identity":"rs-9281720","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}