Extension of the Concept of Utopia for Rank Aggregation Problem Without Ties
Abstract
The use of rankings and how to aggregate or summarize them has received increasing attention in various fields: bibliometrics, web search, data mining, statistics, educational quality, and computational biology. For the Optimal Bucket Order Problem, the concept of Utopian Matrix was recently introduced: an ideal and not necessarily feasible solution with an unsurpassed quality for the feasible solutions of the problem. This work proposes an extension of the notion of Utopian Matrix to the Rank Aggregation Problem in which ties are not allowed between elements in the output ranking. Beyond the extension that is direct, the work focuses on studying its usefulness as an idealization or super optimal solution. As the Rank Aggregation Problem can be solved exactly based on its definition as an Integer Linear Programming Problem, an experimental study is presented where it is analyzed the relationship that exists between utopian (and anti utopian) values and the optimal solution in several instances solved by using the open source software SCIP. Among the 47 instances analyzed, in 19 the Utopian Value turned out to be equal to the optimal value (40.43 % feasibility) and in 18 the Anti Utopian Value also turned out to be feasible (38.00 %). This experimental study demonstrates the usefulness of utopian and anti utopian values to be considered as extreme values in the Rank Aggregation Problem, thus being able to find higher and lower bounds for optimization very quickly.
References
H. Ramírez-Murillo; C. A. Torres-Pinzón; E. F. Forero-García, “Photovoltaic Potential Estimation by Means of Data Mining in Four Colombian Cities,” TecnoLógicas, vol. 22, no. 46, pp. 65–85, Sep. 2019. https://doi.org/10.22430/22565337.1345
F. Ganga-Contreras; J. López-Nunez; W. Sáez, “Portal de ranking de universidades iberoamericanas: una propuesta para facilitar procesos decisionales,” Rev. Ibérica Sist. e Tecnol. Informação, no. E25, pp. 472–488, Jan. 2020. https://search.proquest.com/docview/2350120514/fulltextPDF/5AB1DDD5F6D34FFDPQ/1
C. Dwork; R. Kumar; M. Naor; D. Sivakumar, “Rank Aggregation Methods for the Web,” in Proceedings of the 10th International Conference on World Wide Web, New York, 2001, pp. 613–622. https://doi.org/10.1145/371920.372165
L. J. Pérez Lugo, “Método para la agregación de rankings a partir de dos grupos con intereses contrapuestos,” (Tesis Doctorado), Facultad de Matemática, Física y Computación. Departamento de Ciencias de la Computación, Universidad Central “Marta Abreu” de Las Villas, 2015. https://dspace.uclv.edu.cu/handle/123456789/7315
D. Sculley, “Rank Aggregation for Similar Items,” in Proceedings of the Seventh SIAM International Conference on Data Mining, April 2007, Minneapolis, Minnesota, USA, 2007, pp. 587–592. https://doi.org/10.1137/1.9781611972771.66
S. Chaudhuri; G. Das; V. Hristidis; G. Weikum, “Probabilistic Ranking of Database Query Results,” in Proceedings of the Thirtieth International Conference on Very Large Data Bases, VLDB 2004, Toronto, Canada 2004, pp. 888–899. https://doi.org/10.1016/B978-012088469-8.50078-4
G. Dahl; H. Minken, “A note on permutations and rank aggregation,” Math. Comput. Model., vol. 52, no. 1–2, pp. 380–385, Jul. 2010. https://doi.org/10.1016/j.mcm.2010.02.052
H. L. Turner; J. van Etten; D. Firth; I. Kosmidis, “Modelling rankings in R: the PlackettLuce package,” Comput. Stat., vol. 35, no. 3, pp. 1027–1057, Feb. 2020. https://doi.org/10.1007/s00180-020-00959-3
V. Pihur; S. Datta; S. Datta, “RankAggreg, an R package for weighted rank aggregation,” BMC Bioinform., vol. 10, no. 62, Feb. 2009. https://doi.org/10.1186/1471-2105-10-62
A. Ali; M. Meila, “Experiments with Kemeny ranking: What works when?,” Math. Soc. Sci., vol. 64, no. 1, pp. 28–40, Jul. 2012. https://doi.org/10.1016/j.mathsocsci.2011.08.008
A. Rosete, “Reformulación eficiente del problema de programación lineal de agregación de rankings.,” Ing. Ind., vol. 39, no. 3, Dic. 2018. http://scielo.sld.cu/scielo.php?script=sci_arttext&pid=S1815-59362018000300250
J. Feng; Q. Fang; W. Ng, “Discovering bucket orders from full rankings,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver 2008, pp. 55–66. https://doi.org/10.1145/1376616.1376625
A. Gionis; H. Mannila; K. Puolamäki; A. Ukkonen, “Algorithms for discovering bucket orders from data,” in Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, PA, USA, August, 2006, pp. 561–566. https://doi.org/10.1145/1150402.1150468
J. A. Aledo; J. A. Gámez; A. Rosete, “Utopia in the solution of the Bucket Order Problem,” Decis. Support Syst., vol. 97, pp. 69–80, May. 2017. https://doi.org/10.1016/j.dss.2017.03.006
J. A. Aledo; J. A. Gámez; A. Rosete, “Approaching rank aggregation problems by using evolution strategies: the case of the optimal bucket order problem,” Eur. J. Oper. Res., vol. 270, no. 3, pp. 982–998, Nov. 2018. https://doi.org/10.1016/j.ejor.2018.04.031
J. A. Aledo; J. A. Gámez; D. Molina, “Approaching the rank aggregation problem by local search-based metaheuristics,” J. Comput. Appl. Math., vol. 354, pp. 445–456, Jul. 2019. https://doi.org/10.1016/j.cam.2018.03.014
C. Dwork; R. Kumar; M. Naor; D. Sivakumar, “Rank aggregation revisited.” Manuscript, 2001. http://web.cse.msu.edu/~cse960/Papers/games/rank.pdf
J. A. Aledo; J. A. Gámez; D. Molina; A. Rosete, “Consensus-based journal rankings: A complementary tool for bibliometric evaluation,” J. Assoc. Inf. Sci. Technol., vol. 69, no. 7, pp. 936–948, 2018. https://doi.org/10.1002/asi.24040
J. A. Aledo; J. A. Gámez; D. Molina, “Tackling the rank aggregation problem with evolutionary algorithms,” Appl. Math. Comput., vol. 222, pp. 632–644, Oct. 2013. https://doi.org/10.1016/j.amc.2013.07.081
D. Molina García, “Contribuciones al problema de agregación de rankings. Aplicaciones al aprendizaje automático.,” (Tesis Doctorales), Departamento de Matemáticas, Universidad de Castilla-La Mancha, 2015. https://ruidera.uclm.es/xmlui/handle/10578/7191
E. M. García Nové, “Nuevos problemas de agregación de rankings: Modelos y algoritmos,” (Tesis Doctorales), Departamento de Estadística, Matemáticas e Informática, Universidad Miguel Hernández de Elche, 2018. http://dspace.umh.es/bitstream/11000/4816/1/TD%20Garc%C3%ADa%20Nov%C3%A9%2C%20Eva%20Mar%C3%ADa%20.pdf
W. D. Cook; M. Kress; L. M. Seiford, “An axiomatic approach to distance on partial orderings,” RAIRO-Operations Res., vol. 20, no. 2, pp. 115–122, 1986. http://www.numdam.org/item/?id=RO_1986__20_2_115_0
T. Achterberg, “SCIP: solving constraint integer programs,” Math. Program. Comput., vol. 1, no. 1, pp. 1–41, 2009. https://doi.org/10.1007/s12532-008-0001-1
Z. I. Berlin, “SCIP: solving constraint integer programs,” 2017. https://www.scipopt.org/
N. Mattei; T. Walsh, “PrefLib: A Library for Preferences www.preflib.org,” in Algorithmic Decision Theory - Third International Conference, ADT 2013, Bruxelles, 2013, vol. 8176, pp. 259–270. https://doi.org/10.1007/978-3-642-41575-3_20
R. Reyna-Hernández, “Herramientas y ficheros para replicar y analizar los experimentos.” 2021. https://drive.google.com/drive/folders/18WoyFQaipbpblZs4P7yo_YOZ1m6L5r53?usp=sharing
Downloads
Altmetric
