Método Kemeny–Young

El método Kemeny-Young es un sistema electoral que utiliza boletas preferenciales y conteos de comparación 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 para cada secuencia posible, donde cada secuencia considera qué opción podría ser la más popular, qué opción podría ser la segunda más popular, qué opción podría ser la tercera más popular, y así sucesivamente hasta qué opción podría ser la menos popular. popular. La secuencia que tiene la puntuación más alta es la secuencia ganadora y la primera opción en la secuencia ganadora es la opción más popular. (Como se explica a continuación, los empates pueden ocurrir en cualquier nivel de clasificación).

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

Descripción

El método Kemeny-Young utiliza boletas preferenciales en las que los votantes clasifican las 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 no clasificadas generalmente se interpretan como las menos preferidas.

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

Los cálculos de Kemeny-Young generalmente se realizan en dos pasos. El primer paso es crear una matriz o tabla que cuente las preferencias de los votantes por pares. El segundo paso es probar todas las clasificaciones posibles, calcular una puntuación para cada clasificación y comparar las puntuaciones. Cada puntaje de clasificación es igual a la suma de los recuentos por pares que se aplican a esa clasificación.

La clasificación que tiene la puntuación más alta se identifica como la clasificación general. (Si más de una clasificación tiene la misma puntuación más alta, todas estas clasificaciones posibles están empatadas y, por lo general, la clasificación general implica uno o más empates).

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

orden de preferencia	Elección
Primero	eliot
Segundo	roland
Tercera	Meredith o Selden(igual preferencia)

Estas preferencias se pueden expresar en una tabla de conteo. Una tabla de conteo, que organiza todos los conteos por pares en tres columnas, es útil para contar (contar) las preferencias de las boletas y calcular los puntajes de clasificación. La columna central rastrea cuando 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 conteo:

Todos los posibles paresde nombres de elección	Número de votos con preferencia indicada
Preferir X sobre Y	igual preferencia	Preferir Y sobre X
X = SeldenY = Meredith	0	+1 voto	0
X = SeldenY = Elliot	0	0	+1 voto
X = SeldenY = Roldán	0	0	+1 voto
X = MeredithY = Elliot	0	0	+1 voto
X = MeredithY = Rolando	0	0	+1 voto
X = ElliotY = Rolando	+1 voto	0	0

Ahora suponga que múltiples votantes votaron por esos cuatro candidatos. Después de que se hayan contado todas las boletas, se puede usar el mismo tipo de tabla de conteo para resumir todas las preferencias de todos los votantes. Aquí hay un ejemplo para un caso que tiene 100 votantes:

Todos los posibles paresde nombres de elección	Número de votos con preferencia indicada
Preferir X sobre Y	igual preferencia	Preferir Y sobre X
X = SeldenY = Meredith	50	10	40
X = SeldenY = Elliot	40	0	60
X = SeldenY = Roldán	40	0	60
X = MeredithY = Elliot	40	0	60
X = MeredithY = Rolando	30	0	70
X = ElliotY = Rolando	30	0	70

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

Una vez completada la tabla de conteo, cada clasificación posible de opciones se examina por turnos y su puntaje de clasificación se calcula sumando el número apropiado de cada fila de la tabla de conteo. Por ejemplo, la posible clasificación:

1. eliot
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 > Roldán: 30
• Elliot > Meredith: 60
• Elliot > Selden: 60
• roland > meredith: 70
• Roldán > Selden: 60
• Meredith > Selden: 40

dando una puntuación de clasificación total de 30 + 60 + 60 + 70 + 60 + 40 = 320.

Cálculo de la clasificación general

Después de que se hayan calculado los puntajes para cada clasificación posible, se puede identificar la clasificación que tiene la puntuación más alta y se convierte en la clasificación general. En este caso, la clasificación general es:

1. roland
2. eliot
3. Selden
4. Meredith

con un puntaje de clasificación de 370.

Si hay ciclos o empates, más de una clasificación posible puede tener la misma puntuación más alta. Los ciclos se resuelven produciendo una sola clasificación general donde algunas de las opciones están empatadas.

Matriz resumen

Una vez calculada la clasificación general, los recuentos de comparación por pares se pueden organizar en una matriz de resumen, como se muestra a continuación, en la que las opciones aparecen en el orden ganador desde la más popular (arriba y a la izquierda) hasta la menos popular (abajo y a la derecha). Este diseño de matriz no incluye los conteos por pares de igual preferencia que aparecen en la tabla de conteo:

	... sobre roland	... sobre Elliot	... sobre Selden	... sobre Meredith
Prefiero a Roland...	-	70	60	70
Prefiero a Elliot...	30	-	60	60
Prefiero Selden...	40	40	-	50
Prefiero a Meredith...	30	40	40	-

En esta matriz de resumen, el puntaje de clasificación más alto es igual a la suma de los conteos en la mitad triangular superior derecha de la matriz (que se muestra aquí en negrita, con un fondo verde). Ninguna otra clasificación posible puede tener una matriz de resumen que produzca una suma mayor de números en la mitad triangular superior derecha. (Si lo hiciera, esa sería la clasificación general).

En esta matriz de 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 un mínimo. Los artículos académicos de John Kemeny y Peyton Young se refieren a encontrar 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:

Método	ganador del primer lugar
Kemeny-Joven	roland
Condorcet	roland
Votación de segunda vuelta instantánea	Elliot o Selden(dependiendo de cómo se maneje la eliminatoria de segunda vuelta)
Pluralidad	Selden

Ejemplo

• v
• t
• mi

Imagine que Tennessee tiene una elección sobre la ubicación de su capital. La población de Tennessee se concentra en torno a sus cuatro ciudades principales, que están repartidas por todo el estado. Para este ejemplo, suponga que todo el electorado vive en estas cuatro ciudades y que todos quieren vivir lo más cerca posible de la capital.

Los candidatos a la capital son:

• Memphis, la ciudad más grande del estado, con el 42% de los votantes, pero ubicada lejos de las demás ciudades
• Nashville, con el 26% de los votantes, cerca del centro del estado
• Knoxville, con el 17% de los votantes
• Chattanooga, con el 15% de los votantes

Las preferencias de los votantes se dividirían así:

42% de los votantes(cerca de Memphis)	26% de los votantes(cerca de Nashville)	15% de los votantes(cerca de Chattanooga)	17% de los votantes(cerca de Knoxville)
MenfisNashvilleChattanoogaknoxville	NashvilleChattanoogaknoxvilleMenfis	ChattanoogaknoxvilleNashvilleMenfis	knoxvilleChattanoogaNashvilleMenfis

Esta matriz resume los recuentos de comparación por pares correspondientes:

	... sobreMenfis	... sobreNashville	... sobreChattanooga	... sobreKnoxville
PrefieroMenfis...	-	42%	42%	42%
PrefieroNashville...	58%	-	68%	68%
PrefieroChattanooga...	58%	32%	-	83%
PrefieroKnoxville...	58%	32%	17%	-

El método de Kemeny-Young organiza los conteos de comparación por pares en la siguiente tabla de conteo:

Todos los posibles paresde nombres de elección	Número de votos con preferencia indicada
Preferir X sobre Y	igual preferencia	Preferir Y sobre X
X = MenfisY = Nashville	42%	0	58%
X = MenfisY = Chattanooga	42%	0	58%
X = MenfisY = Knoxville	42%	0	58%
X = NashvilleY = Chattanooga	68%	0	32%
X = NashvilleY = Knoxville	68%	0	32%
X = ChattanoogaY = Knoxville	83%	0	17%

El puntaje de clasificación para la posible clasificación de Memphis primero, Nashville segundo, Chattanooga tercero y Knoxville cuarto es igual (el número sin unidades) 345, que es la suma de los siguientes números anotados.42% (de los votantes) prefieren Memphis sobre Nashville42% prefieren Memphis sobre Chattanooga42% prefieren Memphis sobre KnoxvilleEl 68 % prefiere Nashville a Chattanooga68% prefieren Nashville sobre Knoxville83% prefieren Chattanooga sobre Knoxville

Esta tabla enumera todos los puntajes de clasificación:

Primeraopción	Segundaopción	Terceraopción	Cuartaopción	Puntuación de clasificación
Menfis	Nashville	Chattanooga	knoxville	345
Menfis	Nashville	knoxville	Chattanooga	279
Menfis	Chattanooga	Nashville	knoxville	309
Menfis	Chattanooga	knoxville	Nashville	273
Menfis	knoxville	Nashville	Chattanooga	243
Menfis	knoxville	Chattanooga	Nashville	207
Nashville	Menfis	Chattanooga	knoxville	361
Nashville	Menfis	knoxville	Chattanooga	295
Nashville	Chattanooga	Menfis	knoxville	377
Nashville	Chattanooga	knoxville	Menfis	393
Nashville	knoxville	Menfis	Chattanooga	311
Nashville	knoxville	Chattanooga	Menfis	327
Chattanooga	Menfis	Nashville	knoxville	325
Chattanooga	Menfis	knoxville	Nashville	289
Chattanooga	Nashville	Menfis	knoxville	341
Chattanooga	Nashville	knoxville	Menfis	357
Chattanooga	knoxville	Menfis	Nashville	305
Chattanooga	knoxville	Nashville	Menfis	321
knoxville	Menfis	Nashville	Chattanooga	259
knoxville	Menfis	Chattanooga	Nashville	223
knoxville	Nashville	Menfis	Chattanooga	275
knoxville	Nashville	Chattanooga	Menfis	291
knoxville	Chattanooga	Menfis	Nashville	239
knoxville	Chattanooga	Nashville	Menfis	255

El puntaje de clasificación más alto es 393, y este puntaje está asociado con la siguiente clasificación posible, por lo que esta clasificación también es la clasificación general:

orden de preferencia	Elección
Primero	Nashville
Segundo	Chattanooga
Tercera	knoxville
Cuatro	Menfis

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

La siguiente matriz de resumen organiza los conteos por pares en orden desde el más popular (arriba y a la izquierda) hasta el menos popular (abajo y a la derecha):

	... sobre Nashville...	... sobre Chattanooga...	... sobre Knoxville...	... sobre Menfis...
Prefiero Nashville...	-	68%	68%	58%
Prefiero Chattanooga...	32%	-	83%	58%
Prefiero Knoxville...	32%	17%	-	58%
Prefiero Menfis...	42%	42%	42%	-

En este arreglo, el puntaje de clasificación más alto (393) es igual a la suma de los recuentos en negrita, que se encuentran en la mitad triangular superior derecha de la matriz (con un fondo verde).

Características

En todos los casos que no dan como resultado un empate exacto, el método de Kemeny-Young identifica la opción más popular, la segunda opción más popular, y así sucesivamente.

Un empate puede ocurrir en cualquier nivel de preferencia. Excepto en algunos casos en los que hay ambigüedades circulares, el método de Kemeny-Young 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-Young, cumplen estos criterios:no imposiciónHay preferencias de los votantes que pueden generar todos los resultados posibles del orden de preferencia general, incluidos los empates en cualquier combinación de niveles de preferencia.criterio de CondorcetSi hay una opción que gana todos los concursos por parejas, entonces esta opción gana.criterio mayoritarioSi la mayoría de los votantes prefieren estrictamente la opción X a cualquier otra opción, entonces la opción X se identifica como la más popular.no dictaduraUn solo votante no puede controlar el resultado en todos los casos.

Criterios satisfechos adicionales

El método de Kemeny-Young también satisface estos criterios:Dominio sin restriccionesIdentifica el orden general de preferencia para todas las opciones. El método hace esto para todos los posibles conjuntos de preferencias de los votantes y siempre produce el mismo resultado para el mismo conjunto de preferencias de los votantes.Eficiencia de ParetoCualquier preferencia por pares expresada por cada votante da como resultado que la opción preferida se clasifique más arriba que la opción menos preferida.monotonicidadSi 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 en popularidad general.criterio de smithLa opción más popular es un miembro del conjunto de Smith, que es el conjunto de opciones no vacío más pequeño, de modo que todos los miembros del conjunto se prefieren por parejas a todas las opciones que no están en el conjunto de Smith.Independencia de las alternativas dominadas por SmithSi la opción X no está en el conjunto de Smith, agregar o quitar la opción X no cambia el resultado en el que la opción Y se identifica como la más popular.ReforzamientoSi todas las papeletas se dividen en contiendas separadas y la clasificación general para las contiendas separadas es la misma, entonces se produce la misma clasificación cuando se combinan todas las papeletas.simetría inversaSi se invierten las preferencias en cada papeleta, entonces la opción más popular anteriormente no debe seguir siendo la opción más popular.

Criterios fallidos para todos los métodos de Condorcet

Al igual que todos los métodos de Condorcet, el método de Kemeny-Young no cumple estos criterios (lo que significa que los criterios descritos no se aplican al método de Kemeny-Young):Independencia de alternativas irrelevantesAgregar o retirar la opción X no cambia el resultado en el que la opción Y se identifica como la más popular.Invulnerabilidad al entierroUn votante no puede desplazar una opción de la más popular dándole a la opción una clasificación falsamente baja.Invulnerabilidad al compromisoUn votante no puede hacer que una opción se convierta en la más popular dándole a la opción una clasificación falsamente alta.ParticipaciónAgregar boletas que clasifiquen la opción X sobre la opción Y nunca hace que la opción Y, en lugar de la opción X, se vuelva más popular.Más tarde sin dañoClasificar una opción adicional (que de otro modo no estaba clasificada) no puede impedir que una opción sea identificada como la más popular.ConsistenciaSi todas las boletas 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 boletas.

Criterios fallidos adicionales

El método Kemeny-Young tampoco cumple estos criterios (lo que significa que los criterios descritos no se aplican al método Kemeny-Young):Independencia de los clonesOfrecer una mayor cantidad de opciones similares, en lugar de ofrecer solo una de esas opciones, no cambia la probabilidad de que una de estas opciones se identifique como la más popular.Invulnerabilidad al empujeUn votante no puede hacer que la opción X se convierta en la más popular dando a la opción Y una clasificación falsamente alta.SchwartzLa elección identificada como más popular es un miembro del conjunto de Schwartz.Tiempo de ejecución polinomialSe conoce un algoritmo para determinar el ganador utilizando este método en un tiempo de ejecución que es polinomial en el número de opciones.

Métodos de cálculo y complejidad computacional

No se conoce un algoritmo para calcular un polinomio de clasificación en el tiempo de Kemeny-Young en el número de candidatos, y es poco probable que exista ya que el problema es NP-difícil incluso si solo hay 4 votantes.

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

Tenga en cuenta que la complejidad del cálculo escala linealmente con el número de votantes, por lo que el tiempo necesario para procesar un conjunto determinado de votos está dominado por el número de candidatos y no por el número de votos, lo que limita la importancia de esta restricción a las elecciones en las que los votantes pueden para considerar efectivamente mucho más que los siete elementos comunes de la memoria de trabajo.

El método de Kemeny-Young se puede formular como una instancia de un problema más abstracto, de encontrar conjuntos de arcos de retroalimentación ponderados en gráficos de torneos. Como tal, se pueden aplicar muchos métodos para el cálculo de conjuntos de arcos de retroalimentación a este problema, incluida una variante del algoritmo Held-Karp que puede calcular la clasificación de Kemeny-Young de candidatos en el tiempo , significativamente más rápido para muchos candidatos que el tiempo factorial. de probar todas las clasificaciones. Existe un esquema de aproximación de tiempo polinomial para calcular una clasificación de Kemeny-Young, y también existe un algoritmo de tiempo subexponencial parametrizado con tiempo de ejecución O (2) para calcular dicha clasificación.

Historia

El método Kemeny-Young fue desarrollado por John Kemeny en 1959.

En 1978, Peyton Young y Arthur Levenglick demostraron que este método era el único método neutral que satisfacía el refuerzo y una versión del criterio de Condorcet. En otros artículos, Young adoptó un enfoque epistémico de la agregación de preferencias: supuso que había un orden de preferencia objetivamente 'correcto', pero desconocido, sobre las alternativas, y 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-Young 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-Young 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, cada preferencia por pares, pero la puntuación más pequeña identifica la misma clasificación general.

Desde 1991, el método ha sido promovido bajo el nombre de "clasificación de popularidad VoteFair" por Richard Fobes.

Tabla de comparación

La siguiente tabla compara el método Kemeny-Young con otros métodos de elección preferencial de ganador único:

Sistema	monótono	Ganador de Condorcet	Mayoria	perdedor de Condorcet	perdedor de la mayoría	mayoría mutua	Herrero	ISDA	LIIA	Independencia de los clones	simetría inversa	Participación, consistencia	Más tarde sin daños	Más tarde sin ayuda	Tiempo polinomial	Resolubilidad
Schulze	Sí	Sí	Sí	Sí	Sí	Sí	Sí	Sí	No	Sí	Sí	No	No	No	Sí	Sí
parejas clasificadas	Sí	Sí	Sí	Sí	Sí	Sí	Sí	Sí	Sí	Sí	Sí	No	No	No	Sí	Sí
Alternativa de Tideman	No	Sí	Sí	Sí	Sí	Sí	Sí	Sí	No	Sí	No	No	No	No	Sí	Sí
Kemeny-Joven	Sí	Sí	Sí	Sí	Sí	Sí	Sí	Sí	Sí	No	Sí	No	No	No	No	Sí
Copelandia	Sí	Sí	Sí	Sí	Sí	Sí	Sí	Sí	No	No	Sí	No	No	No	Sí	No
Nanson	No	Sí	Sí	Sí	Sí	Sí	Sí	No	No	No	Sí	No	No	No	Sí	Sí
Negro	Sí	Sí	Sí	Sí	Sí	No	No	No	No	No	Sí	No	No	No	Sí	Sí
Votación de segunda vuelta instantánea	No	No	Sí	Sí	Sí	Sí	No	No	No	Sí	No	No	Sí	Sí	Sí	Sí
Smith/IRV	No	Sí	Sí	Sí	Sí	Sí	Sí	Sí	No	Sí	No	No	No	No	Sí	Sí
Borda	Sí	No	No	Sí	Sí	No	No	No	No	No	Sí	Sí	No	Sí	Sí	Sí
balduino	No	Sí	Sí	Sí	Sí	Sí	Sí	No	No	No	No	No	No	No	Sí	Sí
Bucklin	Sí	No	Sí	No	Sí	Sí	No	No	No	No	No	No	No	Sí	Sí	Sí
Pluralidad	Sí	No	Sí	No	No	No	No	No	No	No	No	Sí	Sí	Sí	Sí	Sí
voto contingente	No	No	Sí	Sí	Sí	No	No	No	No	No	No	No	Sí	Sí	Sí	Sí
coombs	No	No	Sí	Sí	Sí	Sí	No	No	No	No	No	No	No	No	Sí	Sí
minimax	Sí	Sí	Sí	No	No	No	No	No	No	No	No	No	No	No	Sí	Sí
Anti-pluralidad	Sí	No	No	No	Sí	No	No	No	No	No	No	Sí	No	No	Sí	Sí
Voto contingente de Sri Lanka	No	No	Sí	No	No	No	No	No	No	No	No	No	Sí	Sí	Sí	Sí
voto suplementario	No	No	Sí	No	No	No	No	No	No	No	No	No	Sí	Sí	Sí	Sí
dodgson	No	Sí	Sí	No	No	No	No	No	No	No	No	No	No	No	No	Sí