Hispanopedia Wiki
Articulo de referencia

Método Kemeny

El método Kemeny es un sistema electoral que utiliza el voto preferencial y comparaciones por pares para identificar las opciones más populares en una elección. Es un método Con...

Hispanopedia WikiContenido en espanolLectura gratuita

El método Kemeny es un sistema electoral que utiliza el voto preferencial y comparaciones por pares para identificar las opciones más populares en una elección. Es un método Condorcet porque, si hay un ganador Condorcet, siempre se clasificará como la opción más popular.

Este método asigna una puntuación a cada secuencia posible, considerando cuál opción podría ser la más popular, la segunda más popular, la tercera más popular, y así sucesivamente hasta llegar a la menos popular. La secuencia con la puntuación más alta es la ganadora, y la primera opción de la secuencia ganadora es la más popular. (Como se explica más adelante, pueden producirse empates en cualquier nivel de clasificación).

El método Kemeny también se conoce como la regla Kemeny-Young , la clasificación de popularidad VoteFair , el método de máxima verosimilitud y la relación mediana .

Descripción

El método Kemeny utiliza papeletas de voto preferencial en las que los votantes clasifican sus opciones según su orden de preferencia. Un votante puede clasificar más de una opción en el mismo nivel de preferencia. Las opciones sin clasificar se interpretan generalmente como las menos preferidas.

Los cálculos de Kemeny generalmente se realizan en dos pasos. El primer paso consiste en crear una matriz o tabla que contabilice las preferencias de los votantes por pares. El segundo paso consiste en probar todas las clasificaciones posibles , calcular una puntuación para cada una de ellas y comparar las puntuaciones. La puntuación de cada clasificación es igual a la suma de los recuentos por pares que corresponden a dicha clasificación.

La clasificación con la puntuación más alta se considera la clasificación general. (Si varias clasificaciones obtienen la misma puntuación máxima, todas quedan empatadas y, por lo general, la clasificación general incluye uno o más empates).

Otra forma de ver el ordenamiento es que es aquel que minimiza la suma de las distancias tau de Kendall ( distancia de ordenamiento de burbuja ) a las listas de votantes.

Para demostrar cómo se convierte un orden de preferencia individual en una tabla de recuento, conviene considerar el siguiente ejemplo. Supongamos que un solo votante tiene que elegir entre cuatro candidatos (es decir, Elliot, Meredith, Roland y Selden) y tiene el siguiente orden de preferencia:

Estas preferencias se pueden expresar en una tabla de recuento. Una tabla de recuento, que organiza todos los recuentos por pares en tres columnas, es útil para contabilizar las preferencias de voto y calcular las puntuaciones de clasificación. La columna central registra cuándo un votante indica más de una opción en el mismo nivel de preferencia. El orden de preferencia anterior se puede expresar como la siguiente tabla de recuento:

Supongamos ahora que varios votantes votaron por esos cuatro candidatos. Una vez contados todos los votos, se puede utilizar el mismo tipo de tabla de recuento para resumir las preferencias de todos los votantes. He aquí un ejemplo para un caso con 100 votantes:

La suma de los recuentos en cada fila debe ser igual al número total de votos.

Una vez completada la tabla de recuento, se examina cada posible orden de opciones y se calcula su puntuación sumando el número correspondiente de cada fila de la tabla. Por ejemplo, la posible clasificación es:

  1. Elliot
  2. Roland
  3. Meredith
  4. Selden

Satisface las preferencias Elliot > Roland, Elliot > Meredith, Elliot > Selden, Roland > Meredith, Roland > Selden y Meredith > Selden. Las puntuaciones respectivas, tomadas de la tabla, son

  • Elliot > Roland: 30
  • Elliot > Meredith: 60
  • Elliot > Selden: 60
  • Roland > Meredith: 70
  • Roland > Selden: 60
  • Meredith > Selden: 40

lo que da una puntuación de clasificación total de 30 + 60 + 60 + 70 + 60 + 40 = 320.

Cálculo de la clasificación general

Una vez calculadas las puntuaciones para cada posible clasificación, se identifica la que obtiene la puntuación más alta, la cual se convierte en la clasificación general. En este caso, la clasificación general es:

  1. Roland
  2. Elliot
  3. Selden
  4. Meredith

con una puntuación de clasificación de 370.

Si existen ciclos o empates, más de una clasificación posible puede tener la misma puntuación máxima. Los ciclos se resuelven generando una única clasificación general donde algunas de las opciones están empatadas.

Matriz resumen

Una vez calculada la clasificación general, los recuentos de comparaciones por pares se pueden organizar en una matriz resumen, como se muestra a continuación, en la que las opciones aparecen en orden de preferencia, desde la más popular (arriba y a la izquierda) hasta la menos popular (abajo y a la derecha). Esta disposición de la matriz no incluye los recuentos de pares de igual preferencia que aparecen en la tabla de recuento: [ 1 ]

En esta matriz resumen, la puntuación de clasificación más alta es igual a la suma de los recuentos en la mitad triangular superior derecha de la matriz (mostrada aquí en negrita, con fondo verde). Ninguna otra clasificación posible puede tener una matriz resumen que produzca una suma mayor de números en la mitad triangular superior derecha. (Si la tuviera, esa sería la clasificación general).

En esta matriz resumen, la suma de los números en la mitad triangular inferior izquierda de la matriz (que se muestra aquí con un fondo rojo) es mínima. Los artículos académicos de John Kemeny y Peyton Young [ 2 ] [ 3 ] se refieren a la búsqueda de esta suma mínima, que se denomina puntuación de Kemeny y que se basa en cuántos votantes se oponen (en lugar de apoyar) a cada orden por pares:

Ejemplo

Supongamos que Tennessee celebra elecciones para elegir la ubicación de su capital . La población está dividida entre cuatro ciudades, y todos los votantes desean que la capital esté lo más cerca posible de ellas . Las opciones son:

Esta matriz resume los recuentos de comparaciones por pares correspondientes :

El método Kemeny organiza los recuentos de comparaciones por pares en la siguiente tabla de recuento:

La puntuación de clasificación para la posible clasificación de Memphis primero, Nashville segundo, Chattanooga tercero y Knoxville cuarto es igual a (el número sin unidades) 345, que es la suma de los siguientes números anotados.

El 42% (de los votantes) prefiere Memphis a Nashville.
El 42% prefiere Memphis a Chattanooga.
El 42% prefiere Memphis a Knoxville.
El 68% prefiere Nashville a Chattanooga.
El 68% prefiere Nashville a Knoxville.
El 83% prefiere Chattanooga a Knoxville.

Esta tabla enumera todas las puntuaciones de clasificación:

La puntuación de clasificación más alta es 393, y esta puntuación está asociada con la siguiente clasificación posible, por lo que esta clasificación también es la clasificación general:

Si se necesita un único ganador, se elige la primera opción, Nashville. (En este ejemplo, Nashville es el ganador de Condorcet ).

La matriz resumen que aparece a continuación ordena los recuentos por pares desde los más populares (arriba y a la izquierda) hasta los menos populares (abajo y a la derecha):

En esta disposición, la puntuación de clasificación más alta (393) es igual a la suma de los recuentos en negrita, que se encuentran en la mitad triangular superior derecha de la matriz (con fondo verde).

Características

En todos los casos que no resultan en un empate exacto, el método Kemeny identifica la opción más popular, la segunda más popular, y así sucesivamente.

Puede producirse un empate en cualquier nivel de preferencia. Salvo en algunos casos donde intervienen ambigüedades circulares , el método de Kemeny solo produce un empate en un nivel de preferencia cuando el número de votantes con una preferencia coincide exactamente con el número de votantes con la preferencia opuesta.

Criterios satisfechos para todos los métodos de Condorcet.

Todos los métodos de Condorcet, incluido el método de Kemeny, cumplen estos criterios:

No imposición
Existen preferencias de los votantes que pueden generar cualquier resultado posible en cuanto al orden general de preferencia, incluidos los empates en cualquier combinación de niveles de preferencia.
criterio de Condorcet
Si existe una opción que gana todas las comparaciones por pares, entonces esa opción gana.
Criterio de mayoría
Si la mayoría de los votantes prefiere estrictamente la opción X a cualquier otra opción, entonces la opción X se identifica como la más popular.
No dictadura
Un solo votante no puede controlar el resultado en todos los casos.

Criterios adicionales satisfechos

El método Kemeny también cumple con estos criterios:

Dominio no restringido
Identifica el orden general de preferencia para todas las opciones. El método realiza esta tarea para todos los conjuntos posibles de preferencias de los votantes y siempre produce el mismo resultado para el mismo conjunto de preferencias.
eficiencia de Pareto
Cualquier preferencia por pares expresada por cada votante da como resultado que la opción preferida se clasifique por encima de la opción menos preferida.
Monotonicidad
Si los votantes aumentan el nivel de preferencia de una opción, el resultado de la clasificación no cambia o la opción promocionada aumenta su popularidad general.
criterio de Smith
La opción más popular es un miembro del conjunto de Smith , que es el conjunto no vacío más pequeño de opciones tal que cada miembro del conjunto es preferido por pares a cualquier opción que no esté en el conjunto de Smith.
Independencia de las alternativas dominadas por Smith
Si la opción X no está en el conjunto de Smith , agregar o quitar la opción X no cambia un resultado en el que la opción Y se identifica como la más popular.
Reforzamiento
Si todas las papeletas se dividen en contiendas separadas y la clasificación general de cada contienda es la misma, entonces se obtiene la misma clasificación al combinar todas las papeletas. [ 4 ]
Simetría de inversión
Si las preferencias en cada papeleta de votación se invierten, entonces la opción que antes era la más popular no tiene por qué seguir siéndolo.

Criterios no cumplidos para todos los métodos de Condorcet.

Al igual que todos los métodos de Condorcet, el método de Kemeny no cumple con estos criterios (lo que significa que los criterios descritos no se aplican al método de Kemeny):

Independencia de alternativas irrelevantes
Agregar o quitar la opción X no cambia un resultado en el que la opción Y se identifica como la más popular.
Invulnerabilidad al entierro
Un votante no puede desplazar una opción de la lista de las más populares asignándole una clasificación falsamente baja.
Invulnerabilidad a comprometer
Un votante no puede lograr que una opción se convierta en la más popular otorgándole una clasificación falsamente alta.
Participación
Agregar votos que clasifiquen la opción X por encima de la opción Y nunca provoca que la opción Y, en lugar de la opción X, se convierta en la más popular.
Más tarde, sin daño
Clasificar una opción adicional (que de otro modo no estaría clasificada) no puede impedir que una opción sea identificada como la más popular.
Consistencia
Si todas las papeletas se dividen en contiendas separadas y la opción X se identifica como la más popular en cada una de esas contiendas, entonces la opción X es la más popular cuando se combinan todas las papeletas.
Criterio favorito sincero
La estrategia de voto óptima para un individuo siempre debería incluir brindar el máximo apoyo a su candidato favorito.

Criterios adicionales no cumplidos

El método Kemeny tampoco cumple con estos criterios (lo que significa que los criterios descritos no se aplican al método Kemeny):

Independencia de los clones
Ofrecer un mayor número de opciones similares, en lugar de ofrecer solo una, no cambia la probabilidad de que una de esas opciones sea identificada como la más popular.
Invulnerabilidad ante el empuje
Un votante no puede lograr que la opción X se convierta en la más popular otorgándole a la opción Y una clasificación falsamente alta.
Schwartz
La opción identificada como la más popular pertenece al conjunto de Schwartz.
Tiempo de ejecución polinomial [ 5 ]
Se conoce un algoritmo que determina al ganador utilizando este método en un tiempo de ejecución polinomial en el número de opciones.

Métodos de cálculo y complejidad computacional

No se conoce un algoritmo para calcular una clasificación de Kemeny en tiempo polinomial en el número de candidatos, y es improbable que exista ya que el problema es NP-difícil [ 5 ] incluso si solo hay 4 votantes (par) [ 6 ] [ 7 ] o 7 votantes (impar). [ 8 ]

Se ha informado [ 9 ] que los métodos de cálculo basados ​​en programación entera a veces permitían calcular clasificaciones completas para votos de hasta 40 candidatos en segundos. Sin embargo, ciertas elecciones de Kemeny de 40 candidatos y 5 votantes generadas aleatoriamente no se pudieron resolver en una  computadora Pentium de 3 GHz en un tiempo útil en 2006. [ 9 ]

El método de Kemeny puede formularse como una instancia de un problema más abstracto, el de encontrar conjuntos de arcos de retroalimentación ponderados en grafos de torneos . [ 10 ] Como tal, muchos métodos para el cálculo de conjuntos de arcos de retroalimentación pueden aplicarse a este problema, incluyendo una variante del algoritmo de Held-Karp que puede calcular la clasificación de Kemeny-Young denorte{\displaystyle n}candidatos a tiempoO(norte2norte){\displaystyle O(n2^{n})}, significativamente más rápido para muchos candidatos que el tiempo factorial de probar todas las clasificaciones. [ 11 ] [ 12 ] Existe un esquema de aproximación de tiempo polinomial para calcular una clasificación de Kemeny, [ 13 ] y también existe un algoritmo parametrizado de tiempo subexponencial con tiempo de ejecución O * (2 O( √ OPT ) ) para calcular dicha clasificación. [ 10 ]

Historia

El método Kemeny fue desarrollado por John Kemeny en 1959. [ 2 ]

En 1978, Peyton Young y Arthur Levenglick caracterizaron axiomáticamente el método, demostrando que es el único método neutral que satisface la consistencia y el llamado criterio cuasi-Condorcet. [ 3 ] También puede caracterizarse utilizando la consistencia y una propiedad de monotonicidad. [ 14 ] En otros trabajos, [ 15 ] [ 16 ] [ 17 ] [ 18 ] Young adoptó un enfoque epistémico para la agregación de preferencias: supuso que existía un orden de preferencia objetivamente "correcto", pero desconocido, sobre las alternativas, y que los votantes reciben señales ruidosas de este verdadero orden de preferencia (cf. el teorema del jurado de Condorcet ). Utilizando un modelo probabilístico simple para estas señales ruidosas, Young demostró que el método de Kemeny era el estimador de máxima verosimilitud del verdadero orden de preferencia. Young argumenta además que el propio Condorcet conocía la regla de Kemeny y su interpretación de máxima verosimilitud, pero no pudo expresar claramente sus ideas.

En los artículos de John Kemeny y Peyton Young, las puntuaciones de Kemeny utilizan recuentos de cuántos votantes se oponen, en lugar de apoyar, a cada preferencia por pares, [ 2 ] [ 3 ] pero la puntuación más pequeña de este tipo identifica la misma clasificación general.

Desde 1991, Richard Fobes ha promovido este método bajo el nombre de "Clasificación de popularidad VoteFair". [ 19 ]

Tabla comparativa

La siguiente tabla compara el método Kemeny con otros métodos de elección de un solo ganador:

Notas

  1. ↑ Los números de este ejemplo están adaptados de Sample election used in Wikipedia Archived 2017-03-30 at the Wayback Machine .
  2. 1 2 3 John Kemeny, "Matemáticas sin números", Daedalus 88 (1959), págs. 577 – 591.
  3. 1 2 3 H. P. Young y A. Levenglick, " Una extensión consistente del principio de elección de Condorcet ", SIAM Journal on Applied Mathematics 35 , n.º 2 (1978), págs. 285–300.
  4. ↑ Giuseppe Munda, "Evaluación social multicriterio para una economía sostenible", pág. 124.
  5. 1 2 J. Bartholdi III, CA Tovey y MA Trick , "Esquemas de votación para los que puede ser difícil decir quién ganó las elecciones", Social Choice and Welfare , vol. 6, n.º 2 (1989), págs. 157-165.
  6. ↑ C. Dwork, R. Kumar, M. Naor, D. Sivakumar. Métodos de agregación de rangos para la web, WWW10, 2001
  7. ↑ Biedl, Therese ; Brandenburg, Franz J.; Deng, Xiaotie (12 de septiembre de 2005). Healy, Patrick; Nikolov, Nikola S. (eds.). Cruces y permutaciones . Notas de clase en informática. Springer Berlin Heidelberg. págs. 1–12 . doi : 10.1007/11618058_1 . ISBN  9783540314257. S2CID 11189107 . 
  8. ↑ Bachmeier, Georg; Brandt, Felix; Geist, Christian; Harrenstein, Paul; Kardel, Keyvan; Peters, Dominik; Seedig, Hans Georg (2019-11-01). "k-Majority digraphs and the hardness of voting with a constant number of voters" . Journal of Computer and System Sciences . 105 : 130– 157. arXiv : 1704.06304 . doi : 10.1016/j.jcss.2019.04.005 . ISSN 0022-0000 . S2CID 2357131 .  
  9. 1 2 Vincent Conitzer, Andrew Davenport y Jayant Kalagnanam, " Límites mejorados para el cálculo de clasificaciones de Kemeny " (2006).
  10. 1 2 Karpinski, M. y Schudy, W., "Algoritmos más rápidos para el torneo de conjuntos de arcos de retroalimentación, la agregación de rangos de Kemeny y el torneo de intermediación" , en: Cheong, O., Chwa, K.-Y. y Park, K. (Eds.): ISAAC 2010, Parte I, LNCS 6506, págs. 3-14.
  11. ↑ Lawler, E. (1964), "Un comentario sobre conjuntos mínimos de arcos de retroalimentación", IEEE Transactions on Circuit Theory , 11 (2): 296– 297, doi : 10.1109/tct.1964.1082291
  12. ↑ Bodlaender, Hans L. ; Fomin, Fedor V.; Koster, Arie MCA; Kratsch, Dieter; Thilikos, Dimitrios M. (2012), "Una nota sobre algoritmos exactos para problemas de ordenación de vértices en grafos", Theory of Computing Systems , 50 (3): 420– 432, doi : 10.1007/s00224-011-9312-0 , hdl : 1956/4556 , MR 2885638 , S2CID 253742611  
  13. ↑ "Cómo realizar clasificaciones con pocos errores". https://cs.brown.edu/~claire/stoc07.pdf
  14. ↑ Can, Burak; Storcken, Ton (2013-03-01). "Actualización de reglas de preferencia monótonas" (PDF) . Ciencias Sociales Matemáticas . 65 (2): 136– 149. doi : 10.1016/j.mathsocsci.2012.10.004 . ISSN 0165-4896 . 
  15. ↑ HP Young, "La teoría del voto de Condorcet", American Political Science Review 82 , n.º 2 (1988), págs. 1231-1244 .
  16. ↑ HP Young, "Clasificación y elección óptimas a partir de comparaciones por pares", en Information pooling and group decision making editado por B. Grofman y G. Owen (1986), JAI Press, pp. 113 – 122.
  17. ↑ HP Young, "Reglas óptimas de votación", Journal of Economic Perspectives 9 , n.º 1 (1995), págs. 51-64 .
  18. ↑ HP Young, "Elección grupal y juicios individuales", Capítulo 9 de Perspectivas sobre la elección pública: un manual , editado por Dennis Mueller (1997) Cambridge UP., pp.181 – 200.
  19. ↑ Richard Fobes, "The Creative Problem Solver's Toolbox", ( ISBN 0-9632-2210-4), 1993, págs. 223 – 225.
  • VoteFair.org  : un sitio web que calcula los resultados de Kemeny. Para fines comparativos, también calcula al ganador según el método de mayoría simple, Condorcet, Borda y otros métodos de votación.
  • VoteFair_Ranking.cpp  — Programa en C++, disponible en GitHub bajo la licencia MIT, que calcula los resultados de la clasificación de VoteFair, que incluyen cálculos de Condorcet-Kemeny.
  • Biblioteca PHP de la clase Condorcet que admite múltiples métodos Condorcet, incluido el método Kemeny.
  • Programa en C++ para la agregación de preferencias de Kemeny-Young  : programa de línea de comandos para el cálculo rápido de los resultados de Kemeny-Young, disponible como código fuente y binarios compilados para Windows y Linux. Código abierto, excepto por el uso de Numerical Recipes .
  • Programa en C para la agregación de preferencias de Kemeny  : implementa el algoritmo de Davenport sin dependencias de otras bibliotecas. Código abierto, bajo licencia LGPL. También existe una interfaz Ruby para la biblioteca, de código abierto y bajo licencia LPGL.
  • Agregación de rango óptimo de Kemeny-Young en Python  : un tutorial que utiliza una formulación simple como programa entero y es adaptable a otros lenguajes con enlaces a lpsolve.
  • QuickVote es un sitio web que calcula los resultados de Kemeny y ofrece explicaciones y ejemplos del concepto. También calcula al ganador según el método de mayoría simple, el recuento de Borda, la segunda vuelta instantánea y otros métodos de votación.