{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T01:34:50Z","timestamp":1792028090602,"version":"4.4.0"},"reference-count":49,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research"],"published-print":{"date-parts":[[2017,2]]},"abstract":"<jats:p> The question of aggregating pairwise comparisons to obtain a global ranking over a collection of objects has been of interest for a very long time: be it ranking of online gamers (e.g., MSR\u2019s TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In most settings, in addition to obtaining a ranking, finding \u2018scores\u2019 for each object (e.g., player\u2019s rating) is of interest for understanding the intensity of the preferences. <\/jats:p><jats:p> In this paper, we propose Rank Centrality, an iterative rank aggregation algorithm for discovering scores for objects (or items) from pairwise comparisons. The algorithm has a natural random walk interpretation over the graph of objects with an edge present between a pair of objects if they are compared; the score, which we call Rank Centrality, of an object turns out to be its stationary probability under this random walk. <\/jats:p><jats:p> To study the efficacy of the algorithm, we consider the popular Bradley-Terry-Luce (BTL) model (equivalent to the Multinomial Logit (MNL) for pairwise comparisons) in which each object has an associated score that determines the probabilistic outcomes of pairwise comparisons between objects. In terms of the pairwise marginal probabilities, which is the main subject of this paper, the MNL model and the BTL model are identical. We bound the finite sample error rates between the scores assumed by the BTL model and those estimated by our algorithm. In particular, the number of samples required to learn the score well with high probability depends on the structure of the comparison graph. When the Laplacian of the comparison graph has a strictly positive spectral gap, e.g., each item is compared to a subset of randomly chosen items, this leads to dependence on the number of samples that is nearly order optimal. <\/jats:p><jats:p> Experimental evaluations on synthetic data sets generated according to the BTL model show that our algorithm performs as well as the maximum likelihood estimator for that model and outperforms other popular ranking algorithms. <\/jats:p>","DOI":"10.1287\/opre.2016.1534","type":"journal-article","created":{"date-parts":[[2016,10,18]],"date-time":"2016-10-18T17:03:43Z","timestamp":1476810223000},"page":"266-287","source":"Crossref","is-referenced-by-count":131,"title":["Rank Centrality: Ranking from Pairwise Comparisons"],"prefix":"10.1287","volume":"65","author":[{"given":"Sahand","family":"Negahban","sequence":"first","affiliation":[{"name":"Department of Statistics, Yale University, New Haven, Connecticut 06510"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sewoong","family":"Oh","sequence":"additional","affiliation":[{"name":"Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana\u2013Champaign, Urbana, Illinois 61801"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Devavrat","family":"Shah","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, Cambridge, Massachusetts 02139"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"109","reference":[{"key":"B1","first-page":"564","volume-title":"Proc. 5th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA \u201994","author":"Adler M","year":"1994"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9211-1"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411513"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064010"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1109\/Allerton.2011.6120246"},{"key":"B6","volume-title":"Social Choice and Individual Values","author":"Arrow KJ","year":"1963"},{"key":"B7","first-page":"240","volume-title":"Proc. Second Workshop Analytic Algorithms Combinatorics, ANALCO \u201905","author":"Boyd S","year":"2005"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.2307\/2334029"},{"key":"B9","first-page":"268","volume-title":"Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA \u201908","author":"Braverman M","year":"2008"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-009-9045-5"},{"key":"B12","volume-title":"Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix","author":"Condorcet M","year":"1785"},{"key":"B13","volume-title":"The Method of Paired Comparisons","author":"David HA","year":"1963"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005359"},{"key":"B16","first-page":"327","volume-title":"Proc. 27th Internat. Conf. Machine Learning, ICML \u201910","author":"Duchi JC","year":"2010"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1145\/371920.372165"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1145\/371920.372165"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.2307\/2308513"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020425"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553423"},{"key":"B23","first-page":"1475","volume-title":"Adv. Neural Inform. Processing Systems (NIPS)","author":"Hajek B","year":"2014"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_28"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511810817"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1079120141"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0419-x"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775242"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1137\/1035004"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.2307\/3001479"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/31.3-4.324"},{"issue":"1","key":"B32","first-page":"2057","volume":"11","author":"Keshavan RH","year":"2010","journal-title":"J. Machine Learn. Res."},{"key":"B33","first-page":"145","volume-title":"Proc. 28th Internat. Conf. Machine Learn. ICML \u201911","author":"Lu T","year":"2011"},{"key":"B34","volume-title":"Individual Choice Behavior","author":"Luce DR","year":"1959"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/44.1-2.114"},{"issue":"1","key":"B36","first-page":"105","volume":"1","author":"McFadden D","year":"1973","journal-title":"Frontiers Econometrics"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1007\/BF02313422"},{"issue":"1","key":"B38","first-page":"1665","volume":"13","author":"Negahban S","year":"2012","journal-title":"J. Machine Learn. Res."},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001"},{"key":"B40","first-page":"489","volume-title":"Proc. 30th Internat. Conf. Machine Learn., ICML \u201913","author":"Osting B","year":"2013"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.2307\/2346567"},{"key":"B42","first-page":"118","volume-title":"Proc. 31st Internat. Conf. Machine Learn., ICML \u201914","author":"Rajkumar A","year":"2014"},{"issue":"3","key":"B43","first-page":"81","volume":"37","author":"Rao CR","year":"1945","journal-title":"Bull. Calcutta Math. Soc."},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00227-8"},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1037\/h0084096"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2158885"},{"key":"B48","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2015.1455"},{"key":"B49","doi-asserted-by":"publisher","DOI":"10.1007\/b139000"},{"key":"B50","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9099-z"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187902"},{"key":"B53","unstructured":"Wei TH (1952) The algebraic foundations of ranking theory. Ph.D. thesis, University of Cambridge, Cambridge, UK."}],"container-title":["Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/opre.2016.1534","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T14:15:00Z","timestamp":1680444900000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/opre.2016.1534"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["10.1287\/opre.2016.1534"],"URL":"https:\/\/doi.org\/10.1287\/opre.2016.1534","relation":{},"ISSN":["0030-364X","1526-5463"],"issn-type":[{"value":"0030-364X","type":"print"},{"value":"1526-5463","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2]]}}}