×

A differential evolution algorithm for finding the median ranking under the Kemeny axiomatic approach. (English) Zbl 1391.90650

Summary: In recent years, the analysis of preference rankings has become an increasingly important topic. One of the most important tasks in dealing with preference rankings is the identification of the median ranking, namely the ranking that best represents the preferences of a population of judges. This task is known under several alternative names, such as rank aggregation problem, consensus ranking problem, social choice problem. In this paper, we propose a differential evolution algorithm for the consensus ranking detection (DECoR) within the Kemeny’s axiomatic framework. The algorithm works with full, partial and incomplete rankings. A simulation study shows that our proposal is particularly feasible when working with a very large number of objects to be ranked, because it is accurate and also faster than other proposals. Some applications on real data sets show the practical utility of our proposal in helping the users in taking decisions.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
91B10 Group preferences
91B14 Social choice
90C90 Applications of mathematical programming

Software:

AS 136; PrefLib; ConsRank
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aledo, J. A.; Gámez, J. A.; Molina, D., Tackling the rank aggregation problem with evolutionary algorithms, Appl. Math. Comput., 222, 632-644, (2013) · Zbl 1346.68151
[2] Aledo, J. A.; Gámez, J. A.; Rosete, A., Partial evaluation in rank aggregation problems, Comput. Oper. Res, (2016)
[3] Ali, A.; Meila, M., Experiments with kemeny ranking: what works when?, Math. Social Sci., 64, 1, 28-40, (2012) · Zbl 1247.91041
[4] Allende, S.; Bouza, C.; Li, M., Optimal consensus ranking using sls: an approach and an application, Investigación Operacional, 34, 1, 58-75, (2013) · Zbl 1314.90091
[5] Amodio, S.; D’Ambrosio, A.; Siciliano, R., Accurate algorithms for identifying the Median ranking when dealing with weak and partial rankings under the kemeny axiomatic approach, Eur. J.Oper. Res., 249, 2, 667-676, (2016) · Zbl 1346.91065
[6] Arrow, K. J., Social choice and individual values, 12, (1951), Oxford, England. Wiley · Zbl 0984.91513
[7] Beck, M. P.; Lin, B. W., Some heuristics for the consensus ranking problem, Comput. Oper. Res., 10, 1, 1-7, (1983)
[8] Biernacki, C.; Jacques, J., A generative model for rank data based on insertion sort algorithm, Comput. Stat. Data Anal., 58, 162-176, (2013) · Zbl 1365.62167
[9] de Borda, J. C., Mémoire sur LES élections au scrutin, (1781), Histoire de l’Academie Royale des Sciences
[10] Borg, I.; Groenen, P. J., Modern multidimensional scaling: theory and applications, (2005), Springer Science & Business Media · Zbl 1085.62079
[11] Brusco, M. J.; Stahl, S., Branch-and-bound applications in combinatorial data analysis, (2006), Springer Science & Business Media
[12] Busse, L. M.; Orbanz, P.; Buhmann, J. M., Cluster analysis of heterogeneous rank data, Proceedings of the 24th International Conference on Machine learning, 113-120, (2007), ACM
[13] Cheng, W.; Hühn, J.; Hüllermeier, E., Decision tree and instance-based learning for label ranking, Proceedings of the 26th Annual International Conference on Machine Learning, 161-168, (2009), ACM
[14] Cohen, W. W.; Schapire, R. E.; Singer, Y., Learning to order things, Adv. Neural Inf. Process. Sys., 10, 451, (1998)
[15] de Condorcet, M., 1785. Essai sur l’application de l’analyse a la probabilite des decisions rendues a la pluralite des voix (Essay on the application of analysis to the probability of majority Decisions).
[16] Cook, W. D.; Golany, B.; Penn, M.; Raviv, T., Creating a consensus ranking of proposals from reviewers’ partial ordinal rankings, Comput. Oper. Res., 34, 4, 954-965, (2007) · Zbl 1102.90073
[17] Cook, W. D.; Kress, M.; Seiford, L. M., An axiomatic approach to distance on partial orderings, Revue française d’automatique, d’informatique et de recherche opérationnelle. Recherche opérationnelle, 20, 2, 115-122, (1986) · Zbl 0607.90003
[18] Cook, W. D.; Saipe, A., Committee approach to priority planning: the Median ranking method, Cahiers du Centre d’Études de Recherche Opérationnelle, 18, 3, 337-351, (1976) · Zbl 0348.90088
[19] D’Ambrosio, A., Amodio, S., 2015. ConsRank: Compute the Median Ranking(s) According to the Kemeny’s Axiomatic Approach. R package version 1.0.2.
[20] D’Ambrosio, A.; Amodio, S.; Iorio, C., Two algorithms for finding optimal solutions of the kemeny rank aggregation problem for full rankings, Electron. J. Appl. Stat. Anal., 8, 2, 198-213, (2015)
[21] D’Ambrosio, A.; Heiser, W. J., A recursive partitioning method for the prediction of preference rankings based upon kemeny distances, Psychometrika, 81, 3, 774-794, (2016) · Zbl 1345.62144
[22] Davendra, D.; Onwubolu, G., Enhanced differential evolution hybrid scatter search for discrete optimization, Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, 1156-1162, (2007), IEEE
[23] Davenport, A.; Kalagnanam, J., A computational study of the kemeny rule for preference aggregation, AAAI, 4, 697-702, (2004)
[24] De Jong, K.; Fogel, D. B.; Schwefel, H.-P., A history of evolutionary computation, Handb. Evol. Comput. A, 2, 1-12, (1997)
[25] Dwork, C.; Kumar, R.; Naor, M.; Sivakumar, D., Rank aggregation methods for the web, Proceedings of the 10th International Conference on World Wide Web, 613-622, (2001), ACM
[26] Emond, E.; Mason, D., A new technique for high level decision support, Technical Report DOR (CAM) Project Report 2000/13, (2000), Department of National Defence, Canada
[27] Emond, E.; Mason, D., A new rank correlation coefficient with application to the consensus ranking problem, J. Multi-Criteria Decis. Anal., 11, 1, 17-28, (2002) · Zbl 1038.62052
[28] Fligner, M. A.; Verducci, J. S., Multistage ranking models, J. Am. Stat.l Assoc., 83, 403, 892-901, (1988) · Zbl 0719.62036
[29] Fligner, M. A.; Verducci, J. S., Probability models and statistical analyses for ranking data, 80, (1993), Springer · Zbl 0754.00011
[30] Garcıa-Lapresta, J. L.; Pérez-Román, D., Consensus measures generated by weighted kemeny distances on weak orders, Procceedings of the 10th International Conference on Intelligent Systems Design and Applications, Cairo, (2010)
[31] Gionis, A.; Mannila, H.; Puolamäki, K.; Ukkonen, A., Algorithms for discovering bucket orders from data, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, 561-566, (2006), ACM
[32] Goldberg, D. E.; Holland, J. H., Genetic algorithms and machine learning, Mach.Learn., 3, 2, 95-99, (1988)
[33] Good, I., The number of orderings of n candidates when ties are permitted, Fibonacci Q., 13, 11-18, (1975) · Zbl 0299.05009
[34] Hartigan, J. A.; Wong, M. A., Algorithm as 136: a k-means clustering algorithm, J. R. Stat. Soc. Ser.(Appl. Stat.), 28, 1, 100-108, (1979) · Zbl 0447.62062
[35] Hastie, T.; Tibshirani, R.; Friedman, J., The elements of statistical learning theory, (2009), Springer New York
[36] Heiser, W.; D’Ambrosio, A., Clustering and prediction of rankings within a kemeny distance framework, (Lausen, B.; Van den Poel, D.; Ultsch, A., Algorithms from and for Nature and Life, (2013)), 19-31
[37] Heiser, W. J., Geometric representation of association between categories, Psychometrika, 69, 4, 513-545, (2004) · Zbl 1306.62425
[38] Holland, J. H., Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence., (1975), U Michigan Press · Zbl 0317.68006
[39] Jacques, J.; Biernacki, C., Model-based clustering for multivariate partial ranking data, J. Stat. Plann. Inference, 149, 201-217, (2014) · Zbl 1285.62069
[40] Kamishima, T., Nantonac collaborative filtering: recommendation based on order responses, Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 583-588, (2003), ACM
[41] Kemeny, J., Mathematics without numbers, 88, (1959), Daedalus
[42] Kemeny, J.; Snell, J., Preference rankings: an axiomatic approach, (Kemeny, J.; Snell, J., Mathematical Models in the Social Sciences, (1962), New York: Blaisdell), 9-23
[43] Kendall, M. G., A new measure of rank correlation, Biometrika, 30, 1/2, 81-93, (1938) · Zbl 0019.13001
[44] Kirkpatrick, S.; Vecchi, M. P., Optimization by simmulated annealing, Science, 220, 4598, 671-680, (1983) · Zbl 1225.90162
[45] Lorena, L. H.; Lorena, A. C.; Lorena, L. A.; De Leon Carvalho, A. C., Clustering search applied to rank aggregation, Intelligent Systems (BRACIS), 2014 Brazilian Conference on, 198-203, (2014), IEEE
[46] Mallows, C. L., Non-null ranking models. i, Biometrika, 44, 1/2, 114-130, (1957) · Zbl 0087.34001
[47] Marden, J. I., Analyzing and modeling rank data, (1996), CRC Press
[48] Mattei, N.; Walsh, T., Preflib: a library of preference data, Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT 2013), (2013), Springer
[49] Meila, M.; Arora, R., Consensus ranking with signed permutations, J. Mach. Learn. Res., 31, 117-125, (2013)
[50] Meila, M.; Phadnis, K.; Patterson, A.; Bilmes, J., Consensus ranking under the exponential models, Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence, 285-294, (2007), UAI
[51] Mezura-Montes, E.; Velázquez-Reyes, J.; Coello Coello, C. A., A comparative study of differential evolution variants for global optimization, Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, 485-492, (2006), ACM
[52] Murphy, T. B.; Martin, D., Mixtures of distance-based models for ranking data, Comput. Stat.Data Analysis, 41, 3, 645-655, (2003) · Zbl 1429.62258
[53] Nápoles, G.; Dikopoulou, Z.; Papageorgiou, E.; Bello, R.; Vanhoof, K., Aggregation of partial rankings-an approach based on the kemeny ranking problem, International Work-Conference on Artificial Neural Networks, 343-355, (2015), Springer
[54] O’Leary Morgan, K.; Morgon, S., State rankings 2010: A statistical view of America; crime state ranking 2010: crime across America; health care state rankings 2010: health care across America, (2010), CQ Press
[55] Onwubolu, G.; Davendra, D., Differential evolution: a handbook for global permutation-based combinatorial optimization, 175, (2009), Springer Science & Business Media · Zbl 1156.90004
[56] Price, K. V., New ideas in optimization, An Introduction to Differential Evolution, 79-108, (1999), McGraw-Hill Ltd., UK Maidenhead, UK, England, chapter
[57] Storn, R.; Price, K., Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces, 3, (1995), ICSI Berkeley
[58] Thompson, G., Generalized permutation polytopes and exploratory graphical methods for ranked data, Ann. Stat., 1401-1430, (1993) · Zbl 0810.62004
[59] Ukkonen, A.; Puolamäki, K.; Gionis, A.; Mannila, H., A randomized approximation algorithm for computing bucket orders, Inf. Process. Lett., 109, 7, 356-359, (2009) · Zbl 1191.68874
[60] Wang, Y.-M.; Yang, J.-B.; Xu, D.-L., A preference aggregation method through the estimation of utility intervals, Comput. Oper. Res., 32, 8, 2027-2049, (2005) · Zbl 1068.90075
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.