Método Schulze

El método Schulze es un sistema electoral desarrollado en 1997 por Markus Schulze que selecciona a un único ganador mediante votos que expresan preferencias. El método también se puede utilizar para crear una lista ordenada de ganadores. El método de Schulze también se conoce como caída secuencial de Schwartz (SSD), caída secuencial de Schwartz a prueba de clones (CSSD), el método de ruta de ritmo, ganador de ruta de ritmo, votación de ruta y ganador de ruta.

El método de Schulze es un método de Condorcet, lo que significa que si hay un candidato que es preferido por mayoría sobre cualquier otro candidato en comparaciones por pares, entonces este candidato será el ganador cuando se aplique el método de Schulze.

El resultado del método de Schulze (definido a continuación) da una ordenación de los candidatos. Por lo tanto, si hay varios puestos disponibles, el método se puede utilizar para este fin sin modificaciones, dejando que los k candidatos mejor clasificados ganen los k puestos disponibles. Además, para las elecciones de representación proporcional se ha propuesto una variante de voto único transferible.

El método Schulze es utilizado por varias organizaciones, incluidas Wikimedia, Debian, Ubuntu, Gentoo, los partidos políticos del Partido Pirata y muchas otras.

Descripción del método

Votación

La entrada para el método de Schulze es la misma que para otros sistemas electorales clasificados de un solo ganador: cada votante debe proporcionar una lista de preferencia ordenada sobre los candidatos en los que se permiten empates (un orden débil estricto).

Una forma típica para que los votantes especifiquen sus preferencias en una boleta es la siguiente. Cada boleta enumera a todos los candidatos, y cada votante clasifica esta lista en orden de preferencia usando números: el votante coloca un '1' al lado del candidato(s) más preferido(s), un '2' al lado del segundo favorito, y así sucesivamente.. Cada votante puede opcionalmente:

• dar la misma preferencia a más de un candidato. Esto indica que este votante es indiferente entre estos candidatos.
• Usar números no consecutivos para expresar preferencias. Esto no tiene impacto en el resultado de las elecciones, ya que solo importa el orden en que los votantes clasifican a los candidatos, y no los números absolutos de las preferencias.
• mantener a los candidatos sin clasificar. Cuando un votante no clasifica a todos los candidatos, esto se interpreta como si este votante (i) prefiere estrictamente todos los candidatos clasificados a todos los no clasificados, y (ii) es indiferente entre todos los candidatos no clasificados.

Cálculo

Sea el número de votantes que prefieren candidato a candidato .

Una ruta de candidato a candidato es una secuencia de candidatos con las siguientes propiedades:

1. y .
2. d[C(i+1),C(i)]}">para todos

En otras palabras, en una comparación por pares, cada candidato en el camino vencerá al siguiente candidato.

La fuerza de un camino de candidato a candidato es el menor número de votantes en la secuencia de comparaciones:para todos

Para un par de candidatos y que están conectados por al menos un camino, la fuerza del camino más fuerte es la fuerza máxima de los caminos que los conectan. Si no hay ningún camino de candidato a candidato , entonces .

El candidato es mejor que el candidato si y solo si p[E,D]">.

El candidato es un ganador potencial si y sólo si para todos los demás candidatos .

Se puede probar que p[Y,X]">y p[Z,Y]">juntos implican p[Z,X]">. Por lo tanto, se garantiza (1) que la definición anterior de " mejor " realmente define una relación transitiva y (2) que siempre hay al menos un candidato para cada otro candidato .

Ejemplo

En el siguiente ejemplo, 45 votantes clasifican a 5 candidatos.

Las preferencias por pares deben calcularse primero. Por ejemplo, al comparar A y B por pares, hay 5+5+3+7=20 votantes que prefieren A a B y 8+2+7+8=25 votantes que prefieren B a A. Así y . El conjunto completo de preferencias por pares es:

		20	26	30	22
	25		dieciséis	33	18
	19	29		17	24
	15	12	28		14
	23	27	21	31

Las celdas para d[X, Y] tienen un fondo verde claro si d[X, Y] > d[Y, X]; de lo contrario, el fondo es rojo claro. No hay un ganador indiscutible al observar solo las diferencias por pares aquí.

Ahora hay que identificar los caminos más fuertes. Para ayudar a visualizar las rutas más fuertes, el conjunto de preferencias por pares se representa en el diagrama de la derecha en forma de gráfico dirigido. Una flecha desde el nodo que representa a un candidato X hasta el que representa a un candidato Y se etiqueta con d[X, Y]. Para evitar abarrotar el diagrama, solo se ha dibujado una flecha de X a Y cuando d[X, Y] > d[Y, X] (es decir, las celdas de la tabla con fondo verde claro), omitiendo la que está en la dirección opuesta (la celdas de la tabla con fondo rojo claro).

Un ejemplo de cómo calcular la fuerza de la ruta más fuerte es p[B, D] = 33: la ruta más fuerte de B a D es la ruta directa (B, D) que tiene una fuerza de 33. Pero al calcular p[A, C], la El camino más fuerte de A a C no es el camino directo (A, C) de fuerza 26, más bien el camino más fuerte es el camino indirecto (A, D, C) que tiene fuerza min(30, 28) = 28. La fuerza de un camino es la fuerza de su eslabón más débil.

Para cada par de candidatos X e Y, la siguiente tabla muestra el camino más fuerte del candidato X al candidato Y en rojo, con el enlace más débil subrayado.

ParaDesde	UN	B	C	D	mi
UN	N / A	A-(30)-D- (28) -C-(29)-B	A-(30)-D- (28) -C	A- (30) -D	A-(30)-D-(28)-C- (24) -E	UN
B	B- (25) -A	N / A	B-(33)-D- (28) -C	B- (33) -D	B-(33)-D-(28)-C- (24) -E	B
C	C-(29)-B- (25) -A	C- (29) -B	N / A	C- (29) -B-(33)-D	C- (24) -E	C
D	D-(28)-C-(29)-B- (25) -A	D- (28) -C-(29)-B	D- (28) -C	N / A	D-(28)-C- (24) -E	D
mi	E-(31)-D-(28)-C-(29)-B- (25) -A	E-(31)-D- (28) -C-(29)-B	E-(31)-D- (28) -C	E- (31) -D	N / A	mi
	UN	B	C	D	mi	DesdePara

		28	28	30	24
	25		28	33	24
	25	29		29	24
	25	28	28		24
	25	28	28	31

Ahora se puede determinar la salida del método de Schulze. Por ejemplo, al comparar A y B, ya p[B,A] (= 25)">que, para el método de Schulze el candidato A es mejor que el candidato B. Otro ejemplo es que p[D,E] (= 24)">, entonces el candidato E es mejor que el candidato D. Continuando así, el resultado es que el ranking de Schulze es A > C > B > D">, y E gana. En otras palabras, E gana ya que para todos los demás candidatos X.

Implementación

El único paso difícil para implementar el método de Schulze es calcular las fortalezas de la ruta más fuerte. Sin embargo, este es un problema bien conocido en la teoría de grafos, a veces llamado el problema del camino más ancho. Por lo tanto, una forma sencilla de calcular las fuerzas es una variante del algoritmo de Floyd-Warshall. El siguiente pseudocódigo ilustra el algoritmo.

# Entrada: d[i,j], el número de votantes que prefieren al candidato i al candidato j.
# Salida: p[i,j], la fuerza del camino más fuerte del candidato i al candidato j.

para i de 1 a C
    para j de 1 a C
        si yo ≠ j entonces
            si d[i,j] > d[j,i] entonces
                p[i,j]:= d[i,j]
            demás
                p[i, j]:= 0

para i de 1 a C
    para j de 1 a C
        si yo ≠ j entonces
            para k de 1 a C
                si i ≠ k y j ≠ k entonces
                    p[j,k]:= max (p[j,k], min (p[j,i], p[i,k]))

Este algoritmo es eficiente y tiene un tiempo de ejecución O(C) donde C es el número de candidatos.

Lazos e implementaciones alternativas

Al permitir que los usuarios tengan vínculos en sus preferencias, el resultado del método de Schulze depende naturalmente de cómo se interpreten estos vínculos al definir d[*,*]. Dos elecciones naturales son que d[A, B] representa el número de votantes que prefieren estrictamente A a B (A>B), o el margen de (votantes con A>B) menos (votantes con B>A). Pero no importa cómo se definan los d s, el ranking de Schulze no tiene ciclos, y suponiendo que los d s sean únicos, no tiene vínculos.

Aunque los empates en el ranking de Schulze son poco probables, son posibles. El artículo original de Schulze proponía romper los empates de acuerdo con un votante seleccionado al azar e iterar según fuera necesario.

Una forma alternativa de describir al ganador del método Schulze es el siguiente procedimiento:

1. dibujar un gráfico dirigido completo con todos los candidatos y todos los posibles bordes entre los candidatos
2. iterativamente [a] elimine todos los candidatos que no estén en el conjunto de Schwartz (es decir, cualquier candidato x que no pueda alcanzar a todos los demás que alcancen x) y [b] elimine el borde del gráfico con el valor más pequeño (si es por márgenes, el margen más pequeño; si es por votos, menos votos).
3. el ganador es el último candidato no eliminado.

Hay otra forma alternativa de demostrar el ganador del método Schulze. Este método es equivalente a los otros descritos aquí, pero la presentación está optimizada para que la importancia de los pasos sea visualmente evidente cuando un humano los recorre, no para el cálculo.

1. Haga la tabla de resultados, llamada "matriz de preferencias por pares", como la que se usó anteriormente en el ejemplo. Si usa márgenes en lugar de totales de votos sin procesar, réstelos de su trasposición. Luego, cada número positivo es una victoria por pares para el candidato en esa fila (y marcado en verde), los empates son ceros y las pérdidas son negativas (marcadas en rojo). Ordena a los candidatos por el tiempo que duran en la eliminación.
2. Si hay un candidato sin rojo en su línea, gana.
3. De lo contrario, dibuje un cuadro cuadrado alrededor del conjunto de Schwartz en la esquina superior izquierda. Se puede describir como el "círculo de ganadores" mínimo de candidatos que no pierden ante nadie fuera del círculo. Tenga en cuenta que a la derecha del cuadro no hay rojo, lo que significa que es un círculo de ganadores, y tenga en cuenta que dentro del cuadro no es posible reordenar lo que produciría un círculo de ganadores más pequeño.
4. Corta cada parte de la mesa fuera de la caja.
5. Si todavía no hay un candidato sin rojo en su línea, se debe comprometer algo; todo candidato perdió alguna carrera, y la derrota que mejor toleramos es aquella en la que el perdedor obtuvo más votos. Entonces, tome la celda roja con el número más alto (si va por los márgenes, el menos negativo), póngala en verde, o en cualquier otro color que no sea rojo, y regrese al paso 2.

Aquí hay una tabla de márgenes hecha a partir del ejemplo anterior. Tenga en cuenta el cambio de orden utilizado con fines de demostración.

	mi	UN	C	B	D
mi		1	-3	9	17
UN	-1		7	-5	15
C	3	-7		13	-11
B	-9	5	-13		21
D	-17	-15	11	-21

La primera caída (la derrota de A ante E por 1 voto) no ayuda a reducir el conjunto de Schwartz.

	mi	UN	C	B	D
mi		1	-3	9	17
UN	-1		7	-5	15
C	3	-7		13	-11
B	-9	5	-13		21
D	-17	-15	11	-21

Entonces llegamos directamente a la segunda caída (la pérdida de E ante C por 3 votos), y eso nos muestra al ganador, E, con su fila clara.

	mi	UN	C	B	D
mi		1	-3	9	17
UN	-1		7	-5	15
C	3	-7		13	-11
B	-9	5	-13		21
D	-17	-15	11	-21

Este método también se puede usar para calcular un resultado, si la tabla se rehace de tal manera que uno pueda reorganizar de manera conveniente y confiable el orden de los candidatos tanto en la fila como en la columna, con el mismo orden utilizado en ambos en todo momento..

Criterios satisfechos y fallidos

Criterios satisfechos

El método de Schulze satisface los siguientes criterios:

• Dominio sin restricciones
• No imposición (también conocida como soberanía ciudadana)
• no dictadura
• criterio de Pareto
• Criterio de monotonicidad
• criterio mayoritario
• Criterio de mayoría perdedora
• criterio de Condorcet
• Criterio de perdedor de Condorcet
• criterio de Schwartz
• criterio de smith
• Independencia de las alternativas dominadas por Smith
• Criterio de mayoría mutua
• Independencia de los clones
• simetría inversa
• Mono-añadir
• Mono-añadir-regordete
• Criterio de resolubilidad
• Tiempo de ejecución polinomial
• prudencia
• Conjuntos MinMax
• Criterio de pluralidad de Woodall si se utilizan votos ganadores para d[X,Y]
• Terminación simétrica si se utilizan márgenes para d[X,Y]

Criterios fallidos

Dado que el método de Schulze satisface el criterio de Condorcet, falla automáticamente los siguientes criterios:

• Participación
• Consistencia
• Invulnerabilidad al compromiso
• Invulnerabilidad al entierro
• Más tarde sin daño

Asimismo, dado que el método de Schulze no es una dictadura y está de acuerdo con los votos unánimes, el Teorema de Arrow implica que no cumple el criterio.

• Independencia de alternativas irrelevantes

El método Schulze también falla

• Criterio de Peyton Young Independencia Local de Alternativas Irrelevantes.

Tabla de comparación

La siguiente tabla compara el método de Schulze 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í

La principal diferencia entre el método de Schulze y el método de pares clasificados se puede ver en este ejemplo:

Suponga que la puntuación MinMax de un conjunto X de candidatos es la fuerza de la victoria por pares más fuerte de un candidato A ∉ X contra un candidato B ∈ X. Luego, el método de Schulze, pero no los pares clasificados, garantiza que el ganador sea siempre un candidato del conjunto con un puntaje MinMax mínimo. Entonces, en cierto sentido, el método de Schulze minimiza la mayoría más grande que debe invertirse al determinar el ganador.

Por otro lado, los pares clasificados minimizan la mayoría más grande que debe invertirse para determinar el orden de llegada, en el sentido minlexmax. En otras palabras, cuando los pares clasificados y el método de Schulze producen diferentes órdenes de llegada, para las mayorías en las que los dos órdenes de llegada no están de acuerdo, el orden de Schulze invierte una mayoría mayor que el orden de los pares clasificados.

Historia

El método Schulze fue desarrollado por Markus Schulze en 1997. Se discutió por primera vez en listas de correo públicas en 1997-1998 y en 2000. Posteriormente, los usuarios del método Schulze incluyeron Debian (2003), Gentoo (2005), Topcoder (2005), Wikimedia (2008), KDE (2008), el Partido Pirata de Suecia (2009) y el Partido Pirata de Alemania (2010). En la Wikipedia en francés, el método de Schulze fue uno de los dos métodos de múltiples candidatos aprobados por mayoría en 2005, y se ha utilizado varias veces. El recién formado capítulo de Boise, Idaho de los Socialistas Democráticos de América eligió este método en febrero para su primera elección especial celebrada en marzo de 2018.

En 2011, Schulze publicó el método en la revista académica Social Choice and Welfare.

Usuarios

La ciudad de Silla utiliza el método Schulze para todos los referéndums. Lo utiliza el Instituto de Ingenieros Eléctricos y Electrónicos, la Asociación de Maquinaria Informática y USENIX mediante el uso de la herramienta de decisión HotCRP. El método Schulze es utilizado por las ciudades de Turín y San Donà di Piave y por el distrito londinense de Southwark mediante el uso de la plataforma WeGovNow, que a su vez utiliza la herramienta de decisión LiquidFeedback. Las organizaciones que actualmente utilizan el método Schulze incluyen:

• AEGEE - Foro Europeo de Estudiantes
• Asociación Annodex
• Berufsverband der Kinder- und Jugendärzte [ de ] (BVKJ)
• BoardGameGeek
• Fundación de fundición de nubes
• Club der Ehemaligen der Deutschen SchülerAkademien e. v
• Puntos destacados del condado
• Dapr
• Debian
• Gobierno estudiantil asociado en la École normale supérieure de Paris
• EuroBill Tracker
• Comunidad Europea de Educación Democrática (EUDEC)
• MPEG
• Movimiento Cinco Estrellas de Campobasso, Fondi, Monte Compatri, Montemurlo, Pescara y San Cesareo
• Sociedad Flamenca de Estudiantes de Ingeniería de Lovaina
• friki gratis
• Fundación de Hardware Libre de Italia
• Fundación Gentoo
• Protección de privacidad de GNU (GnuPG)
• Organización de Estudiantes de Posgrado en la Universidad Estatal de Nueva York: Ciencias de la Computación (GSOCS)
• Haskell
• Casa Hillegass Parker
• Cerveza casera
• Corporación de Internet para la Asignación de Nombres y Números (ICANN)
• Club de Scrabble del Valle de Kanawha
• KDE eV
• Salón Kingman
• Fundación Caballero
• Kubernetes
• Kumoricon
• Liga de Administradores Profesionales de Sistemas (LOPSA)
• LíquidoRetroalimentación
• madisonio
• Metallab
• Estudiantes asociados de las escuelas Minerva en KGI
• Televisión musical (MTV)
• Neo
• puente de ruido
• Gobierno Estudiantil Asociado en la Universidad Northwestern
• AbiertoEmbedded
• Intercambio de red neuronal abierta
• pila abierta
• Abrir interruptor
• Fiesta Pirata Australia
• Partido Pirata de Austria
• Partido Pirata de Bélgica
• Partido Pirata de Brasil
• Partido Pirata de Alemania
• Partido Pirata de Islandia
• Partido Pirata de Italia
• Partido Pirata de los Países Bajos
• Partido Pirata de Suecia
• Partido Pirata de Suiza
• Partido Pirata de los Estados Unidos
• RLLMUK
• Chirrido
• Estudiantes por la Cultura Libre
• Laboratorios de azúcar
• Unión Sostenible
• Sverok
• Codificador superior
• ubuntu
• Gobierno Estudiantil Asociado en la Universidad de Friburgo
• Gobierno Estudiantil Asociado en el Departamento de Ciencias de la Computación de la Universidad de Kaiserslautern
• Premios Vidya Gaem
• voltios europa
• Wikipedia en francés, hebreo, húngaro, ruso y persa.