A New Binary Programming Formulation and Social Choice Property for Kemeny Rank Aggregation

References

• Ahlgren P, Jarneving B, Rousseau R (2003) Requirements for a cocitation similarity measure, with special reference to Pearson’s correlation coefficient. J. Assoc. Inform. Sci. Tech. 54(6):550–560.Crossref, 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. Assoc. Comput. Machinery 55(5):23.Crossref, Google Scholar
• Amodio S, D’Ambrosio A, Siciliano R (2016) Accurate algorithms for identifying the median ranking when dealing with weak and partial rankings under the Kemeny axiomatic approach. European J. Oper. Res. 249(2):667–676.Crossref, Google Scholar
• Arrow KJ (1951) Social Choice and Individual Values (Wiley, New York).Google Scholar
• Asfaw D, Vitelli V, Sørensen Ø, Arjas E, Frigessi A (2017) Time-varying rankings with the Bayesian mallows model. Stat 6(1):14–30.Crossref, Google Scholar
• Bartholdi J, Tovey CA, Trick MA (1989) Voting schemes for which it can be difficult to tell who won the election. Soc. Choice Welfare 6:157–165.Crossref, Google Scholar
• Betzler N, Bredereck R, Niedermeier R (2014) Theoretical and empirical evaluation of data reduction for exact Kemeny rank aggregation. Autonomous Agents Multi-Agent Systems 28(5):721–748.Crossref, Google Scholar
• Brancotte B, Yang B, Blin G, Cohen-Boulakia S, Denise A, Hamel S (2015) Rank aggregation with ties: Experiments and analysis. Proc. VLDB Endowment 8(11):1202–1213.Crossref, Google Scholar
• Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD (2016) Handbook of Computational Social Choice (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Ceberio J, Irurozki E, Mendiburu A, Lozano JA (2015) A review of distances for the Mallows and generalized Mallows estimation of distribution algorithms. Comput. Optim. Appl. 62(2):545–564.Crossref, Google Scholar
• Cohen D, Jeavons P, Jefferson C, Petrie KE, Smith BM (2005) Symmetry definitions for constraint satisfaction problems. Van Beek P, ed. Internat. Conf. Principles Practice Constraint Programming (Springer, Berlin), 17–31.Google Scholar
• Condorcet JAN (1785) Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix (L’Imprimerie Royale, Paris).Google Scholar
• Conitzer V, Davenport A, Kalagnanam J (2006) Improved bounds for computing Kemeny rankings. Cohn A, ed. Proc. 21st National Conf. Artificial Intelligence, vol. 1 (AAAI Press, Palo Alto, CA), 620–626.Google Scholar
• Cook WD (2006) Distance-based and ad hoc consensus models in ordinal preference ranking. Eur. J. Oper. Res. 172(2):369–385.Crossref, Google Scholar
• Cook WD, Kress M (1985) Ordinal ranking with intensity of preference. Management Sci. 31(1):26–32.Link, Google Scholar
• Cook WD, Seiford LM (1978) Priority ranking and consensus formation. Management Sci. 24(16):1721–1732.Link, Google Scholar
• Cook WD, Raviv T, Richardson AJ (2010) Aggregating incomplete lists of journal rankings: An application to academic accounting journals. Accounting Perspect. 9(3):217–235.Crossref, Google Scholar
• Cook WD, Golany B, Penn M, Raviv T (2007) Creating a consensus ranking of proposals from reviewers’ partial ordinal rankings. Comput. Oper. Res. 34(4):954–965.Crossref, Google Scholar
• Crispino M, Arjas E, Vitelli V, Barrett N, Frigessi A (2019) A Bayesian Mallows approach to nontransitive pair comparison data: How human are sounds? Ann. Appl. Statist. 13(1):492–519.Crossref, Google Scholar
• Critchlow DE (2012) Metric Methods for Analyzing Partially Ranked Data (Springer, New York).Google Scholar
• Cushman P, Hoeksema JT, Kouveliotou C, Lowenthal J, Peterson B, Stassun KG, von Hippel T (2015) Impact of declining proposal success rates on scientific productivity. Preprint, submitted October 4, https://arxiv.org/abs/1510.01647.Google Scholar
• D’Ambrosio A, Mazzeo G, Iorio C, Siciliano R (2017) A differential evolution algorithm for finding the median ranking under the Kemeny axiomatic approach. Comput. Oper. Res. 82(C):126–138.Crossref, Google Scholar
• Davenport A, Kalagnanam J (2004) A computational study of the Kemeny rule for preference aggregation. Cohn AG, ed. Proc. 19th National Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 697–702.Google Scholar
• Davidson J, Liebald B, Liu J, Nandy P, Van Vleet T, Gargi U, Gupta S, et al. (2010) The YouTube video recommendation system. Proc. 4th ACM Conf. Recommender Systems (ACM, New York), 293–296.Google Scholar
• de Borda JC (1781) Mémoire sur les élections au scrutin (L’Académie royale des sciences, Paris).Google Scholar
• Desarkar MS, Sarkar S, Mitra P (2016) Preference relations based unsupervised rank aggregation for metasearch. Expert Systems Appl. 49(C):86–98.Crossref, Google Scholar
• Diaconis P (1988) Group Representations in Probability and Statistics (Institute of Mathematical Statistics, Hayward, CA).Google Scholar
• Doignon JP, Fiorini S (2001) Facets of the weak order polytope derived from the induced partition projection. SIAM J. Discrete Math. 15(1):112–121.Crossref, Google Scholar
• Doignon JP, Pekeč A, Regenwetter M (2004) The repeated insertion model for rankings: Missing link between two subset choice models. Psychometrika 69(1):33–54.Crossref, Google Scholar
• Dummett M (1998) The Borda count and agenda manipulation. Soc. Choice Welfare 15(2):289–296.Crossref, Google Scholar
• Dwork C, Kumar R, Naor M, Sivakumar D (2001) Rank aggregation methods for the web. Proc. 10th Internat. Conf. World Wide Web (ACM, New York), 613–622.Google Scholar
• Emond EJ, Mason DW (2002) A new rank correlation coefficient with application to the consensus ranking problem. J. Multi-Criteria Decision Anal. 11(1):17–28.Crossref, Google Scholar
• Endriss U, Obraztsova S, Polukarov M, Rosenschein JS (2016) Strategic voting with incomplete information. Brewka G, ed. Proc. 25th Internat. Joint Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 236–242.Google Scholar
• Escobedo AR, Yasmin R (2021) Derivations of large classes of facet-defining inequalities of the weak order polytope using ranking structures. Preprint, submitted March 25, https://arxiv.org/abs/2008.03799.Google Scholar
• Escobedo AR, Moreno-Centeno E, Yasmin R (2021) An axiomatic distance methodology for aggregating multimodal evaluations. Preprint, submitted January 23, http://www.optimization-online.org/DB_HTML/2021/01/8223.html.Google Scholar
• Fagin R, Kumar R, Sivakumar D (2003) Efficient similarity search and classification via rank aggregation. Proc. 2003 ACM SIGMOD Internat. Conf. Management Data (ACM, New York), 301–312.Google Scholar
• Fagin R, Kumar R, Mahdian M, Sivakumar D, Vee E (2004) Comparing and aggregating rankings with ties. Proc. 23rd ACM SIGMOD-SIGACT-SIGART Sympos. Principles Database Systems (ACM, New York), 47–58.Google Scholar
• Farah M, Vanderpooten D (2007) An outranking approach for rank aggregation in information retrieval. Proc. 30th Annual Internat. ACM SIGIR Conf. Res. Development Inform. Retrieval (ACM, New York), 591–598.Google Scholar
• Favardin P, Lepelley D, Serais J (2002) Borda rule, Copeland method and strategic manipulation. Rev. Econom. Design 7(2):213–228.Crossref, Google Scholar
• Feld SL, Grofman B (1988) The Borda count in n-dimensional issue space. Public Choice 59(2):167–176.Crossref, Google Scholar
• Fields EB, Okudan GE, Ashour OM (2013) Rank aggregation methods comparison: A case for triage prioritization. Expert Systems Appl. 40(4):1305–1311.Crossref, Google Scholar
• Fiorini S, Fishburn PC (2004) Weak order polytopes. Discrete Math. 275(1–3):111–127.Crossref, Google Scholar
• Fishbain B, Moreno-Centeno E (2016) Self calibrated wireless distributed environmental sensory networks. Sci. Rep. 6:24382.Crossref, Google Scholar
• Gao Y, Xu K (2019) pRankAggreg: A fast clustering based partial rank aggregation. Inform. Sci. 478:408–421.Crossref, Google Scholar
• Gass S (1998) Tournaments, transitivity and pairwise comparison matrices. J. Oper. Res. Soc. 49(6):616–624.Crossref, Google Scholar
• Good I (1975) The number of orderings of n candidates when ties are permitted. Fibonacci Quart. 13:11–18.Google Scholar
• Goodin RE, List C (2006) A conditional defense of plurality rule: Generalizing May’s theorem in a restricted informational environment. Amer. J. Political Sci. 50(4):940–949.Crossref, Google Scholar
• Heiser WJ (2004) Geometric representation of association between categories. Psychometrika 69(4):513–545.Crossref, Google Scholar
• Hochbaum DS, Levin A (2006) Methodologies and algorithms for group-rankings decision. Management Sci. 52(9):1394–1408.Link, Google Scholar
• IBM Knowledge Center (2017) CPLEX optimization studio v12.8.0 documentation, https://www.ibm.com/support/pages/cplex-optimization-studio-v128.Google Scholar
• IBM Support (2019) RS03137: CPLEX may ignore time limits on highly symmetric models on which a new incumbent is found close to the time limit, https://www.ibm.com/support/pages/apar/RS03137.Google Scholar
• Irurozki E, Calvo B, Lozano JA (2016) PerMallows: An R package for Mallows and generalized Mallows models. J. Statist. Software 71(12):1–30.Crossref, Google Scholar
• Keisler J (2004) Value of information in portfolio decision analysis. Decision Anal. 1(3):177–189.Link, Google Scholar
• Kemeny JG, Snell LJ (1962) Preference ranking: An axiomatic approach. Mathematical Models in Social Science (Ginn, Boston), 9–23.Google Scholar
• Kemmer R, Yoo Y, Escobedo A, Maciejewski R (2020) Enhancing collective estimates by aggregating cardinal and ordinal inputs. Aroyo L, Simperl E, eds. Proc. 8th AAAI Conf. Human Comput. Crowdsourcing (AAAI Press, Palo Alto, CA), 73–82.Google Scholar
• Kendall MG (1938) A new measure of rank correlation. Biometrika 30(1–2):81–93.Crossref, Google Scholar
• Kendall MG (1945) The treatment of ties in ranking problems. Biometrika 33(3):239–251.Crossref, Google Scholar
• Kendall MG (1948) Rank Correlation Methods (Griffin, London).Google Scholar
• Kenyon-Mathieu C, Schudy W (2007) How to rank with few errors. Proc. 39th Annual ACM Sympos. Theory Comput. (ACM, New York), 95–103.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
• Liberti L (2008) Automatic generation of symmetry-breaking constraints. Yang B, Du D-Z, Wang CA, eds. Internat. Conf. Combin. Optim. Appl. (Springer, Berlin), 328–338.Google Scholar
• Lin S (2010a) Rank aggregation methods. WIREs Comput. Statist. 2(5):555–570.Crossref, Google Scholar
• Lin S (2010b) Space oriented rank-based data integration. Statist. Appl. Genetics Molecular Biol. 9(1):20.Google Scholar
• Lu T, Boutilier C (2014) Effective sampling and learning for Mallows models with pairwise-preference data. J. Machine Learning Res. 15(1):3783–3829.Google Scholar
• Mallows CL (1957) Non-null ranking models. I. Biometrika 44(1–2):114–130.Crossref, Google Scholar
• Mandal M, Mukhopadhyay A (2017) Multiobjective PSO-based rank aggregation: Application in gene ranking from microarray data. Inform. Sci. 385–386:55–75.Crossref, Google Scholar
• Mao A, Procaccia AD, Chen Y (2012) Social choice for human computation. Workshops 26th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 137–142.Google Scholar
• Mao A, Procaccia AD, Chen Y (2013) Better human computation through principled voting. Proc. 27th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 1142–1148.Google Scholar
• Marbach D, Costello JC, Küffner R, Vega NM, Prill RJ, Camacho DM, Allison KR, et al. (2012) Wisdom of crowds for robust gene network inference. Nature Methods 9(8):796–804.Crossref, Google Scholar
• Marden JI (1996) Analyzing and Modeling Rank Data (CRC Press, Boca Raton, FL).Google Scholar
• Martí R, Reinelt G (2011) The Linear Ordering Problem (Springer, Berlin).Crossref, Google Scholar
• Mattei N, Walsh T (2013) PrefLib: A library for preferences. Perny P, Pirlot M, Tsoukiàs A, eds. Internat. Conf. Algorithmic Decision Theory (Springer, Berlin), 259–270.Google Scholar
• Miller GA (1956) The magical number seven, plus or minus two: Some limits on our capacity for processing information. Psych. Rev. 63(2):81–97.Crossref, Google Scholar
• Milosz R, Hamel S (2018) Exploring the median of permutations problem. J. Discrete Algorithms 52–53:92–111.Crossref, Google Scholar
• Moreno-Centeno E, Escobedo AR (2016) Axiomatic aggregation of incomplete rankings. IIE Trans. 48(6):475–488.Crossref, Google Scholar
• Muravyov SV (2014) Dealing with chaotic results of Kemeny ranking determination. Measurement 51:328–334.Crossref, Google Scholar
• Nemhauser GL, Wolsey LA (1988) Integer Programming and Combinatorial Optimization (Wiley, Chichester, UK).Google Scholar
• Newman A, Vempala S (2001) Fences are futile: On relaxations for the linear ordering problem. Aardal K, Gerards B, eds. Internat. Conf. Integer Programming Combin. Optim. (Springer, Berlin), 333–347.Google Scholar
• Schilling MS, Oeser N, Schaub C (2007) How effective are decision analyses? Assessing decision process and group alignment effects. Decision Anal. 4(4):227–242.Link, Google Scholar
• Sherali HD, Smith JC (2001) Improving discrete model representations via symmetry considerations. Management Sci. 47(10):1396–1407.Link, Google Scholar
• Skolfield JK, Yasmin R, Escobedo AR, Huie LM (2020) A comparison of axiomatic distance-based collective intelligence methods for wireless sensor network state estimation in the presence of information injection. 6th World Forum Internet Things (WF-IoT) (IEEE, Piscataway, NJ), 1–6.Google Scholar
• Smith JH (1973) Aggregation of preferences with variable electorate. Econometrica 41(6):1027–1041.Crossref, Google Scholar
• Steyvers M, Miller B, Hemmer P, Lee MD (2009) The wisdom of crowds in the recollection of order information. Bengio Y, Schuurmans D, Lafferty JD, Williams CKI, Culotta A, eds. Proc. 22nd Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 1785–1793.Google Scholar
• Streib N, Young SJ, Sokol J (2012) A Major League Baseball team uses operations research to improve draft preparation. Interfaces 42(2):119–130.Link, Google Scholar
• Truchon M (1998) An extension of the Condorcet criterion and Kemeny orders. Cahier 98-15, Centre de Recherche en Économie et Finance Appliquées, Université Laval, Québec, Canada.Google Scholar
• Wald R, Khoshgoftaar TM, Dittman D, Awada W, Napolitano A (2012) An extensive comparison of feature ranking aggregation techniques in bioinformatics. 13th Internat. Conf. Inform. Reuse Integration (IRI) (IEEE, Piscataway, NJ), 377–384.Google Scholar
• Ye M, Liang C, Yu Y, Wang Z, Leng Q, Xiao C, Chen J, Hu R (2016) Person reidentification via ranking aggregation of similarity pulling and dissimilarity pushing. IEEE Trans. Multimedia 18(12):2553–2566.Crossref, Google Scholar
• Yilmaz E, Aslam JA, Robertson S (2008) A new rank correlation coefficient for information retrieval. Proc. 31st Annual Internat. ACM SIGIR Conf. Res. Development Inform. Retrieval (ACM, New York), 587–594.Google Scholar
• Yoo Y, Escobedo AR, Skolfield JK (2020) A new correlation coefficient for comparing and aggregating non-strict and incomplete rankings. Eur. J. Oper. Res. 285(3):1025–1041.Crossref, Google Scholar
• Young HP, Levenglick A (1978) A consistent extension of Condorcet’s election principle. SIAM J. Appl. Math. 35(2):285–300.Crossref, Google Scholar
• Young P (1995) Optimal voting rules. J. Econom. Perspect. 9(1):51–64.Crossref, Google Scholar