Computationally-efficient methods for reaching consensus

Resumen

Los sistemas de votación se remontan a la antigüedad y son un elemento clave de la vida cotidiana en las sociedades actuales. Durante los últimos siglos se han propuesto muchas metodologías para llegar a decisiones colectivas. En esta tesis nos centramos en la parte del campo de teoría de la elección social que estudia como resolver la situación cuando un conjunto de votantes expresa sus preferencias en forma de rankings sobre un conjunto de alternativas. Kemeny propuso ya en 1959 un método para resolver este asunto, el cual goza de gran reputación a nivel teórico pero que es eficiente desde el punto de vista computacional. En consecuencia, su uso en muchos contextos reales no es posible. El problema del método de Kemeny es que, propone como ganador el ranking sobre el conjunto de alternativas que minimice la distancia a las preferencias dadas por los votantes (definida por el recuento del desacuerdo en el orden de las alternativas), cuyo computo es factorial sobre el número de alternativas. Esto hace que el cálculo sea imposible en términos de tiempo de ejecución cuando el número de alternativas aumenta. El punto de partida de esta tesis es el desarrollo de algoritmos eficientes para el problema de Kemeny. Los algoritmos desarrollados son algoritmos Branch and Bound, que estudian las restricciones teóricas que permiten reducir la exploración de las posibles soluciones, minimizando consecuentemente el tiempo de ejecución requerido por el ordenador para encontrar la solución y haciendo factible su computación para casos que no pueden ser resueltos con algoritmos de fuerza bruta. A continuación, tras investigar sobre las restricciones teóricas que se pueden incluir en los algoritmos, se estudia también como diseñar algoritmos que incorporen estas restricciones de forma eficiente para reducir el tiempo de ejecución requerido en la práctica para encontrar la solución del problema. Durante la evaluación del rendimiento de los algoritmos propuestos, se observó una variación en los tiempos de ejecución incluso para contextos de votación que se suponía tenían las mismas propiedades. Por esta razón, dentro de esta tesis se han definido también índices para medir diferentes características de las preferencias y estudiar su comportamiento en relación con el tiempo de ejecución, con el objetivo de identificar los factores que inciden en la variación del tiempo de ejecución. Además, utilizando estos índices se ha entrenado un modelo de aprendizaje automático que pretende predecir el tiempo de ejecución necesario para encontrar el ranking de Kemeny dadas las preferencias de los votantes, basándose en los tiempos de ejecución previamente obtenidos. Para concluir, se exploran diferentes aplicaciones de la agregación de rankings. Estas aplicaciones se presentan de dos formas diferentes. Por un lado, se estudia su incorporación de las metodologías de agregación de rankings en algoritmos de aprendizaje automático, tanto de clasificación como de clustering. Por otro lado, se introduce la agregación de rankings como mecanismo en un problema de toma de decisiones, con el objetivo de agregar las variables consideradas importantes por diferentes modelos de clasificación, para llegar a un consenso de los factores que impactan en la predicción independientemente del algoritmo utilizado para la construcción del modelo. Esta tesis se presenta como un compendio de publicaciones. Los principales resultados de la investigación se han publicado en artículos de revistas y conferencias entre los años 2019 y 2022. El compendio incluye cuatro artículos de revista publicados en la lista Journal Citation Report (JCR). Además, los artículos de conferencia publicados en el desarrollo de esta investigación se añaden también en el informe con el fin de mostrar los resultados alcanzados.