Teorema de Gibbard-Satterthwaite

Resultado de imposibilidad para los sistemas de votación por orden de preferencia

El teorema de Gibbard-Satterthwaite es un teorema de la teoría de la votación . Fue conjeturado por primera vez por el filósofo Michael Dummett y el matemático Robin Farquharson en 1961 ^[1] y luego demostrado de forma independiente por el filósofo Allan Gibbard en 1973 ^[2] y el economista Mark Satterthwaite en 1975. ^{[3] Se trata de} sistemas electorales ordinales deterministas. que elige un único ganador, y establece que para cada regla de votación de este formulario, debe cumplirse al menos una de las siguientes tres cosas:

1. La regla es dictatorial, es decir, existe un elector distinguido que puede elegir al ganador; o
2. La regla limita los posibles resultados a dos alternativas únicamente; o
3. La regla es susceptible de votación táctica : en algunas situaciones, el voto sincero de un votante puede no defender mejor su opinión .

El alcance de este teorema se limita a la votación ordinal. No se aplica a los sistemas de votación cardinal , como la votación por puntaje o la votación STAR , ni a la votación con múltiples ganadores, métodos no deterministas o mecanismos de decisión sin votación .

El teorema de Gibbard es más general y cubre procesos de decisión colectiva que pueden no ser ordinales, como la votación cardinal . ^{[nota 1]} 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, donde el resultado puede depender en parte del azar; El teorema de Duggan-Schwartz extiende estos resultados a sistemas electorales con múltiples ganadores.

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 elector comunica su orden de preferencia sobre los candidatos. En cada votación 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. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle d}$

Supongamos que sus preferencias son las siguientes.

Si los votantes emitieron votos sinceros, entonces los puntajes son: . Por tanto, el candidato resultará elegido con 7 puntos. ${\displaystyle (a:3,b:6,c:7,d:2)}$ ${\displaystyle c}$

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

Alice ha mejorado estratégicamente al candidato y al candidato degradado . Ahora, los puntajes son: . Por 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. ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle (a:2,b:7,c:6,d:3)}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle c}$

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

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

Declaración formal

Sea 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 una cuestión determinada. Denotamos por el conjunto de electores . Sea el conjunto de órdenes débiles estrictos : 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 arroja la identidad del candidato ganador. ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {N}}=\{1,\ldots ,n\}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle f:{\mathcal {P}}^{n}\to {\mathcal {A}}}$ ${\displaystyle (P_{1},\ldots ,P_{n})\in {\mathcal {P}}^{n}}$

Decimos que es manipulable si y sólo si existe un perfil en el que algún votante , reemplazando su boleta por otra , pueda obtener el resultado que prefiere (en el sentido de ). ${\displaystyle f}$ ${\displaystyle (P_{1},\ldots ,P_{n})\in {\mathcal {P}}^{n}}$ ${\displaystyle i}$ ${\displaystyle P_{i}}$ ${\displaystyle P_{i}'}$ ${\displaystyle P_{i}}$

Lo denotamos con 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 sólo si la cardinalidad de es 3 o más. ${\displaystyle f({\mathcal {P}}^{n})}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f({\mathcal {P}}^{n})}$

Decimos que es dictatorial si y sólo si existe un votante que es dictador , en el sentido de que la alternativa ganadora es siempre la que más le gusta entre los resultados posibles, 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. ${\displaystyle f}$ ${\displaystyle i}$

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

Contraejemplos y lagunas

Existe una variedad de "contraejemplos" del teorema de Gibbard-Satterthwaite cuando las condiciones del teorema no se aplican.

votación cardinal

Consideremos una elección de tres candidatos realizada mediante votación por puntuación . Siempre es óptimo para un votante darle al mejor candidato la puntuación más alta posible y al peor candidato la puntuación más baja posible. Entonces, no importa qué puntuación le asigne el votante al candidato del medio, siempre estará (no estrictamente) entre la primera y la última puntuación; esto implica que la puntuación del votante será débilmente consistente con la clasificación honesta de ese votante. Sin embargo, la puntuación óptima real puede depender de los demás votos emitidos, como lo indica el teorema de Gibbard .

Dictadura en serie

La dictadura en serie se define de la siguiente manera. Si el votante 1 tiene un candidato único que le gusta, 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 quedan eliminados. Luego se examina la papeleta 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 reduce de nuevo, etc. Si después de examinar todas las papeletas aún quedan varios candidatos no eliminados, se aplica una regla arbitraria de desempate.

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

Voto por mayoría simple

Si sólo hay dos resultados posibles, una regla de votación puede no ser manipulable sin ser dictatorial. Por ejemplo, es el caso de la mayoría simple: cada elector asigna 1 punto a su alternativa superior 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 para un votante comunicar sus preferencias sinceras; y claramente no es dictatorial. Muchas otras reglas no son manipulables ni dictatoriales: por ejemplo, supongamos que la alternativa gana si obtiene dos tercios de los votos, y gana en caso contrario. ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle b}$

Corolario

Consideremos ahora el caso en el que, por supuesto, un votante no puede ser indiferente entre dos candidatos. Lo denotamos por el conjunto de órdenes totales estrictas y definimos una regla de votación estricta como función . Las definiciones de resultados posibles , manipulables , dictatoriales tienen adaptaciones naturales a este marco. ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle f:{\mathcal {L}}^{n}\to {\mathcal {A}}}$

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 sólo si siempre selecciona al candidato más querido por el dictador entre los posibles resultados; en particular, no depende de las papeletas de los demás votantes. Como consecuencia, no es manipulable: el dictador está perfectamente defendido por su voto sincero y los demás votantes no tienen ningún impacto en el resultado, por lo que no tienen incentivos 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.

Tanto en el teorema como en el corolario, no es necesario suponer que se pueda elegir alguna alternativa. Sólo se supone 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: ^[4] en lugar de suponer que la regla tiene al menos tres resultados posibles, a veces se supone que contiene al menos tres elementos y que la regla de votación es sobre , es decir, cada alternativa es un resultado posible. ^[5] El supuesto de estar en lo cierto es a veces incluso reemplazado por el supuesto de que la regla es unánime , en el sentido de que si todos los votantes prefieren al mismo candidato, entonces éste debe ser elegido. ^{[6] [7]} ${\displaystyle {\mathcal {A}}}$

Bosquejo de prueba

El teorema de Gibbard-Satterthwaite se puede demostrar basándose en el teorema de imposibilidad de Arrow , que trata de 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 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 cima de las preferencias de todos los votantes. Luego, examina si elige o . Es posible demostrar 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, dicha función no puede existir. Por tanto, tampoco puede existir una regla de votación de este tipo . ^{[8] : 214–215} ${\displaystyle f}$ ${\displaystyle \operatorname {Rank} }$ ${\displaystyle a\prec b}$ ${\displaystyle \operatorname {Rank} }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \operatorname {Rank} }$ ${\displaystyle f}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle f}$ ${\displaystyle \operatorname {Rank} }$ ${\displaystyle \operatorname {Rank} }$ ${\displaystyle f}$

Autores posteriores han desarrollado otras variantes de la prueba. ^{[5] [6] [7] [9] [10] [11] [12] [13] [14]}

Historia

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

Este principio de votación hace que las elecciones sean más un juego de habilidad que una verdadera prueba de los deseos de los electores.

Durante la década de 1950, Robin Farquharson publicó artículos influyentes sobre la teoría del voto. ^[16] En un artículo con Michael Dummett , ^[17] conjetura que la votación determinista gobierna con al menos tres resultados la votación táctica . ^[18] Esta conjetura fue probada posteriormente 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 . ^[2] Independientemente, Satterthwaite demostró el mismo resultado en su tesis doctoral en 1973 y luego la publicó en un artículo de 1975. ^[3] Esta prueba también se basa en el teorema de imposibilidad de Arrow, pero no incluye la versión más general dada por el teorema de Gibbard.

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 sólo depender de las votaciones sino que también puede implicar una parte del azar.

El teorema de Duggan-Schwartz ^[19] 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 único ganador.

Importancia

El teorema de Gibbard-Satterthwaite generalmente se presenta como un resultado sobre los sistemas de votación, pero también puede verse como un resultado importante del diseño de mecanismos , que se ocupa de una clase más amplia de reglas de decisión. Noam Nisan describe esta relación: ^{[8] : 215}

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 esta imposibilidad mediante diversas modificaciones en el modelo.

La idea principal de estas "rutas de escape" es que permiten una clase más amplia de mecanismos que la votación por clasificación, de manera similar a las rutas de escape del teorema de imposibilidad de Arrow .

Ver también

• Portal de economía

• Votación clasificada
• Votación estratégica
• teorema de gibbard
• Teorema de imposibilidad de Arrow
• Teorema de Duggan-Schwartz

notas y referencias

1. El teorema de Gibbard no implica que los métodos cardinales necesariamente incentivan la inversión del rango relativo de dos candidatos.

1. Rudolf Farra y Maurice Salles (octubre de 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. S2CID  46164353.
2. Gibbard, Allan (1973). "Manipulación de los sistemas de votación: un resultado general". Econométrica . 41 (4): 587–601. doi :10.2307/1914083. JSTOR  1914083.
3. Satterthwaite, Mark Allen (abril de 1975). "A prueba de estrategias 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. 
4. Weber, Tjark (2009). "Alternativas frente a resultados: una nota sobre el teorema de Gibbard-Satterthwaite". Informe técnico (Biblioteca de la Universidad de Múnich) .
5. Reny, Philip J. (2001). "Teorema de Arrow y teorema de Gibbard-Satterthwaite: un enfoque unificado". Cartas de Economía . 70 (1): 99-105. CiteSeerX 10.1.1.130.1704 . doi :10.1016/S0165-1765(00)00332-3. 
6. Benoît, Jean-Pierre (2000). "El teorema de Gibbard-Satterthwaite: una prueba sencilla". Cartas de Economía . 69 (3): 319–322. doi :10.1016/S0165-1765(00)00312-8. ISSN  0165-1765.
7. Sen, Arunava (2001). "Otra prueba directa del teorema de Gibbard-Satterthwaite" (PDF) . Cartas de Economía . 70 (3): 381–385. doi :10.1016/S0165-1765(00)00362-1. ISSN  0165-1765.
8. Vazirani, Vijay V .; Nisán, Noam ; Jardín rugoso, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
9. 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. S2CID  153421058.
10. Barberá, Salvador (1983). "Prueba de la estrategia 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.
11. Dummett, Michael (1984). Procedimientos de votación . Prensa de la Universidad de Oxford. ISBN 978-0198761884.
12. 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. S2CID  46164353.
13. 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 .
14. Taylor, Alan D. (abril de 2002). "La manipulabilidad de los sistemas de votación". El Mensual Matemático Estadounidense . 109 (4): 321–337. doi :10.2307/2695497. JSTOR  2695497.
15. Negro, Duncan (1958). La teoría de los comités y las elecciones . Prensa de la Universidad de Cambridge.
16. 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.
17. Dummett, Michael; Farquharson, Robin (enero de 1961). "Estabilidad en la votación". Econométrica . 29 (1): 33–43. doi :10.2307/1907685. JSTOR  1907685.
18. Dummett, Michael (2005). "La obra y la vida de Robin Farquharson". Elección social y bienestar . 25 (2): 475–483. doi :10.1007/s00355-005-0014-x. JSTOR  41106711. S2CID  27639067.
19. Duggan, Juan; Schwartz, Thomas (2000). "Manipulación estratégica sin determinación ni creencias compartidas: Gibbard-Satterthwaite generalizado". Elección social y bienestar . 17 (1): 85–93. doi :10.1007/PL00007177. ISSN  0176-1714. JSTOR  41106341. S2CID  271833.