Teorema de Gibbard-Satterthwaite

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

El teorema de Gibbard-Satterthwaite es un teorema de la teoría de la elección social . 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]. Trata sobre sistemas electorales ordinales deterministas que eligen a un único ganador y muestra que para cada regla de votación de esta forma, debe cumplirse al menos una de las tres cosas siguientes:

1. La regla es dictatorial, es decir, existe un elector distinguido que puede elegir al ganador; o
2. La regla limita los resultados posibles a sólo dos alternativas; o
3. La regla no es sencilla, es decir, no existe una única estrategia que sea siempre la mejor (que no dependa de las preferencias o el comportamiento de otros votantes).

La prueba del 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

Consideremos 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 candidato con mayor puntuación, 2 puntos al segundo candidato, 1 punto al tercero y 0 puntos al último. Una vez que se han contado todas las papeletas, el candidato con más puntos es declarado ganador. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle d}$

Supongamos que sus preferencias son las siguientes:

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

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

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

Decimos que el recuento 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 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 solo dos opciones.

Declaración formal

Sea el conjunto de alternativas (que se supone finito), también llamadas candidatos , aunque no sean necesariamente personas: también pueden ser varias decisiones posibles sobre un asunto dado. Denotamos por el conjunto de votantes . Sea el conjunto de órdenes débiles estrictos sobre : un elemento de este conjunto puede representar las preferencias de un votante, donde un votante puede ser indiferente respecto del orden de algunas alternativas. Una regla de votación es una función . Su entrada es un perfil de preferencias y produce 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 , al reemplazar su papeleta por otra , puede obtener un 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}}$

Denotamos por la imagen de , es decir, el conjunto de resultados posibles para 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. ${\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 resultados posibles, 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 de los cardenales

Consideremos una elección de tres candidatos realizada mediante votación por puntaje . 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, sin importar 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 votación por puntaje del votante será débilmente consistente con la clasificación honesta de ese votante. Sin embargo, la puntuación óptima real puede depender de las otras papeletas emitidas, como lo indica el teorema de Gibbard .

Dictadura serial

La dictadura serial se define de la siguiente manera: si el elector 1 tiene un único candidato que le gusta más, este candidato es elegido. En caso contrario, los resultados posibles se limitan a los candidatos que más gustan, mientras que los demás candidatos son eliminados. A continuación, se examina la papeleta del elector 2: si hay un único candidato que le gusta más entre los que no son eliminados, este candidato es elegido. En caso contrario, la lista de resultados posibles se reduce de nuevo, etc. Si después de examinar todas las papeletas todavía quedan varios candidatos que no son eliminados, se utiliza una regla de desempate arbitraria.

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

Voto por mayoría simple

Si sólo hay dos resultados posibles, una regla de votación puede ser inmanipulable sin ser dictatorial. Por ejemplo, es el caso de la votación por mayoría simple: cada votante asigna 1 punto a su alternativa principal y 0 a la otra, y la alternativa con más puntos es declarada ganadora. (Si ambas alternativas alcanzan la misma cantidad de puntos, el empate se deshace de manera arbitraria pero determinista, por ejemplo, gana el resultado). Esta regla de votación no es manipulable porque un votante siempre está en mejores condiciones de comunicar sus preferencias sinceras; y claramente no es dictatorial. Muchas otras reglas no son ni 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

Ahora consideramos el caso en el que, por supuesto, un votante no puede ser indiferente entre dos candidatos. Denotamos por el conjunto de órdenes totales estrictas sobre 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. ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle f:{\mathcal {L}}^{n}\to {\mathcal {A}}}$

En el caso de una regla de votación estricta, se cumple el inverso del teorema de Gibbard-Satterthwaite. En efecto, una regla de votación estricta es dictatorial si y sólo si siempre elige al candidato que más le gusta al dictador entre los resultados posibles; en particular, no depende de los votos de los demás votantes. En 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 ningún incentivo para desviarse del voto sincero. Así, obtenemos la siguiente equivalencia.

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

En el teorema, así como en el corolario, no es necesario suponer que cualquier alternativa puede ser elegida. Sólo se supone que al menos tres de ellas pueden ganar, es decir, son resultados posibles de la regla de votación. Es posible que algunas otras alternativas no puedan ser elegidas 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: ^[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 que es sobre , a veces incluso se reemplaza por el supuesto de que la regla es unánime , en el sentido de que si todos los votantes prefieren al mismo candidato, entonces debe ser elegido. ^{[6] [7]} ${\displaystyle {\mathcal {A}}}$

Bosquejo de la prueba

El teorema de Gibbard-Satterthwaite se puede demostrar utilizando el teorema de imposibilidad de Arrow para funciones de clasificación social . Damos un esbozo de la prueba en el caso simplificado en el que se supone que alguna regla de votación es eficiente en el sentido de Pareto . ${\displaystyle f}$

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. ^{[ aclaración necesaria ]} Luego, examina si elige o . ${\displaystyle \operatorname {Rank} }$ ${\displaystyle a\prec b}$ ${\displaystyle \operatorname {Rank} }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \operatorname {Rank} }$ ${\displaystyle f}$ ${\displaystyle a}$ ${\displaystyle b}$

Es posible demostrar que, si no es manipulable ni dictatorial, satisface la independencia de alternativas irrelevantes. El teorema de imposibilidad de Arrow dice que, cuando hay tres o más alternativas, dicha función debe ser una dictadura . Por lo tanto, dicha regla de votación también debe ser una dictadura. ^{[8] : 214–215} ${\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] [ citas excesivas ]}

Historia

El aspecto estratégico de la votación ya lo advirtió en 1876 Charles Dodgson, también conocido como Lewis Carroll , un 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 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 de la votación. ^[16] En un artículo con Michael Dummett , ^[17] conjetura que las reglas de votación deterministas con al menos tres resultados nunca son una votación táctica directa . ^[18] Esta conjetura fue probada más tarde 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 lo publicó en un artículo de 1975. ^[3] Esta prueba también se basa en el teorema de imposibilidad de Arrow, pero no involucra la versión más general dada por el teorema de Gibbard.

Resultados relacionados

El teorema de Gibbard se ocupa de los procesos de elección colectiva que pueden no ser ordinales, es decir, en los que 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 los mecanismos no deterministas, es decir, en los que el resultado puede no depender sólo de las papeletas, sino que también puede implicar una parte de azar.

El teorema de Duggan-Schwartz extiende este resultado en otra dirección, al abordar reglas de votación deterministas que eligen múltiples ganadores. ^[19]

Importancia

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

El teorema GS parece acabar con toda esperanza de diseñar funciones de elección social compatibles con los incentivos. Todo el campo del diseño de mecanismos intenta escapar de este resultado imposible utilizando diversas modificaciones en el modelo.

La idea principal de estas "vías de escape" es que permiten una clase más amplia de mecanismos que la votación por orden de preferencia, de forma similar a las vías de escape del teorema de imposibilidad de Arrow .

Véase también

• Portal de la economía

• Teorema de imposibilidad de Arrow
• Ciclo de Condorcet
• Teorema de Duggan-Schwartz
• Teorema de Gibbard
• Votación por orden de preferencia
• Votación estratégica

Notas y referencias

1. El teorema de Gibbard no implica que los métodos cardinales necesariamente incentiven 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) . Social Choice and Welfare . 27 (2): 347–364. doi :10.1007/s00355-006-0128-9. S2CID  46164353.
2. Gibbard, Allan (1973). "Manipulación de los esquemas de votación: un resultado general". Econometrica . 41 (4): 587–601. doi :10.2307/1914083. JSTOR  1914083.
3. Satterthwaite, Mark Allen (abril de 1975). "Impermeabilidad estratégica y condiciones de Arrow: teoremas de existencia y correspondencia para procedimientos de votación y funciones de bienestar social". Journal of Economic Theory . 10 (2): 187–217. CiteSeerX 10.1.1.471.9842 . doi :10.1016/0022-0531(75)90050-2. 
4. Weber, Tjark (2009). "Alternativas vs. 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". Economics Letters . 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 demostración sencilla". Economics Letters . 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) . Economics Letters . 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 demostración concisa del teorema sobre la manipulación de las funciones de elección social". Public Choice . 32 : 137–142. doi :10.1007/bf01718676. ISSN  0048-5829. JSTOR  30023000. S2CID  153421058.
10. Barberá, Salvador (1983). "Estrategia-Proofness y votantes decisivos: 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 . Oxford University Press. 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. Cambridge University Press. ISBN 9780521424585. Recuperado el 10 de enero de 2016 .
14. 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.
15. Black, Duncan (1958). La teoría de los comités y las elecciones . Cambridge: University Press.
16. Farquharson, Robin (febrero de 1956). «Sencillez en los procedimientos de votación». Oxford Economic Papers . Nueva serie. 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". Econometrica . 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, John; Schwartz, Thomas (2000). "Manipulabilidad estratégica sin resolució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.