En la teoría de la elección social , el teorema de Gibbard-Satterthwaite es un resultado publicado independientemente por el filósofo Allan Gibbard en 1973 [1] y el economista Mark Satterthwaite en 1975. [2] Se trata de sistemas electorales ordinales deterministas que eligen un único ganador. Establece que para cada regla de votación, debe cumplirse una de las siguientes tres cosas:
- La regla es dictatorial, es decir, existe un elector distinguido que puede elegir al ganador; o
- La regla limita los posibles resultados a solo dos alternativas; o
- La regla es susceptible de votación táctica : en ciertas condiciones, la boleta sincera de algunos votantes 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 con 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 solo depender de las acciones de los votantes, sino que también puede involucrar una parte del azar.
Descripción informal
Considere tres votantes llamados Alice, Bob y Carol, que desean seleccionar un ganador entre cuatro candidatos nombrados , , y . Supongamos que utilizan el recuento 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 que se han contado todas las papeletas, se declara ganador al candidato con más puntos.
Suponga que sus preferencias son las siguientes.
Votante | Opción 1 | Opción 2 | Opción 3 | Opción 4 |
---|---|---|---|---|
Alicia | ||||
Beto | ||||
Villancico |
Si los votantes emiten votos sinceros, entonces las puntuaciones son: . Por lo tanto, candidato Será elegido, con 7 puntos.
Pero Alice puede votar estratégicamente y cambiar el resultado. Suponga que modifica su boleta para producir la siguiente situación.
Votante | Opción 1 | Opción 2 | Opción 3 | Opción 4 |
---|---|---|---|---|
Alicia | ||||
Beto | ||||
Villancico |
Alice ha mejorado estratégicamente al candidato y candidato degradado . Ahora, las puntuaciones son:. Por eso,Yo seleccioné. Alice está satisfecha con la modificación de su boleta, porque prefiere el resultado a , que es el resultado que obtendría si votara con sinceridad.
Decimos que el conteo de Borda es manipulable : existen situaciones en las que una boleta sincera 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 sólo dos opciones.
Declaración formal
Dejar Ser el conjunto de alternativas (que se supone finito), también llamadas candidatas , aunque no sean necesariamente personas: también pueden ser varias decisiones posibles sobre un tema determinado. Denotamos porel conjunto de votantes . Dejarser 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 orden de algunas alternativas. Una regla de votación es una función. Su entrada es un perfil de preferencias y da la identidad del candidato ganador.
Nosotros decimos eso es manipulable si y solo si existe un perfil donde algún votante , reemplazando su boleta con otra papeleta , puede obtener un resultado que ella prefiera (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.
Nosotros decimos eso es dictatorial si y solo si existe un votantequien es un dictador , 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 otros 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 de
Dictadura en serie
La dictadura en serie se define de la siguiente manera. Si el votante 1 tiene un candidato único más querido, entonces este candidato es elegido. De lo contrario, los posibles resultados se limitan 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 candidato único más querido entre los no eliminados, entonces este candidato es elegido. De lo contrario, la lista de posibles resultados se reduce de nuevo, etc. Si aún quedan varios candidatos no eliminados después de que se hayan examinado todas las papeletas, se utiliza una regla arbitraria de desempate.
Esta regla de votación no es manipulable: un votante siempre está mejor si comunica 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 específico o, si hay varias alternativas más queridas, 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 alternativa superior y 0 a la otra, y la alternativa con más puntos se declara ganadora. (Si ambas alternativas alcanzan el mismo número de puntos, el empate se rompe de manera arbitraria pero determinista, por ejemplo, resultadogana.) Esta regla de votación no es manipulable porque un votante siempre está mejor si comunica sus preferencias sinceras; y claramente no es dictatorial. Muchas otras reglas no son ni manipulables ni dictatoriales: por ejemplo, suponga que la alternativa gana si obtiene dos tercios de los votos, y gana de lo contrario.
Una forma de juego que muestra que lo contrario no se sostiene
Considere la siguiente regla. Todos los candidatos son eliminados, excepto el candidato o los candidatos que ocupan los primeros puestos en la boleta del votante 1. Luego, entre los candidatos no eliminados, uno es elegido usando el conteo de Borda . Todo este proceso es dictatorial, por definición. Sin embargo, es manipulable, por las mismas razones que el habitual recuento de Borda. Por tanto, el teorema de Gibbard-Satterthwaite es una implicación y no una equivalencia.
Corolario
Consideremos ahora el caso en el que, por supuesto, un votante no puede ser indiferente entre dos candidatos. Denotamos porel conjunto de órdenes totales estrictas sobrey definimos una estricta regla de votación en función. Las definiciones de posibles desenlaces , 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 impacto 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 ninguna alternativa. Solo se asume que al menos tres de ellos pueden ganar, es decir, son posibles resultados de la regla de votación. Es posible que en ningún caso se puedan elegir otras alternativas: el teorema y el corolario siguen siendo válidos. Sin embargo, el corolario a veces se presenta bajo una forma menos general: [3] en lugar de asumir que la regla tiene al menos tres resultados posibles, a veces se asume quecontiene al menos tres elementos y que la regla de votación es a , es decir, todas las alternativas es un resultado posible. [4] 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 al mismo candidato, entonces ella debe ser elegida. [5] [6]
Boceto de 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, 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 la prueba en el caso simplificado donde la regla de votaciónse supone que es unánime. Es posible construir una función de clasificación social., de la siguiente manera: para decidir si , la 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 no manipulable y no dictatorial, entonces satisface 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, talla función no puede existir. Por lo tanto, tal regla de votacióntampoco puede existir. [7] : 214–215
Historia
Charles Dodgson, también conocido como Lewis Carroll , un pionero en la teoría de la elección social, ya notó el aspecto estratégico del voto en 1876 . Su cita (sobre un sistema de votación en particular) se hizo famosa por Duncan Black : [8]
Este principio de votación hace que una 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. [9] En un artículo con Michael Dummett , [10] él conjetura que las reglas de votación deterministas con al menos tres cuestiones enfrentan una votación táctica endémica . [11] Esta conjetura de Farquarson-Dummett fue probada 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 probar el resultado que ahora conocemos como teorema de Gibbard , y luego deduce el resultado actual, que es una consecuencia inmediata de él. [1] Independientemente, Satterthwaite demuestra el mismo resultado en su tesis doctoral en 1973, luego lo publica en un artículo de 1975. [2] Su demostración 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 breves, ya sea para el teorema mismo o para el corolario y versiones debilitadas que mencionamos anteriormente. [4] [5] [6] [12] [13] [14] [15] [16] [17]
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 puede no solo depender de las papeletas sino que también puede involucrar una parte del azar.
El teorema de Duggan-Schwartz [18] extiende este resultado en otra dirección, al tratar con reglas de votación deterministas que eligen un subconjunto no vacío de 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 fundamental 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: [7] : 215
El teorema de 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 mediante diversas modificaciones en el modelo.
La idea principal de estas "rutas de escape" es que tratan sólo con clases restringidas de preferencias, en contraste con el teorema de Gibbard-Satterthwaite, que trata de preferencias arbitrarias. Por ejemplo, en esta disciplina, con frecuencia se asume que los agentes tienen preferencias cuasi-lineales , lo que significa que su función de utilidad depende linealmente del dinero. En ese caso, las transferencias monetarias se pueden utilizar para inducirlos a actuar con sinceridad. Ésta es la idea detrás de la exitosa subasta de Vickrey-Clarke-Groves .
Ver también
- Teorema de gibbard
- Teorema de imposibilidad de Arrow
- Teorema de Duggan-Schwartz
Referencias
- ↑ a b Gibbard, Allan (1973). "Manipulación de esquemas de votación: un resultado general". Econometrica . 41 (4): 587–601. doi : 10.2307 / 1914083 . JSTOR 1914083 .
- ^ a b Satterthwaite, Mark Allen (abril de 1975). "Prueba de estrategia y condiciones de Arrow: teoremas de existencia y correspondencia para procedimientos de votación y funciones de bienestar social". Revista de teoría económica . 10 (2): 187–217. CiteSeerX 10.1.1.471.9842 . doi : 10.1016 / 0022-0531 (75) 90050-2 .
- ^ Weber, Tjark (2009). "Alternativas frente a resultados: una nota sobre el teorema de Gibbard-Satterthwaite" . Informe técnico (Biblioteca de la Universidad de Munich) .
- ^ a b Reny, Philip J. (2001). "Teorema de Arrow y el teorema de Gibbard-Satterthwaite: un enfoque unificado". Cartas económicas . 70 (1): 99–105. CiteSeerX 10.1.1.130.1704 . doi : 10.1016 / S0165-1765 (00) 00332-3 .
- ^ a b Benoît, Jean-Pierre (2000). "El teorema de Gibbard-Satterthwaite: una prueba simple". Cartas económicas . 69 (3): 319–322. doi : 10.1016 / S0165-1765 (00) 00312-8 . ISSN 0165-1765 .
- ^ a b Sen, Arunava (2001). "Otra prueba directa del teorema de Gibbard-Satterthwaite" (PDF) . Cartas económicas . 70 (3): 381–385. doi : 10.1016 / S0165-1765 (00) 00362-1 . ISSN 0165-1765 .
- ^ a b Vazirani, Vijay V .; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
- ^ Negro, Duncan (1958). La teoría de los comités y las elecciones . Prensa de la Universidad de Cambridge.
- ^ Farquharson, Robin (febrero de 1956). "Sencillez en los procedimientos de votación". Documentos económicos de Oxford . Series nuevas. 8 (1): 80–89. doi : 10.1093 / oxfordjournals.oep.a042255 . JSTOR 2662065 .
- ^ Dummett, Michael; Farquharson, Robin (enero de 1961). "Estabilidad en la votación". Econometrica . 29 (1): 33–43. doi : 10.2307 / 1907685 . JSTOR 1907685 .
- ^ Dummett, Michael (2005). "El trabajo y la vida de Robin Farquharson". Elección social y bienestar . 25 (2): 475–483. doi : 10.1007 / s00355-005-0014-x . JSTOR 41106711 .
- ^ Gärdenfors, Peter (1977). "Una prueba concisa del teorema sobre la manipulación de funciones de elección social". Elección pública . 32 : 137-142. doi : 10.1007 / bf01718676 . ISSN 0048-5829 . JSTOR 30023000 .
- ^ Barberá, Salvador (1983). "Estrategia de prueba y votantes fundamentales: una prueba directa del teorema de Gibbard-Satterthwaite". Revista económica internacional . 24 (2): 413–417. doi : 10.2307 / 2648754 . ISSN 0020-6598 . JSTOR 2648754 .
- ^ Dummett, Michael (1984). Procedimientos de votación . Prensa de la Universidad de Oxford. ISBN 978-0198761884.
- ^ Fara, Rudolf; Salles, Maurice (2006). "Una entrevista con Michael Dummett: de la filosofía analítica al análisis de la votación y más allá" (PDF) . Elección social y bienestar . 27 (2): 347–364. doi : 10.1007 / s00355-006-0128-9 . JSTOR 41106783 .
- ^ Moulin, Hervé (1991). Axiomas de la toma de decisiones cooperativa . Prensa de la Universidad de Cambridge. ISBN 9780521424585. Consultado el 10 de enero de 2016 .
- ^ Taylor, Alan D. (abril de 2002). "La manipulabilidad de los sistemas de votación". The American Mathematical Monthly . 109 (4): 321–337. doi : 10.2307 / 2695497 . JSTOR 2695497 .
- ^ Duggan, John; Schwartz, Thomas (2000). "Manipulabilidad estratégica sin determinación o creencias compartidas: Gibbard-Satterthwaite generalizado". Elección social y bienestar . 17 (1): 85–93. doi : 10.1007 / PL00007177 . ISSN 0176-1714 . JSTOR 41106341 .