Teorema de Gibbard–Satterthwaite

En la teoría de la elección social, el teorema de Gibbard–Satterthwaite es un resultado publicado de forma independiente por el filósofo Allan Gibbard en 1973 y el economista Mark Satterthwaite en 1975. Se trata de sistemas electorales ordinales deterministas que eligen a un único ganador. Establece que para cada regla de votación, una de las siguientes tres cosas debe cumplir:

1. La regla es dictatorial, es decir, existe un votante distinguido que puede elegir al ganador; o
2. La regla limita los posibles resultados a solo dos alternativas; o
3. La regla es susceptible de votación táctica: en ciertas condiciones, la boleta sincera de un votante puede no defender mejor su opinión.

Si bien el alcance de este teorema se limita a la votación ordinal, el teorema de Gibbard es más general, ya que trata de procesos de decisión colectiva que pueden no ser ordinales: por ejemplo, sistemas de votación donde los votantes asignan calificaciones a los candidatos. El teorema de Gibbard de 1978 y el teorema de Hylland son aún más generales y extienden estos resultados a procesos no deterministas, es decir, donde el resultado puede no sólo depender de las acciones de los votantes sino también involucrar una parte del azar.

Descripción informal

Considere tres votantes llamados Alice, Bob y Carol, que desean seleccionar un ganador entre cuatro candidatos llamados , y. Supongamos que utilizan el conteo de Borda: cada votante comunica su orden de preferencia sobre los candidatos. Por cada papeleta se asignan 3 puntos al primer candidato, 2 puntos al segundo candidato, 1 punto al tercero y 0 puntos al último. Una vez contadas todas las papeletas, se declara ganador al candidato con más puntos.

Suponga que sus preferencias son las siguientes.

Votante	Elección 1	Opción 2	Opción 3	Elección 4
Alicia
Beto
Villancico

Si los votantes emitieron votos sinceros, entonces los puntajes son: . Por lo tanto, el candidato será elegido, con 7 puntos.

Pero Alice puede votar estratégicamente y cambiar el resultado. Supongamos que modifica su boleta, para producir la siguiente situación.

Votante	Elección 1	Opción 2	Opción 3	Elección 4
Alicia
Beto
Villancico

Alice ha mejorado estratégicamente el candidato y el candidato degradado . Ahora, los puntajes son: . Por lo tanto, es elegido. Alice está satisfecha con la modificación de su boleta porque prefiere el resultado a , que es el resultado que obtendría si votara sinceramente.

Decimos que el conteo de Borda es manipulable: existen situaciones en las que un voto sincero no defiende mejor las preferencias de un votante.

El teorema de Gibbard-Satterthwaite establece que toda regla de votación es manipulable, excepto posiblemente en dos casos: si hay un votante distinguido que tiene un poder dictatorial, o si la regla limita los posibles resultados a solo dos opciones.

Declaración formal

Sea el conjunto de alternativas (que se supone finito), también llamados candidatos, aunque no sean necesariamente personas: también pueden ser varias decisiones posibles sobre un tema dado. Denotamos por el conjunto de votantes. Sea el conjunto de órdenes débiles estrictas sobre : ​​un elemento de este conjunto puede representar las preferencias de un votante, donde un votante puede ser indiferente con respecto al ordenamiento de algunas alternativas. Una regla de votación es una función . Su entrada es un perfil de preferencias y arroja la identidad del candidato ganador.

Decimos que es manipulable si y solo si existe un perfil donde algún votante , al reemplazar su papeleta por otra papeleta , puede obtener el resultado que prefiere (en el sentido de ).

Denotamos por la imagen de , es decir, el conjunto de posibles resultados de la elección. Por ejemplo, decimos que tiene al menos tres resultados posibles si y solo si la cardinalidad de es 3 o más.

Decimos que es dictatorial si y sólo si existe un votante que es dictatorial, en el sentido de que la alternativa ganadora es siempre la que más le gusta entre los posibles resultados, independientemente de las preferencias de los demás votantes. Si el dictador tiene varias alternativas igualmente preferidas entre los posibles resultados, entonces la alternativa ganadora es simplemente una de ellas.

Teorema de Gibbard-Satterthwaite : si una regla de votación tiene al menos 3 resultados posibles y no es dictatorial, entonces es manipulable.

Ejemplos

Dictadura en serie

La dictadura en serie se define de la siguiente manera. Si el votante 1 tiene un único candidato que más gusta, entonces este candidato es elegido. De lo contrario, los resultados posibles se restringen a los candidatos más queridos, mientras que los demás candidatos se eliminan. Luego se examina la boleta del votante 2: si hay un único candidato favorito entre los no eliminados, entonces este candidato es elegido. De lo contrario, la lista de posibles resultados se vuelve a reducir, etc. Si todavía hay varios candidatos no eliminados después de que se hayan examinado todas las papeletas, entonces se utiliza una regla de desempate arbitraria.

Esta regla de votación no es manipulable: siempre es mejor que un votante comunique sus preferencias sinceras. También es dictatorial, y su dictador es el votante 1: la alternativa ganadora es siempre la que más gusta a ese votante concreto o, si hay varias alternativas que más gustan, se elige entre ellas.

Voto por mayoría simple

Si solo hay 2 resultados posibles, una regla de votación puede no ser manipulable sin ser dictatorial. Por ejemplo, es el caso del voto de mayoría simple: cada votante asigna 1 punto a su primera alternativa y 0 a la otra, y la alternativa con más puntos es declarada ganadora. (Si ambas alternativas alcanzan el mismo número de puntos, el empate se rompe de manera arbitraria pero determinista, por ejemplo, gana el resultado). Esta regla de votación no es manipulable porque siempre es mejor que un votante comunique sus preferencias sinceras; y claramente no es dictatorial. Muchas otras reglas no son manipulables ni dictatoriales: por ejemplo, suponga que la alternativa gana si obtiene dos tercios de los votos y gana en caso contrario.

Una forma de juego que muestra que lo contrario no se cumple

Considere la siguiente regla. Todos los candidatos son eliminados, excepto el candidato o candidatos que se colocan en la primera posición en la boleta del votante 1. Luego, entre los candidatos no eliminados, se elige uno utilizando el conteo de Borda. Todo este proceso es dictatorial, por definición. Sin embargo, es manipulable, por las mismas razones que el conteo habitual de Borda. Por lo tanto, el teorema de Gibbard-Satterthwaite es una implicación y no una equivalencia.

Corolario

Consideremos ahora el caso en el que, por suposición, un votante no puede ser indiferente entre dos candidatos. Denotamos por el conjunto de órdenes totales estrictas y definimos una regla de votación estricta como una función . Las definiciones de resultados posibles, manipulables, dictatoriales tienen adaptaciones naturales a este marco.

Para una regla de votación estricta, lo contrario del teorema de Gibbard-Satterthwaite es cierto. De hecho, una regla de votación estricta es dictatorial si y solo si siempre selecciona al candidato más querido del dictador entre los posibles resultados; en particular, no depende de las papeletas de los demás votantes. En consecuencia, no es manipulable: la dictadora está perfectamente defendida por su voto sincero, y los demás votantes no tienen incidencia en el resultado, por lo que no tienen ningún incentivo para desviarse del voto sincero. Así, obtenemos la siguiente equivalencia.

Teorema : si una regla de votación estricta tiene al menos 3 resultados posibles, no es manipulable si y solo si es dictatorial.

En el teorema, así como en el corolario, no es necesario suponer que se puede elegir cualquier alternativa. Solo se supone que al menos tres de ellos pueden ganar, es decir, son posibles resultados de la regla de votación. Es posible que se puedan elegir algunas otras alternativas en ninguna circunstancia: el teorema y el corolario siguen siendo válidos. Sin embargo, el corolario a veces se presenta bajo una forma menos general: en lugar de suponer que la regla tiene al menos tres posibles resultados, a veces se supone que contiene al menos tres elementos y que la regla de votación es sobre, es decir, cada alternativa es posible. Salir. La suposición de estar en a veces incluso se reemplaza con la suposición de que la regla es unánime., en el sentido de que si todos los votantes prefieren a la misma candidata, ésta debe ser elegida.

Bosquejo de la prueba

El teorema de Gibbard-Satterthwaite se puede demostrar con base en el teorema de imposibilidad de Arrow, que se ocupa de las funciones de clasificación social, es decir, los sistemas de votación diseñados para producir un orden de preferencia completo de los candidatos, en lugar de simplemente elegir un ganador. Damos un bosquejo de prueba en el caso simplificado donde se supone que la regla de votación es unánime. Es posible construir una función de clasificación social de la siguiente manera: para decidir si , la función crea nuevas preferencias en las que y se mueven a la parte superior de las preferencias de todos los votantes. Luego, examina si elige o . Es posible probar que, si es inmanipulable y no dictatorial, entoncessatisface las propiedades: unanimidad, independencia de alternativas irrelevantes, y no es una dictadura. El teorema de imposibilidad de Arrow dice que, cuando hay tres o más alternativas, tal función no puede existir. Por lo tanto, tal regla de votación tampoco puede existir.

Historia

El aspecto estratégico del voto ya fue advertido en 1876 por Charles Dodgson, también conocido como Lewis Carroll, pionero en la teoría de la elección social. Su cita (sobre un sistema de votación en particular) se hizo famosa por Duncan Black:

Este principio de votación hace que la elección sea más un juego de habilidad que una prueba real de los deseos de los electores.

Durante la década de 1950, Robin Farquharson publicó artículos influyentes sobre la teoría del voto. En un artículo con Michael Dummett, conjetura que las reglas de votación deterministas con al menos tres temas se enfrentan a una votación táctica endémica. Esta conjetura de Farquarson-Dummett se demuestra de forma independiente por Allan Gibbard y Mark Satterthwaite. En un artículo de 1973, Gibbard explota el teorema de imposibilidad de Arrow de 1951 para demostrar el resultado que ahora conocemos como teorema de Gibbard, y luego deduce el presente resultado, que es una consecuencia inmediata de él. Independientemente, Satterthwaite demuestra el mismo resultado en su tesis doctoral en 1973 y luego lo publica en un artículo de 1975.Su prueba también se basa en el teorema de imposibilidad de Arrow, pero no expone la versión más general dada por el teorema de Gibbard. Posteriormente, varios autores desarrollan variantes de la demostración, generalmente más cortas, ya sea para el teorema mismo o para las versiones corolario y debilitada que mencionamos anteriormente.

Resultados relacionados

El teorema de Gibbard trata de procesos de elección colectiva que pueden no ser ordinales, es decir, donde la acción de un votante puede no consistir en comunicar un orden de preferencia sobre los candidatos. El teorema de Gibbard de 1978 y el teorema de Hylland extienden estos resultados a mecanismos no deterministas, es decir, donde el resultado no solo puede depender de las papeletas, sino que también puede involucrar una parte del azar.

El teorema de Duggan-Schwartz extiende este resultado en otra dirección, al tratar con reglas de votación deterministas que eligen un subconjunto no vacío de los candidatos en lugar de un solo ganador.

Posteridad

El teorema de Gibbard-Satterthwaite generalmente se presenta como un resultado que pertenece al campo de la teoría de la elección social y se aplica a los sistemas de votación, pero también puede verse como el resultado seminal del diseño de mecanismos, que se ocupa de concebir reglas para tomar decisiones colectivas. posiblemente en procesos que impliquen una transferencia monetaria. Noam Nisan describe esta relación:

El teorema GS parece anular cualquier esperanza de diseñar funciones de elección social compatibles con incentivos. Todo el campo del Diseño de Mecanismos intenta escapar de este resultado de imposibilidad usando varias modificaciones en el modelo.

La idea principal de estas "rutas de escape" es que tratan solo con clases restringidas de preferencias, en contraste con el teorema de Gibbard-Satterthwaite, que trata con preferencias arbitrarias. Por ejemplo, en esta disciplina se asume con frecuencia que los agentes tienen preferencias casi lineales, lo que significa que su función de utilidad depende linealmente del dinero. En ese caso, las transferencias monetarias pueden utilizarse para inducirlos a actuar con veracidad. Esta es la idea detrás de la exitosa subasta de Vickrey-Clarke-Groves.