En los sistemas de votación , el conjunto de Smith , que lleva el nombre de John H. Smith , pero también conocido como el ciclo superior , o como suposición de elección superior generalizada (GETCHA), es el conjunto de candidatos no vacío más pequeño en una elección en particular, de modo que cada El miembro derrota a todos los candidatos fuera del grupo en una elección por parejas. El conjunto de Smith proporciona un estándar de elección óptima para el resultado de una elección. Los sistemas de votación que siempre eligen a un candidato del conjunto de Smith pasan el criterio de Smith y se dice que son "eficientes en Smith".
Un conjunto de candidatos, cada uno de cuyos miembros derrota por parejas a todos los candidatos fuera del conjunto, se conoce como conjunto dominante .
Propiedades de los conjuntos de Smith
- El conjunto de Smith siempre existe y está bien definido (consulte la siguiente sección).
- El conjunto de Smith puede tener más de un candidato, ya sea por empates por pares o por ciclos, como en la paradoja de Condorcet .
- El ganador de Condorcet , si existe, es el único miembro del grupo Smith. Si existen ganadores débiles de Condorcet, entonces están en el set de Smith.
- El conjunto de Smith es siempre un subconjunto del conjunto de candidatos preferidos por mayoría mutua , si existe. [1]
Propiedades de los conjuntos dominantes
Teorema: los conjuntos dominantes están anidados ; es decir, de dos conjuntos dominantes en una elección, uno es un subconjunto del otro.
Prueba: Supongamos por el contrario que existen dos conjuntos dominantes, D y E , ninguno de los cuales es un subconjunto del otro. A continuación, debe existir candidatos d ∈ D , e ∈ E tal que d ∉ E y E ∉ D . Pero por la hipótesis d derrota a todos los candidatos que no están en D (incluido e ) mientras que e derrota a todos los candidatos que no están en E (incluido d ), lo cual es una contradicción. ∎
Corolario: De ello 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 no es cierto umbral θ D tal que los elementos de D son, precisamente, los candidatos cuyos resultados 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).
Prueba: Elige D como un elemento de D con la puntuación mínima Copeland, e identificar este partido en el θ D . Ahora supongamos que algún candidato e ∉ D tiene un Copeland no menor puntuación de θ D . Entonces, dado que d pertenece a D y e no, se sigue que d derrota a e ; y con el fin de e ' s Copeland puntuación que ser al menos igual a D ' s, tiene que haber alguna tercer candidato f contra quien electrónico obtiene una puntuación mejor que hace 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 a quien d no derrota, lo que lleva a una contradicción de cualquier manera. ∎
Comparación de conjuntos de Schwartz
El conjunto de Schwartz , conocido como el axioma de elección óptima generalizada o GOCHA, está estrechamente relacionado y es siempre un subconjunto del conjunto de Smith. El conjunto de Smith es más grande si y solo si un candidato en el conjunto de Schwartz tiene un empate por parejas con un candidato que no está en el conjunto de Schwartz.
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 de este tipo fuera del conjunto:
- candidatos que tienen vínculos por parejas con candidatos en el conjunto,
- candidatos que derrotan a un candidato en el set.
Tenga en cuenta que los candidatos del segundo tipo solo pueden existir después de que se hayan agregado los candidatos del primer tipo.
Algoritmos
El conjunto de Smith se puede calcular en tiempo cuadrático a partir de la puntuación de Copeland. Suponga que la matriz de resultados es la siguiente:
2do 1er | A | B | C | D | mi | F | GRAMO | puntaje | |
---|---|---|---|---|---|---|---|---|---|
A | - | 1 | 1 | 1 | 1 | 1 | 0 | 5 | |
B | 0 | - | 0 | 0 | 1 | 0 | 0 | 1 | |
C | 0 | 1 | - | 0 | 1 | 1/2 | 1 | 3 1/2 | |
D | 0 | 1 | 1 | - | 1 | 1 | 1 | 5 | |
mi | 0 | 0 | 0 | 0 | - | 0 | 0 | 0 | |
F | 0 | 1 | 1/2 | 0 | 1 | - | 0 | 2 1/2 | |
GRAMO | 1 | 1 | 0 | 0 | 1 | 1 | - | 4 |
Aquí una entrada en la tabla principal es 1 si el primer candidato fue preferido al segundo por más votantes que el segundo al primero; 0 si se cumple la relación opuesta; y 1/2si hay empate. La última columna da la puntuación Copeland del primer candidato.
El algoritmo para calcular el conjunto de Smith es aglomerativo: comienza con el conjunto de Copeland, que está garantizado como un subconjunto del mismo, pero a menudo será más pequeño, y agrega elementos hasta que no se necesitan más. El primer paso es clasificar a los candidatos según la puntuación:
2do 1er | A | D | GRAMO | C | F | B | mi | puntaje | |
---|---|---|---|---|---|---|---|---|---|
A | - | 1 | 0 | 1 | 1 | 1 | 1 | 5 | |
D | 0 | - | 1 | 1 | 1 | 1 | 1 | 5 | |
GRAMO | 1 | 0 | - | 0 | 1 | 1 | 1 | 4 | |
C | 0 | 0 | 1 | - | 1/2 | 1 | 1 | 3 1/2 | |
F | 0 | 0 | 0 | 1/2 | - | 1 | 1 | 2 1/2 | |
B | 0 | 0 | 0 | 0 | 0 | - | 1 | 1 | |
mi | 0 | 0 | 0 | 0 | 0 | 0 | - | 0 |
Observamos la puntuación más alta (5) y consideramos a los candidatos (los ganadores de Copeland) cuya puntuación sea al menos así de alta, es decir, {A, D}. Estos ciertamente pertenecen al grupo de Smith, y cualquier candidato a quien no derroten deberá ser agregado. Para encontrarlos, miramos las celdas en la tabla debajo del cuadrado superior izquierdo que los contiene: estas celdas 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 miramos todas las celdas nuevas que deben considerarse, que son las que están 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 necesitan atención están sombreadas en azul pálido. Como antes, ubicamos la entrada distinta de cero posicionalmente más baja entre las nuevas celdas, agregando todas las filas hacia abajo y todas las filas con la misma puntuación, al conjunto expandido, que ahora comprende {A, D, G, C} .
Repetimos la operación para las nuevas celdas debajo de los cuatro miembros que se sabe que pertenecen al conjunto de Smith. Estos están sombreados en rosa y nos permiten encontrar candidatos que no hayan sido derrotados por {A, D, G, C}. Nuevamente, solo hay uno, F, que agregamos al conjunto.
Las celdas que entran en consideración están sombreadas en verde pálido y, dado que todas sus entradas son cero, no es necesario agregar nuevos candidatos al conjunto, que por lo tanto se fija como {A, D, G, C, F}. Y al notar que todas las entradas en la caja negra son cero, tenemos la confirmación de que todos los candidatos arriba derrotan a todos los candidatos dentro de ella.
La siguiente función C ilustra el algoritmo devolviendo la cardinalidad del conjunto de Smith para una matriz de resultados duplicada dada r y una matriz s de puntajes de Copeland duplicados. Hay n candidatos; r j i 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 de j de r i j . Se supone que los candidatos están clasificados en orden decreciente de puntuación Copeland.
int smithset (int ** r, int * s, int n) {fila int, col, lhs, rhs; para (rhs = 1, lhs = 0; lhs;> {para (; rhs / * esta línea es opcional * / for (col = rhs, row = n; col == rhs && row> = rhs; row--) for (col = lhs; col } return lhs; }
Otros algoritmos que se pueden aplicar al mismo problema son: el algoritmo Floyd-Warshall ; una versión del algoritmo de Kosaraju y el algoritmo de Tarjan . Ninguno es más rápido que cuadrático.
El método de Smith
El conjunto Smith puede verse como la definición de un método de votación clasificado en el que ...
Todos los miembros del grupo Smith son ganadores. Suele combinarse con otro método. [2]
Un ejemplo notable del método de Smith en combinación es Smith / IRV (ver votación de segunda vuelta instantánea ).
Ver también
Referencias
Otras lecturas
- Ward, Benjamin (1961). "Regla de la mayoría y asignación". Revista de resolución de conflictos . 5 (4): 379–389. doi : 10.1177 / 002200276100500405 . En un análisis de la toma de decisiones en serie basada en la regla de la mayoría, describe el conjunto de Smith y el conjunto de Schwartz.
- Smith, JH (1973). "Agregación de preferencias con electorados variables". Econometrica . La sociedad econométrica. 41 (6): 1027–1041. doi : 10.2307 / 1914033 . JSTOR 1914033 .Introduce una versión de un Criterio de Condorcet generalizado que se satisface cuando las elecciones por pares se basan en una elección de mayoría simple, y para cualquier grupo dominante, cualquier candidato del grupo es colectivamente preferido a cualquier candidato que no esté en el grupo. Pero Smith no discute la idea de un conjunto dominante más pequeño.
- Fishburn, Peter C. (1977). "Funciones de elección social de Condorcet". Revista SIAM de Matemática Aplicada . 33 (3): 469–489. doi : 10.1137 / 0133030 . Reduce el criterio de Condorcet generalizado de Smith al conjunto dominante más pequeño y lo llama Principio de Condorcet de Smith.
- Schwartz, Thomas (1986). La lógica de la elección colectiva . Nueva York: Columbia University Press. Analiza el conjunto de Smith (llamado GETCHA) y el conjunto de Schwartz (llamado GOTCHA) como posibles estándares para una elección colectiva óptima.
- Somdeb Lahiri (nd), 'Toma de decisiones grupal y multicriterio'. Describe algunas propiedades de los conjuntos de opciones.
enlaces externos
- Algoritmos de ejemplo para calcular el conjunto de Smith