IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v65y2018i1p266-287.html
   My bibliography  Save this article

Rank Centrality: Ranking from Pairwise Comparisons

Author

Listed:
  • Sahand Negahban

    (Department of Statistics, Yale University, New Haven, Connecticut 06510)

  • Sewoong Oh

    (Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana–Champaign, Urbana, Illinois 61801)

  • Devavrat Shah

    (Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, Cambridge, Massachusetts 02139)

Abstract

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’s 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 ‘scores’ for each object (e.g., player’s rating) is of interest for understanding the intensity of the preferences. 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. 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. 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.

Suggested Citation

  • Sahand Negahban & Sewoong Oh & Devavrat Shah, 2017. "Rank Centrality: Ranking from Pairwise Comparisons," Operations Research, INFORMS, vol. 65(1), pages 266-287, February.
    • Handle: RePEc:inm:oropre:v:65:y:2018:i:1:p:266-287
    DOI: 10.287/opre.2016.1534
    as

    Download full text from publisher

    File URL: https://doi.org/10.287/opre.2016.1534
    Download Restriction: no
    File URL: https://libkey.io/10.287/opre.2016.1534?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. R. L. Plackett, 1975. "The Analysis of Permutations," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 24(2), pages 193-202, June.
    2. Saaty, Thomas L., 2003. "Decision-making with the AHP: Why is the principal eigenvector necessary," European Journal of Operational Research, Elsevier, vol. 145(1), pages 85-91, February.
    3. Frederick Mosteller, 1951. "Remarks on the method of paired comparisons: II. The effect of an aberrant standard deviation when equal standard deviations and equal correlations are assumed," Psychometrika, Springer;The Psychometric Society, vol. 16(2), pages 203-206, June.
    4. Frederick Mosteller, 1951. "Remarks on the method of paired comparisons: I. The least squares solution assuming equal standard deviations and equal correlations," Psychometrika, Springer;The Psychometric Society, vol. 16(1), pages 3-9, March.
    5. Devavrat Shah & Tauhid Zaman, 2016. "Finding Rumor Sources on Random Trees," Operations Research, INFORMS, vol. 64(3), pages 736-755, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Dipankar Das, 2023. "A Model of Competitive Assortment Planning Algorithm," Papers 2307.09479, arXiv.org.
    2. Carrizosa, Emilio & Guerrero, Vanesa & Romero Morales, Dolores, 2019. "Visualization of complex dynamic datasets by means of mathematical optimization," Omega, Elsevier, vol. 86(C), pages 125-136.
    3. Weijie J. Su, 2022. "A Truthful Owner-Assisted Scoring Mechanism," Papers 2206.08149, arXiv.org.
    4. Yangming Zhou & Jin-Kao Hao & Zhen Li, 2024. "Heuristic Search for Rank Aggregation with Application to Label Ranking," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 308-326, March.
    5. Christis Katsouris, 2023. "Statistical Estimation for Covariance Structures with Tail Estimates using Nodewise Quantile Predictive Regression Models," Papers 2305.11282, arXiv.org, revised Jul 2023.
    6. Tino Werner, 2022. "Elicitability of Instance and Object Ranking," Decision Analysis, INFORMS, vol. 19(2), pages 123-140, June.
    7. Alwyn Lim & Shawn Pope, 2022. "What drives companies to do good? A “universal” ordering of corporate social responsibility motivations," Corporate Social Responsibility and Environmental Management, John Wiley & Sons, vol. 29(1), pages 233-255, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sahand Negahban & Sewoong Oh & Devavrat Shah, 2017. "Rank Centrality: Ranking from Pairwise Comparisons," Operations Research, INFORMS, vol. 65(1), pages 266-287, February.
    2. Mukhtar Ali, 1998. "Probability models on horse-race outcomes," Journal of Applied Statistics, Taylor & Francis Journals, vol. 25(2), pages 221-229.
    3. Jayanti Gupta & Paul Damien, 2002. "Conjugacy class prior distributions on metric‐based ranking models," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 64(3), pages 433-445, August.
    4. Lendie Follett & Heath Henderson, 2022. "A hybrid approach to targeting social assistance," Papers 2201.01356, arXiv.org.
    5. Centola, Damon & van de Rijt, Arnout, 2015. "Choosing your network: Social preferences in an online health community," Social Science & Medicine, Elsevier, vol. 125(C), pages 19-31.
    6. Csató, László, 2013. "Rangsorolás páros összehasonlításokkal. Kiegészítések a felvételizői preferencia-sorrendek módszertanához [Paired comparisons ranking. A supplement to the methodology of application-based preferenc," Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), Közgazdasági Szemle Alapítvány (Economic Review Foundation), vol. 0(12), pages 1333-1353.
    7. Osei, Prince P. & Davidov, Ori, 2022. "Bayesian linear models for cardinal paired comparison data," Computational Statistics & Data Analysis, Elsevier, vol. 172(C).
    8. Éva Orbán-Mihálykó & Csaba Mihálykó & László Koltay, 2019. "Incomplete paired comparisons in case of multiple choice and general log-concave probability density functions," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(2), pages 515-532, June.
    9. Maryam Aghayerashti & Ehsan Bahrami Samani & Mojtaba Ganjali, 2023. "Bayesian Latent Variable Model of Mixed Correlated Rank and Beta-Binomial Responses with Missing Data for the International Statistical Literacy Project Poster Competition," Sankhya B: The Indian Journal of Statistics, Springer;Indian Statistical Institute, vol. 85(1), pages 210-250, May.
    10. Donald Martin, 1999. "Paired comparison models applied to the design of the Major League baseball play-offs," Journal of Applied Statistics, Taylor & Francis Journals, vol. 26(1), pages 69-80.
    11. László Csató, 2015. "A graph interpretation of the least squares ranking method," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 44(1), pages 51-69, January.
    12. Éva Orbán-Mihálykó & Csaba Mihálykó & László Koltay, 2019. "A generalization of the Thurstone method for multiple choice and incomplete paired comparisons," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(1), pages 133-159, March.
    13. Kwan, Ying Keung & Ip, Wai Cheung & Kwan, Patrick, 2000. "A crime index with Thurstone's scaling of crime severity," Journal of Criminal Justice, Elsevier, vol. 28(3), pages 237-244.
    14. Elliott, Michael A., 2010. "Selecting numerical scales for pairwise comparisons," Reliability Engineering and System Safety, Elsevier, vol. 95(7), pages 750-763.
    15. Jose Pina-Sánchez & John Paul Gosling, 2020. "Tackling selection bias in sentencing data analysis: a new approach based on a scale of severity," Quality & Quantity: International Journal of Methodology, Springer, vol. 54(3), pages 1047-1073, June.
    16. Julio González-Díaz & Ruud Hendrickx & Edwin Lohmann, 2014. "Paired comparisons analysis: an axiomatic approach to ranking methods," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(1), pages 139-169, January.
    17. Dennie van Dolder & Vincent Buskens, 2014. "Individual Choices in Dynamic Networks: An Experiment on Social Preferences," PLOS ONE, Public Library of Science, vol. 9(4), pages 1-16, April.
    18. Harman, Wyatte L. & Eidman, Vernon R. & Hatch, Roy E. & Claypool, P. L., 1972. "Relating Farm and Operator Characteristics to Multiple Goals," Journal of Agricultural and Applied Economics, Cambridge University Press, vol. 4(1), pages 215-220, July.
    19. Araki, Kenji & Hirose, Yoshihiro & Komaki, Fumiyasu, 2019. "Paired comparison models with age effects modeled as piecewise quadratic splines," International Journal of Forecasting, Elsevier, vol. 35(2), pages 733-740.
    20. Vincent Buskens & Jeroen Weesie, 2000. "An Experiment On The Effects Of Embeddedness In Trust Situations," Rationality and Society, , vol. 12(2), pages 227-253, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:65:y:2018:i:1:p:266-287. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.