El conjunto de Smith , [nota 1] a veces llamado ciclo superior , generaliza la idea de un ganador de Condorcet a los casos en los que no existe tal ganador . Lo hace permitiendo que los ciclos de candidatos sean tratados conjuntamente, como si fueran un único ganador de Condorcet. [1] Los sistemas de votación que siempre eligen a un candidato del conjunto de Smith pasan el criterio de Smith . El conjunto de Smith y el criterio de Smith reciben ambos su nombre del matemático John H. Smith .
El conjunto de Smith proporciona un criterio de elección óptima para el resultado de una elección. Un criterio alternativo, más estricto, lo proporciona el conjunto de Landau .
El conjunto de Smith se define formalmente como el conjunto más pequeño tal que cada candidato dentro del conjunto S es invencible, de dos en dos, para cada candidato fuera de S.
Alternativamente, puede definirse como el conjunto de todos los candidatos con una trayectoria de derrota (no estricta) hacia cualquier candidato que los derrote.
Un conjunto de candidatos en el que cada uno de sus miembros derrota por pares a todos los candidatos que se encuentran fuera del conjunto se denomina conjunto dominante . Por lo tanto, el conjunto de Smith también se denomina el conjunto dominante más pequeño .
El conjunto de Schwartz es equivalente al conjunto de Smith, excepto que ignora los votos empatados. Formalmente, el conjunto de Schwartz es el conjunto tal que cualquier candidato dentro del conjunto tiene una trayectoria de victoria estricta frente a cualquier candidato que lo derrote.
El conjunto de Smith se puede construir a partir del conjunto de Schwartz agregando repetidamente dos tipos de candidatos hasta que no existan más candidatos fuera del conjunto:
Tenga en cuenta que los candidatos del segundo tipo solo pueden existir después de que se hayan agregado los candidatos del primer tipo.
Teorema: Los conjuntos dominantes están anidados ; es decir, de cualesquiera dos conjuntos dominantes en una elección, uno es un subconjunto del otro.
Demostración: Supongamos, por el contrario, que existen dos conjuntos dominantes, D y E , ninguno de los cuales es un subconjunto del otro. Entonces deben existir candidatos d ∈ D , e ∈ E tales que d ∉ E y e ∉ D . Pero, por hipótesis, d derrota a todo candidato que no esté en D (incluido e ) mientras que e derrota a todo candidato que no esté en E (incluido d ), lo que constituye una contradicción. ∎
Corolario: Se deduce que el conjunto de Smith es el conjunto dominante no vacío más pequeño y que está bien definido.
Teorema: Si D es un conjunto dominante, entonces existe un umbral θ D tal que los elementos de D son precisamente los candidatos cuyas puntuaciones Copeland son al menos θ D . (La puntuación Copeland de un candidato es el número de otros candidatos a los que derrota más la mitad del número de otros candidatos con los que está empatado).
Demostración: Elijamos d como un elemento de D con puntuación Copeland mínima, e identifiquemos esta puntuación con θ D . Ahora supongamos que algún candidato e ∉ D tiene una puntuación Copeland no menor que θ D . Entonces, como d pertenece a D y e no, se sigue que d derrota a e ; y para que la puntuación Copeland de e sea al menos igual a la de d , debe haber algún tercer candidato f contra el cual e obtenga una mejor puntuación que d . Si f ∈ D , entonces tenemos un elemento de D que no derrota a e , y si f ∉ D entonces tenemos un candidato fuera de D al que d no derrota, lo que lleva a una contradicción en ambos sentidos. ∎
El criterio de Smith es un criterio de sistema de votación que formaliza una idea de la regla de la mayoría más sólida que el criterio de Condorcet . Un sistema de votación satisface el criterio de Smith si siempre elige un candidato del conjunto de Smith.
Aunque es menos común, el término Smith-eficiente también se ha utilizado para métodos que eligen del conjunto de Smith. [3]
He aquí un ejemplo de un electorado en el que no hay ningún ganador de Condorcet: hay cuatro candidatos: A, B, C y D. El 40% de los votantes considera que D>A>B>C. El 35% de los votantes considera que B>C>A>D. El 25% de los votantes considera que C>A>B>D. El conjunto de Smith es {A,B,C}. Los tres candidatos del conjunto de Smith son mayoritariamente preferidos sobre D (ya que el 60% considera que cada uno de ellos es superior a D). El conjunto de Smith no es {A,B,C,D} porque la definición exige el subconjunto más pequeño que cumpla las otras condiciones. El conjunto de Smith no es {B,C} porque B no es mayoritariamente preferido sobre A; el 65% considera que A es superior a B. (Etc.)
En este ejemplo, bajo minimax, A y D empatan; bajo Smith//Minimax, A gana.
En el ejemplo anterior, los tres candidatos del conjunto Smith están en un ciclo de mayoría de "piedra/papel/tijera" : A supera a B por una mayoría del 65%, B supera a C por una mayoría del 75% y C supera a A por una mayoría del 60%.
Cualquier método de elección que cumpla con el criterio de Smith también cumple con el criterio de ganador de Condorcet , ya que si hay un ganador de Condorcet, entonces es el único candidato en el conjunto de Smith. Los métodos de Smith también cumplen con el criterio de perdedor de Condorcet , porque un perdedor de Condorcet nunca caerá en el conjunto de Smith. También implica el criterio de mayoría mutua , ya que el conjunto de Smith es un subconjunto del conjunto MMC. [2] Por el contrario, cualquier método que falle en cualquiera de esos tres criterios mayoritarios (mayoría mutua, perdedor de Condorcet o ganador de Condorcet) también fallará en el criterio de Smith.
El criterio de Smith se satisface con los métodos de pares clasificados , de Schulze , de Nanson y otros métodos. Además, cualquier método de votación se puede modificar para satisfacer el criterio de Smith, encontrando el conjunto de Smith y eliminando a los candidatos que estén fuera de él.
Por ejemplo, el método de votación Smith//Minimax aplica Minimax a los candidatos del conjunto Smith. Otro ejemplo es el método alternativo de Tideman , que alterna entre la eliminación de candidatos fuera del conjunto Smith y la eliminación del candidato que fue el perdedor por mayoría relativa (similar a la segunda vuelta ), hasta que se encuentra un ganador de Condorcet. Un enfoque diferente es elegir al miembro del conjunto Smith que esté en el primer lugar en el orden de llegada del método de votación.
Los métodos que no cumplen el criterio de Condorcet tampoco cumplen el criterio de Smith. Sin embargo, algunos métodos de Condorcet (como Minimax ) pueden no cumplir el criterio de Smith.
El conjunto de Smith contiene el conjunto de Copeland y el conjunto de Landau como subconjuntos.
También contiene el conjunto de Banks y el conjunto bipartidista . También se han definido otros subconjuntos del conjunto de Smith. [4]
El conjunto de Smith se puede calcular con el algoritmo de Floyd–Warshall en el tiempo Θ ( n 3 ) o el algoritmo de Kosaraju en el tiempo Θ ( n 2 ).
El algoritmo puede presentarse en detalle mediante un ejemplo. Supongamos que la matriz de resultados es la siguiente:
Aquí, una entrada en la tabla principal es 1 si el primer candidato fue preferido al segundo por más votantes que los que prefirieron el segundo al primero; 0 si se cumple la relación opuesta; y1/2 Si hay un empate, la última columna indica la puntuación Copeland del primer candidato.
El algoritmo para calcular el conjunto de Smith es aglomerativo: comienza con el conjunto de Copeland, que se garantiza que es un subconjunto de él, pero que a menudo será más pequeño, y va añadiendo elementos hasta que no se necesiten más. El primer paso es ordenar los candidatos según su puntuación:
Observamos la puntuación más alta (5) y consideramos a los candidatos (ganadores de Copeland) cuya puntuación es al menos tan alta, es decir {A, D}. Estos pertenecen ciertamente al conjunto Smith, y cualquier candidato al que no derroten deberá agregarse. Para encontrar candidatos invictos, observamos las celdas en la tabla debajo del cuadrado superior izquierdo de 2 × 2 que contiene {A, D} (este cuadrado se muestra con un borde discontinuo): las celdas en cuestión están sombreadas en amarillo en la tabla. Necesitamos encontrar la entrada más baja (posicionalmente) distinta de cero entre estas celdas, que es la celda en la fila G. Todos los candidatos hasta esta fila, y cualquier fila inferior con la misma puntuación, deben agregarse al conjunto, que se expande a {A, D, G}.
Ahora observamos las celdas nuevas que deben tenerse en cuenta, que son las que se encuentran debajo del cuadrado superior izquierdo que contiene {A, D, G}, pero excluyendo las de las dos primeras columnas que ya hemos tenido en cuenta. Las celdas que requieren atención están sombreadas en azul pálido. Como antes, ubicamos la entrada distinta de cero posicionalmente más baja entre las celdas nuevas, agregando todas las filas hasta ella y todas las filas con el mismo puntaje al conjunto expandido, que ahora incluye {A, D, G, C}.
Repetimos la operación para las nuevas celdas que se encuentran debajo de los cuatro miembros que se sabe que pertenecen al conjunto de Smith. Estas están sombreadas en rosa y nos permiten encontrar candidatos que no hayan sido derrotados por ninguno de {A, D, G, C}. Nuevamente, hay solo uno, F, que agregamos al conjunto.
Las celdas que se tienen en cuenta están sombreadas en verde pálido y, dado que todas sus entradas son cero, no necesitamos agregar nuevos candidatos al conjunto, que, por lo tanto, queda fijado como {A, D, G, C, F}. Y al observar que todas las entradas en el recuadro negro son cero, tenemos la confirmación de que todos los candidatos que están por encima de él derrotan a todos los candidatos que están dentro de él.
La siguiente función C ilustra el algoritmo devolviendo la cardinalidad del conjunto de Smith para una matriz de resultados duplicada r y una matriz s de puntuaciones de Copeland duplicadas. Hay n candidatos; r i j es 2 si más votantes prefieren i a j que prefieren j a i , 1 si los números son iguales y 0 si más votantes prefieren j a i que prefieren i a j ; s i es la suma sobre j de r i j . Se supone que los candidatos están ordenados en orden decreciente de puntuación de Copeland.
int smithset ( int ** r , int * s , intn ) { int fila , columna , izq . , der .; para ( der. = 1 , izq. = 0 ; izq . < der.; izq. = der . , der . = fila + 1 ) { para ( ; der. < n && s [ der . ] == s [ der. - 1 ]; der. ++ ); /* esta línea es opcional */ para ( col = der. , fila = n ; col == der. && fila >= der .; fila -- ) para ( col = izq .; col < der. && r [ fila - 1 ][ col ] == 0 ; col ++ ); } return der .; } Para muchas soluciones de torneo, se han propuesto en la literatura generalizaciones o extensiones a torneos débiles.