Lagrangian Inference for Ranking Problems

References

• Adelman D (2020) An efficient frontier approach to scoring and ranking hospital performance. Oper. Res. 68(3):762–792.Link, Google Scholar
• Adler M, Gemmell P, Harchol-Balter M, Karp RM, Kenyon C (1994) Selection in the presence of noise: The design of playoff systems. Proc. 5th Annual ACM-SIAM Sympos. on Discrete Algorithms, 564–572.Google Scholar
• Ailon N (2010) Aggregation of partial rankings, p-ratings and top-m lists. Algorithmica 57(2):284–300.Crossref, Google Scholar
• Ailon N, Charikar M, Newman A (2008) Aggregating inconsistent information: ranking and clustering. J. ACM 55(5):1–27.Crossref, Google Scholar
• Altman A, Tennenholtz M (2005) Ranking systems: The PageRank axioms. Proc. 6th ACM Conf. on Electronic Commerce, 1–8.Google Scholar
• Ammar A, Shah D (2011) Ranking: Compare, don’t score. Proc. 49th Annual Allerton Conf. on Comm., Control, and Computing (IEEE, New York), 776–783.Google Scholar
• Ammar A, Shah D (2012) Efficient rank aggregation using partial data. Performance Evaluation Rev. 40(1):355–366.Crossref, Google Scholar
• Aouad A, Farias V, Levi R, Segev D (2018) The approximability of assortment optimization under ranking preferences. Oper. Res. 66(6):1661–1669.Link, Google Scholar
• Azari Soufiani H, Chen WZ, Parkes DC, Xia L (2013) Generalized method-of-moments for rank aggregation. Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. Adv. Neural Inform. Processing Systems 2706–2714.Google Scholar
• Baltrunas L, Makcinskas T, Ricci F (2010) Group recommendations with rank aggregation and collaborative filtering. Proc. 4th ACM Conf. on Recommender Systems, 119–126.Google Scholar
• Benjamini Y, Hochberg Y (1995) Controlling the false discovery rate: A practical and powerful approach to multiple testing. J. Royal Statist. Soc. B 57(1):289–300.Crossref, Google Scholar
• Benjamini Y, Yekutieli D (2001) The control of the false discovery rate in multiple testing under dependency. Ann. Statist. 29(4)1165–1188.Google Scholar
• Beutel A, Chen J, Doshi T, Qian H, Wei L, Wu Y, Heldt L, et al.(2019) Fairness in recommendation ranking through pairwise comparisons. Proc. 25th ACM SIGKDD Internat. Conf. on Knowledge Discovery & Data Mining, 2212–2220.Google Scholar
• Bouadjenek MR, Hacid H, Bouzeghoub M (2013) Sopra: A new social personalized ranking function for improving web search. Proc. 36th Internat. ACM SIGIR Conf. on Res. and Development in Inform. Retrieval, 861–864.Google Scholar
• Boulesteix AL, Slawski M (2009) Stability and aggregation of ranked gene lists. Brief Bioinform. 10(5):556–568.Crossref, Google Scholar
• Bradley RA, Terry ME (1952) Rank analysis of incomplete block designs: I. The method of paired comparisons. Biometrika 39(3–4):324–345.Crossref, Google Scholar
• Brown LD (2003) Ranking journals using social science research network downloads. Rev. Quant. Finance Accounting 20(3):291–307.Crossref, Google Scholar
• Busa-Fekete R, Szorenyi B, Cheng W, Weng P, Hüllermeier E (2013) Top-k selection based on adaptive sampling of noisy preferences. Proc. Internat. Conf. on Machine Learn., 1094–1102.Google Scholar
• Cai T, Liu W, Luo X (2011) A constrained L1 minimization approach to sparse precision matrix estimation. J. Amer. Statist. Assoc. 106(494):594–607.Crossref, Google Scholar
• Candès EJ, Recht B (2009) Exact matrix completion via convex optimization. Foundations Comput. Math. 9(6):717–772.Crossref, Google Scholar
• Casella G, Berger RL (2021) Statistical Inference (Cengage Learning, Boston).Google Scholar
• Chen P, Gao C, Zhang AY (2020) Partial recovery for top-k ranking: Optimality of MLE and suboptimality of spectral method. Preprint, submitted June 30, https://arxiv.org/abs/2006.16485.Google Scholar
• Chen P, Gao C, Zhang AY (2021) Optimal full ranking from pairwise comparisons. Preprint, submitted January 21, https://arxiv.org/abs/2101.08421.Google Scholar
• Chen X, Chen Y, Li X (2022) Asymptotically optimal sequential design for rank aggregation. Math. Oper. Res. 47(3):2310–2332.Google Scholar
• Chen X, Jiao K, Lin Q (2016) Bayesian decision process for cost-efficient dynamic ranking via crowdsourcing. J. Machine Learn. Res. 17(1):7617–7656.Google Scholar
• Chen X, Li Y, Mao J (2018b) A nearly instance optimal algorithm for top-k ranking under the multinomial logit model. Proc. 29th Annual ACM-SIAM Sympos. on Discrete Algorithms, 2504–2522.Google Scholar
• Chen X, Bennett PN, Collins-Thompson K, Horvitz E (2013) Pairwise ranking aggregation in a crowdsourced setting. Proc. 6th ACM Internat. Conf. on Web Search and Data Mining, 193–202.Google Scholar
• Chen X, Gopi S, Mao J, Schneider J (2018a) Optimal instance adaptive algorithm for the top-k ranking problem. IEEE Trans. Inform. Theory 64(9):6139–6160.Crossref, Google Scholar
• Chen Y, Suh C (2015) Spectral MLE: Top-k rank aggregation from pairwise comparisons. Internat. Conf. on Machine Learn., 371–380.Google Scholar
• Chen Y, Fan J, Ma C, Wang K (2019) Spectral method and regularized MLE are both optimal for top-k ranking. Ann. Statist. 47(4):2204.Crossref, Google Scholar
• Chernoff H (1954) On the distribution of the likelihood ratio. Ann. Math. Statist. 25(3):573–578.Crossref, Google Scholar
• Chernozhukov V, Chetverikov D, Kato K (2013) Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors. Ann. Statist. 41(6):2786–2819.Crossref, Google Scholar
• Copeland AH (1951) A reasonable social welfare function. Technical report, University of Michigan, Ann Arbor, MI.Google Scholar
• Cremonesi P, Koren Y, Turrin R (2010) Performance of recommender algorithms on top-n recommendation tasks. Proc. 4th ACM Conf. on Recommender Systems, 39–46.Google Scholar
• Ding J, Han D, Dezert J, Yang Y (2018) A new hierarchical ranking aggregation method. Inform. Sci. 453:168–185.Crossref, Google Scholar
• Duchi JC, Mackey LW, Jordan MI (2010) On the Consistency of Ranking Algorithms (ICML).Google Scholar
• Dwork C, Kumar R, Naor M, Sivakumar D (2001) Rank aggregation methods for the web. Proc. 10th Internat. Conf. on World Wide Web, 613–622.Google Scholar
• Eisenach C, Bunea F, Ning Y, Dinicu C (2020) High-dimensional inference for cluster-based graphical models. J. Machine Learn. Res. 21(53).Google Scholar
• Farnoud F, Touri B, Milenkovic O (2012) Novel distance measures for vote aggregation. Preprint, submitted March 28, https://arxiv.org/abs/1203.6371.Google Scholar
• Filiberto Y, Bello R, Nowe A (2018) A new method for personnel selection based on ranking aggregation using a reinforcement learning approach. Comput. Systems 22(2):537–546.Google Scholar
• Ford Jr LR (1957) Solution of a ranking problem from binary comparisons. Amer. Math. Monthly 64(8P2):28–33.Crossref, Google Scholar
• Gao C, Shen Y, Zhang AY (2021) Uncertainty quantification in the Bradley-Terry-Luce model. Preprint, submitted October 8, https://arxiv.org/abs/2110.03874.Google Scholar
• Ge Y, Dudoit S, Speed TP (2003) Resampling-based multiple testing for microarray data analysis. TEST. 12(1):1–77.Crossref, Google Scholar
• Geyik SC, Ambler S, Kenthapadi K (2019) Fairness-aware ranking in search & recommendation systems with application to LinkedIn talent search. Proc. 25th ACM SIGKDD Internat. Conf. on Knowledge Discovery & Data Mining, 2221–2231.Google Scholar
• Gleich DF Lim Lh (2011) Rank aggregation via nuclear norm minimization. Proc. 17th ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining, 60–68.Google Scholar
• Goldberg K, Roeder T, Gupta D, Perkins C (2001) Eigentaste: A constant time collaborative filtering algorithm. Inform. Retrieval 4(2):133–151.Crossref, Google Scholar
• Gourieroux C, Holly A, Monfort A (1982) Likelihood ratio test, Wald test, and Kuhn-Tucker test in linear models with inequality constraints on the regression parameters. Econometrica 50(1):63–80.Crossref, Google Scholar
• Guiver J, Snelson E (2009) Bayesian inference for Plackett-Luce ranking models. Proc. 26th Annual Internat. Conf. on Machine Learn., 377–384.Google Scholar
• Guo J, Fan Y, Pang L, Yang L, Ai Q, Zamani H, Wu C, et al. (2020) A deep look into neural ranking models for information retrieval. Inform. Processing Management 57(6):102067.Crossref, Google Scholar
• Hajek B, Oh S, Xu J (2014) Minimax-optimal inference from partial rankings. Adv. Neural Inform. Processing Systems 1475–1483.Google Scholar
• Hall P, Miller H (2009) Using the bootstrap to quantify the authority of an empirical ranking. Ann. Statist. 37(6B):3929–3959.Google Scholar
• Harper FM, Konstan JA (2015) The movielens datasets: History and context. ACM Trans. Interactive Intelligent Systems 5(4):1–19.Crossref, Google Scholar
• He X, He Z, Du X, Chua TS (2018) Adversarial personalized ranking for recommendation. Proc. 41st Internat. ACM SIGIR Conf. on Res. & Development in Inform. Retrieval, 355–364.Google Scholar
• Heckel R, Shah NB, Ramchandran K, Wainwright MJ (2019) Active ranking from pairwise comparisons and when parametric assumptions do not help. Ann. Statist. 47(6):3099–3126.Crossref, Google Scholar
• Holm S (1979) A simple sequentially rejective multiple test procedure. Scand. J. Statist. 6(2):65–70.Google Scholar
• Hunter DR (2004) MM algorithms for generalized Bradley-Terry models. Ann. Statist. 32(1):384–406.Crossref, Google Scholar
• Jain L, Gilbert A, Varma U (2020) Spectral methods for ranking with scarce data. Proc. Conf. on Uncertainty in Artificial Intelligence, 609–618.Google Scholar
• Jamieson KG, Nowak RD (2011) Active ranking using pairwise comparisons. Preprint, submitted September 16, https://arxiv.org/abs/1109.3701.Google Scholar
• Jang M, Kim S, Suh C (2018) Top-k rank aggregation from m-wise comparisons. IEEE J. Sel. Top. Signal Process. 12(5):989–1004.Crossref, Google Scholar
• Jang M, Kim S, Suh C, Oh S (2016) Top-k ranking from pairwise comparisons: When spectral ranking is optimal. Preprint, submitted March 14, https://arxiv.org/abs/1603.04153.Google Scholar
• Jang M, Kim S, Suh C, Oh S (2017) Optimal sample complexity of M-wise data for top-K ranking. Proc. 31st Internat. Conf. on Neural Inform. Processing Systems, 1685–1695.Google Scholar
• Javanmard A, Montanari A (2014a) Confidence intervals and hypothesis testing for high-dimensional regression. J. Machine Learn. Res. 15(1):2869–2909.Google Scholar
• Javanmard A, Montanari A (2014b) Hypothesis testing in high-dimensional regression under the Gaussian random design model: Asymptotic theory. IEEE Trans. Inform. Theory 60(10):6522–6554.Crossref, Google Scholar
• Jiang X, Lim LH, Yao Y, Ye Y (2011) Statistical ranking and combinatorial Hodge theory. Math. Programming 127(1):203–244.Crossref, Google Scholar
• Jin T, Xu P, Gu Q, Farnoud F (2020) Rank aggregation via heterogeneous Thurstone preference models. Proc. AAAI Conf. on Artificial Intelligence.Google Scholar
• Keener JP (1993) The Perron–Frobenius theorem and the ranking of football teams. SIAM Rev. 35(1):80–93.Crossref, Google Scholar
• Kendall MG (1955) Further contributions to the theory of paired comparisons. Biometrics 11(1):43–62.Crossref, Google Scholar
• Kendall MG, Smith BB (1940) On the method of paired comparisons. Biometrika 31(3–4):324–345.Crossref, Google Scholar
• Kim M, Farnoud F, Milenkovic O (2015) Hydra: Gene prioritization via hybrid distance-score rank aggregation. Bioinformatics 31(7):1034–1043.Crossref, Google Scholar
• Kim Y, Kim W, Shim K (2017) Latent ranking analysis using pairwise comparisons in crowdsourcing platforms. Inform. Systems 65:7–21.Crossref, Google Scholar
• Kodde DA, Palm FC (1986) Wald criteria for jointly testing equality and inequality restrictions. Econometrica 54(5):1243–1248.Crossref, Google Scholar
• Kolde R, Laur S, Adler P, Vilo J (2012) Robust rank aggregation for gene list integration and meta-analysis. Bioinformatics 28(4):573–580.Crossref, Google Scholar
• Li MM, Liu X, Huang Y, Shi C (2018) Integrating empirical estimation and assortment personalization for e-commerce: A consider-then-choose model. Preprint, submitted September 10, https://dx.doi.org/10.2139/ssrn.3247323.Google Scholar
• Liang S, de Alfaro L (2020) Online top-k selection in crowdsourcing environments. Proc. 6th Internat. Conf. on Comput. and Data Engrg., 252–259.Google Scholar
• Lu T, Boutilier C (2011) Learning Mallows Models with Pairwise Preferences (ICML).Google Scholar
• Lu Y, Negahban SN (2015) Individualized rank aggregation using nuclear norm regularization. Proc. 53rd Annual Allerton Conf. on Comm., Control, and Comput. (IEEE, New York), 1473–1479.Google Scholar
• Luce RD (1959) Individual Choice Behavior. A Theoretical Analysis (Wiley, New York).Google Scholar
• Mallows CL (1957) Nonnull ranking models. Biometrika 44(1–2):114–130.Crossref, Google Scholar
• Maystre L, Grossglauser M (2015) Fast and accurate inference of Plackett–Luce models. Cortes C, Lawrence N, Lee D, Sugiyama M, Garnett R, eds. Adv. Neural Inform. Processing Systems 28:172–180.Google Scholar
• McFadden D (1974) Conditional logit analysis of qualitative choice behavior. Zarembka P, ed. Frontiers in Econometrics (Academic Press, New York), 105–142.Google Scholar
• Minka T, Cleven R, Zaykov Y (2018) Trueskill 2: An improved Bayesian skill rating system. Technical report MSR-TR-2018-8, Microsoft, Redmond, WA.Google Scholar
• Minka T, Graepel T, Herbrich R (2007) TrueskillTM: A Bayesian skill rating system. Adv. Neural Inform. Processing Systems. 19:569–576.Google Scholar
• Mohammadi M, Rezaei J (2020) Ensemble ranking: Aggregation of rankings produced by different multicriteria decision-making methods. Omega 96:102254.Crossref, Google Scholar
• Molenberghs G, Verbeke G (2007) Likelihood ratio, score, and Wald tests in a constrained parameter space. Amer. Statist. 61(1):22–27.Crossref, Google Scholar
• Mosteller F (2006) Remarks on the method of paired comparisons: I. the least squares solution assuming equal standard deviations and equal correlations. Selected Papers of Frederick Mosteller (Springer, Berlin), 157–162.Crossref, Google Scholar
• Nápoles G, Falcon R, Dikopoulou Z, Papageorgiou E, Bello R, Vanhoof K (2017) Weighted aggregation of partial rankings using ant colony optimization. Neurocomput. 250:109–120.Crossref, Google Scholar
• Negahban S, Oh S, Shah D (2017) Rank centrality: Ranking from pairwise comparisons. Oper. Res. 65(1):266–287.Link, Google Scholar
• Negahban S, Oh S, Thekumparampil KK, Xu J (2018) Learning from comparisons and choices. J. Machine Learn. Res. 19(1):1478–1572.Google Scholar
• Negahban S, Wainwright MJ (2012) Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. J. Machine Learn. Res. 13:1665–1697.Google Scholar
• Neudorfer A, Rosset S (2018) Predicting the NCAA basketball tournament using isotonic least squares pairwise comparison model. J. Quant. Anal. Sports 14(4):173–183.Crossref, Google Scholar
• Ning Y, Liu H (2017) A general theory of hypothesis tests and confidence regions for sparse high dimensional models. Ann. Statist. 45(1):158–195.Crossref, Google Scholar
• Orbán-Mihálykó É, Mihálykó C, Koltay L (2019) A generalization of the Thurstone method for multiple choice and incomplete paired comparisons. Central Eur. J. Oper. Res. 27(1):133–159.Crossref, Google Scholar
• Osting B, Brune C, Osher S (2013) Enhanced statistical rankings via targeted data collection. Internat. Conf. on Machine Learn., 489–497.Google Scholar
• Pananjady A, Mao C, Muthukumar V, Wainwright MJ, Courtade TA (2017) Worst-case vs average-case design for estimation from fixed pairwise comparisons. Preprint, submitted July 19, https://arxiv.org/abs/1707.06217.Google Scholar
• Pelechrinis K, Papalexakis E, Faloutsos C (2016) SportsNetRank: Network-based sports team ranking. Large Scale Sports Analytics (SIGKDD).Google Scholar
• Pujahari A, Sisodia DS (2020) Aggregation of preference relations to enhance the ranking quality of collaborative filtering based group recommender system. Expert Systems Appl. 156:113476.Crossref, Google Scholar
• Rajkumar A, Agarwal S (2014) A statistical convergence perspective of algorithms for rank aggregation from pairwise data. Proc. Internat. Conf. on Machine Learn., 118–126.Google Scholar
• Rajkumar A, Agarwal S (2016) When can we rank well from comparisons of o (n\log (n)) nonactively chosen pairs? Conf. on Learning Theory, 1376–1401.Google Scholar
• Richardson M, Prakash A, Brill E (2006) Beyond PageRank: Machine learning for static ranking. Proc. 15th Internat. Conf. on World Wide Web, 707–715.Google Scholar
• Rogers AJ (1986) Modified lagrange multiplier tests for problems with one-sided alternatives. J. Econometrics 31(3):341–361.Crossref, Google Scholar
• Saaty TL (2003) Decision-making with the AHP: Why is the principal eigenvector necessary. Eur. J. Oper. Res. 145(1):85–91.Crossref, Google Scholar
• Shah N, Balakrishnan S, Bradley J, Parekh A, Ramchandran K, Wainwright M (2015) Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence. Artificial Intelligence and Statistics (PMLR), 856–865.Google Scholar
• Shah N, Balakrishnan S, Guntuboyina A, Wainwright M (2016) Stochastically transitive models for pairwise comparisons: Statistical and computational issues. Internat. Conf. on Machine Learning, 11–20 (PMLR).Google Scholar
• Shah NB, Wainwright MJ (2017) Simple, robust and optimal ranking from pairwise comparisons. J. Machine Learn. Res. 18(1):7246–7283.Google Scholar
• Shapiro A (1988) Toward a unified theory of inequality constrained testing in multivariate analysis. Internat. Statist. Rev. 56(1):49–62.Crossref, Google Scholar
• Šidák Z (1967) Rectangular confidence regions for the means of multivariate normal distributions. J. Amer. Statist. Assoc. 62(318):626–633.Google Scholar
• Subochev A, Aleskerov F, Pislyakov V (2018) Ranking journals using social choice theory methods: A novel approach in bibliometrics. J. Informetrics 12(2):416–429.Crossref, Google Scholar
• Suh C, Tan VY, Zhao R (2017) Adversarial top-k ranking. IEEE Trans. Inform. Theory 63(4):2201–2225.Crossref, Google Scholar
• Susko E (2013) Likelihood ratio tests with boundary constraints using data-dependent degrees of freedom. Biometrika 100(4):1019–1023.Crossref, Google Scholar
• Swain TD, Chandler J, Backman V, Marcelino L (2017) Consensus thermotolerance ranking for 110 symbiodinium phylotypes: An exemplar utilization of a novel iterative partial-rank aggregation tool with broad application potential. Functional Ecology 31(1):172–183.Crossref, Google Scholar
• Talluri KT, Van Ryzin GJ (2006) The Theory and Practice of Revenue Management, vol. 68 (Springer Science & Business Media, New York).Google Scholar
• Thurstone LL (1927) A law of comparative judgment. Psych. Rev. 34(4):273.Crossref, Google Scholar
• Tsybakov AB (2008) Introduction to Nonparametric Estimation (Springer Science & Business Media, New York).Google Scholar
• Van de Geer S, Bühlmann P, Ritov Y, Dezeure R (2014) On asymptotically optimal confidence regions and tests for high-dimensional models. Ann. Statist. 42(3):1166–1202.Crossref, Google Scholar
• Verdú S (1994) Generalizing the Fano inequality. IEEE Trans. Inform. Theory 40(4):1247–1251.Crossref, Google Scholar
• Vigna S (2016) Spectral ranking. Network Sci. 4(4):433–445.Crossref, Google Scholar
• Vojnovic M, Yun SY (2017) Parameter estimation for Thurstone choice models. Preprint, submitted April 29, https://arxiv.org/abs/1705.00136.Google Scholar
• Volkovs MN, Zemel RS (2012) A flexible generative model for preference aggregation. Proc. 21st Internat. Conf. on World Wide Web, 479–488.Google Scholar
• Wang J, Shah N, Ravi R (2020) Stretching the effectiveness of MLE from accuracy to bias for pairwise comparisons. Proc. Internat. Conf. on Artificial Intelligence and Statist., 66–76 (PMLR).Google Scholar
• Westfall PH, Young SS (1993) Resampling-Based Multiple Testing: Examples and Methods for p-Value Adjustment, vol. 279 (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Wolak FA (1989) Testing inequality constraints in linear econometric models. J. Econometrics 41(2):205–235.Crossref, Google Scholar
• Xia V, Jain K, Krishna A, Brinton CG (2018) A network-driven methodology for sports ranking and prediction. Proc. 52nd Annual Conf. on Inform. Sci. and Systems (IEEE, New York), 1–6.Google Scholar
• Yu M, Gupta V, Kolar M (2019) Constrained high dimensional statistical inference. Preprint, submitted November 17, https://arxiv.org/abs/1911.07319.Google Scholar
• Zhang CH, Zhang SS (2014) Confidence intervals for low dimensional parameters in high dimensional linear models. J. Royal Statist. Soc. Ser. B Statist. Methodology 76(1):217–242.Crossref, Google Scholar
• Zhang L (2020) Ranking based on triple comparison. PhD thesis, Master’s thesis, Texas A&M University, College Station, Texas.Google Scholar