A General Pairwise Comparison Model for Extremely Sparse Networks

References

• Agresti, A. (1992), “Analysis of Ordinal Paired Comparison Data,” Journal of the Royal Statistical Society, Series C, 41, 287–297. DOI: 10.2307/2347562.
   Web of Science ®Google Scholar
• Agresti, A. (2019), An Introduction to Categorical Data Analysis, Wiley Series in Probability and Statistics (3rd ed.), Hoboken, NJ: Wiley.
   Google Scholar
• Bradley, R. A., and Terry, M. E. (1952), “Rank Analysis of Incomplete Block Designs. I. The Method of Paired Comparisons,” Biometrika, 39, 324–345. DOI: 10.2307/2334029.
   Web of Science ®Google Scholar
• Cattelan, M. (2012), “Models for Paired Comparison Data: A Review with Emphasis on Dependent Data,” Statistical Science, 27, 412–433. DOI: 10.1214/12-STS396.
   Web of Science ®Google Scholar
• Chen, P., Gao, C., and Zhang, A. Y. (2020), “Partial Recovery for Top-k Ranking: Optimality of MLE and Sub-optimality of Spectral Method,” arXiv preprint arXiv:2006.16485.
   Google Scholar
• Chen, Y., Fan, J., Ma, C., and Wang, K. (2019), “Spectral Method and Regularized MLE are both Optimal for Top-K Ranking,” The Annals of Statistics, 47, 2204–2235. DOI: 10.1214/18-AOS1745.
   PubMed Web of Science ®Google Scholar
• Chen, Y., and Suh, C. (2015), “Spectral MLE: Top-k Rank Aggregation from Pairwise Comparisons,” in International Conference on Machine Learning, pp. 371–380.
   Google Scholar
• Chung, F. R. K. (1997), Spectral Graph Theory (Volume 92 of CBMS Regional Conference Series in Mathematics). Published for the Conference Board of the Mathematical Sciences, Washington, DC. Providence, RI: American Mathematical Society.
   Google Scholar
• David, H. A. (1988), The Method of Paired Comparisons (Volume 41 of Griffin’s Statistical Monographs & Courses, 2nd ed.), London: Charles Griffin & Co., Ltd.; New York: The Clarendon Press, Oxford University Press.
   Google Scholar
• Davidson, D., and Marschak, J. (1959), “Experimental Tests of a Stochastic Decision Theory,” Measurement: Definitions and Theories, 17, 233–269.
   Google Scholar
• Davidson, R. R. (1970), “On Extending the Bradley–Terry Model to Accommodate Ties in Paired Comparison Experiments,” Journal of the American Statistical Association, 65, 317–328. DOI: 10.1080/01621459.1970.10481082.
   Web of Science ®Google Scholar
• Dittrich, R., Francis, B., Hatzinger, R., and Katzenbeisser, W. (2007), “A Paired Comparison Approach for the Analysis of Sets of Likert-scale Responses,” Statistical Modelling, 7, 3–28. DOI: 10.1177/1471082X0600700102.
   Web of Science ®Google Scholar
• Erdős, P., and Rényi, A. (1960), “On the Evolution of Random Graphs,” A Magyar Tudományos Akadémia Matematikai Kutató Intézetének közleményei 5, 17–61.
   Google Scholar
• Fishburn, P. C. (1973), “Binary Choice Probabilities: On the Varieties of Stochastic Transitivity,” Journal of Mathematical Psychology, 10, 327–352. DOI: 10.1016/0022-2496(73)90021-7.
   Web of Science ®Google Scholar
• Ford Jr., L. R. (1957), “Solution of a Ranking Problem from Binary Comparisons,” The American Mathematical Monthly, 64, 28–33. DOI: 10.1080/00029890.1957.11989117.
   Google Scholar
• Han, R., Ye, R., Tan, C., and Chen, K. (2020), “Asymptotic Theory of Sparse Bradley–Terry Model,” Annals of Applied Probability, 30, 2491–2515.
   Web of Science ®Google Scholar
• Heckel, R., Shah, N. B., Ramchandran, K., and Wainwright, M. J. (2019), “Active Ranking from Pairwise Comparisons and When Parametric Assumptions do not Help,” The Annals of Statistics, 47, 3099–3126. DOI: 10.1214/18-AOS1772.
   Web of Science ®Google Scholar
• Holland, P. W., Laskey, K. B., and Leinhardt, S. (1983), “Stochastic Blockmodels: First Steps,” Social Networks, 5, 109–137. DOI: 10.1016/0378-8733(83)90021-7.
   Web of Science ®Google Scholar
• Hunter, D. R. (2004), “MM Algorithms for Generalized Bradley–Terry Models,” The Annals of Statistics, 32, 384–406. DOI: 10.1214/aos/1079120141.
   Web of Science ®Google Scholar
• Jang, M., Kim, S., Suh, C., and Oh, S. (2016), “Top-k Ranking from Pairwise Comparisons: When Spectral Ranking is Optimal,” arXiv preprint arXiv:1603.04153.
   Google Scholar
• Luce, R. D. (1959), Individual Choice Behavior: A Theoretical Analysis, New York: Wiley; London: Chapman & Hall, Ltd.
   Google Scholar
• Maydeu-Olivares, A. (2001), “Limited Information Estimation and Testing of Thurstonian Models for Paired Comparison Data Under Multiple Judgment Sampling,” Psychometrika, 66, 209–227. DOI: 10.1007/BF02294836.
   Web of Science ®Google Scholar
• Maydeu-Olivares, A. (2002), “Limited Information Estimation and Testing of Thurstonian Models for Preference Data,” Mathematical Social Sciences, 43, 467–483.
   Web of Science ®Google Scholar
• Maystre, L., and Grossglauser, M. (2015), “Fast and Accurate Inference of Plackett–Luce Models,” in Advances in Neural Information Processing Systems, pp. 172–180.
   Google Scholar
• Mosteller, F. (2006), “Remarks on the Method of Paired Comparisons: I. The Least Squares Solution Assuming Equal Standard Deviations and Equal Correlations,” in Selected Papers of Frederick Mosteller, eds. S. E. Fienberg and D. C. Hoaglinpp, pp. 157–162, New York: Springer.
   Google Scholar
• Negahban, S., Oh, S., and Shah, D. (2017), “Rank Centrality: Ranking from Pairwise Comparisons,” Operations Research, 65, 266–287. DOI: 10.1287/opre.2016.1534.
   Web of Science ®Google Scholar
• Plackett, R. L. (1975), “The Analysis of Permutations,” Journal of the Royal Statistical Society, Series C, 24, 193–202. DOI: 10.2307/2346567.
   Web of Science ®Google Scholar
• Rao, P. V., and Kupper, L. L. (1967), “Ties in Paired-Comparison Experiments: A Generalization of the Bradley–Terry Model,” Journal of the American Statistical Association, 62, 194–204.
   Web of Science ®Google Scholar
• Shah, N. B., Balakrishnan, S., Bradley, J., Parekh, A., Ramchandran, K., and Wainwright, M. J. (2016), “Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence,” Journal of Machine Learning Research, 17: Paper No. 58, 47.
   Web of Science ®Google Scholar
• Shah, N. B., Balakrishnan, S., Guntuboyina, A., and Wainwright, M. J. (2017), “Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues,” IEEE Transactions on Information Theory, 63, 934–959. DOI: 10.1109/TIT.2016.2634418.
   Web of Science ®Google Scholar
• Simons, G., and Yao, Y.-C. (1999), “Asymptotics When the Number of Parameters Tends to Infinity in the Bradley–Terry Model for Paired Comparisons,” The Annals of Statistics, 27, 1041–1060. DOI: 10.1214/aos/1018031267.
   Web of Science ®Google Scholar
• Stern, H. (1990), “A Continuum of Paired Comparisons Models,” Biometrika, 77, 265–273. DOI: 10.1093/biomet/77.2.265.
   Web of Science ®Google Scholar
• Thurstone, L. L. (1927), “A Law of Comparative Judgment,” Psychological Review, 34, 273–286. DOI: 10.1037/h0070288.
   Google Scholar
• Yan, T., Yang, Y., and Xu, J. (2012), “Sparse Paired Comparisons in the Bradley–Terry Model,” Statistica Sinica, 22, 1305–1318. DOI: 10.5705/ss.2010.299.
   Web of Science ®Google Scholar
• Zermelo, E. (1929), “Die Berechnung der Turnier-Ergebnisse als ein Maximumproblem der Wahrscheinlichkeitsrechnung,” Mathematische Zeitschrift, 29, 436–460. DOI: 10.1007/BF01180541.
   Google Scholar