Computationally-efficient methods for reaching consensus

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.

Author dc:creator

• Rico Pachón, Noelia

Advisor dc:contributor.advisor

• Díaz Rodríguez, Susana Irene

• Algoritmos eficientes
• Teoría de la elección social
• Método Kemeny

Statement dc:rights

• Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Licence dc:rights.uri

• http://creativecommons.org/licenses/by-nc-nd/4.0/

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/10651/68527

OAI identifier oai:identifier

oai:digibuo.uniovi.es:10651/68527