Teorema de Gibbard-Satterthwaite

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 y el economista Mark Satterthwaite en 1975. Muestra que cualquier regla de votación determinista satisface al menos una de las siguientes propiedades:

La regla es dictatorial, es decir, hay un votante privilegiado que puede elegir al ganador; o
La regla solo permite la elección de dos candidatos diferentes; o
La regla es sensible al voto táctico: hay situaciones en las que una boleta sincera no es la que mejor defiende las opiniones de un votante.

Este teorema se limita a las reglas ordinales de votación: la acción de un elector consiste en dar un orden de preferencia sobre las opciones propuestas. El teorema de Gibbard más general permite considerar los mecanismos de elección colectiva que no son necesariamente ordinales: por ejemplo, los sistemas de votación donde los votantes asignan notas a los candidatos. Otros teoremas aún más generales, el teorema de Gibbard de 1978 y el teorema de Hilland , extienden estos resultados a mecanismos no deterministas, es decir, donde el resultado no solo puede depender de las acciones de los votantes sino que también puede tener un elemento de azar.

Presentación

Considere los votantes , y que deseen elegir juntos una opción entre cuatro candidatos , , y . Se asume que utilizan el método Borda : cada votante comunica un orden de preferencia sobre los candidatos. Por cada papeleta, se otorgan 3 puntos al candidato principal, 2 puntos al segundo, 1 punto al tercero y ningún punto al último. Una vez contadas todas las papeletas, se elige al candidato con más puntos. $1$ $2$ $3$ $a$ $B$ $vs$ $D$

Suponga que las preferencias son las siguientes.

avsvsBBBvsDDDaa{\ Displaystyle {\ begin {array} {c | c | c} a & c & c \\ b & b & b \\ c & d & d \\ d & a & a \ end {array}}}

{\ Displaystyle {\ begin {array} {c | c | c} a & c & c \\ b & b & b \\ c & d & d \\ d & a & a \ end {array}}}

Este medio de notación que el votante prefiere , seguido de , y ; votantes y prefieren cada uno , seguido de , y . Si los electores votan sinceramente, a continuación, los resultados son los siguientes: . Por tanto, es quien resulta elegido, con 7 puntos.

1

a

B

vs

D

2

3

vs

B

D

a

{\ Displaystyle (a: 3, b: 6, c: 7, d: 2)}

vs

Pero el votante puede encontrar que otra boleta defiende mejor sus opiniones. Suponga que modifica su boleta para terminar con la siguiente situación. $1$

BvsvsaBBDDDvsaa{\ Displaystyle {\ begin {array} {c | c | c} b & c & c \\ a & b & b \\ d & d & d \\ c & a & a \ end {array}}}

{\ Displaystyle {\ begin {array} {c | c | c} b & c & c \\ a & b & b \\ d & d & d \\ c & a & a \ end {array}}}

El votante empujó estratégicamente al candidato hacia arriba y hacia abajo al candidato . Los nuevos resultados son: . Por tanto, es quien resulta elegido. El votante está satisfecho de haber presentado una papeleta diferente de sus preferencias sinceros, ya que prefiere el nuevo resultado en lugar de , el resultado que se habría obtenido al votar sinceramente.

1

B

vs

{\ Displaystyle (a: 2, b: 7, c: 6, d: 3)}

B

1

B

vs

Se dice que el método de Borda es manipulable : hay situaciones en las que un voto sincero no defiende mejor las preferencias de un votante.

Desafortunadamente, el teorema de Gibbard-Satterthwaite muestra que una regla de votación es necesariamente manipulable, excepto posiblemente en dos casos: si hay un votante privilegiado que tiene un poder dictatorial, o si la regla permite elegir solo una 'entre dos decisiones posibles.

Declaración del teorema

Observamos el conjunto de alternativas (supuestamente terminadas), también llamadas candidatas , aunque no necesariamente sean personas: también pueden ser diferentes posibles decisiones para un tema determinado. Tomamos nota de todos los votantes . Denotamos el conjunto de órdenes estrictas débiles (en) on : un elemento de este conjunto permite representar las preferencias de un votante. Una regla de votación es una función . Toma un perfil de preferencia como argumento y devuelve un candidato ganador. ${\ mathcal {A}}$ ${\ Displaystyle {\ mathcal {N}} = \ {1, \ ldots, n \}}$ $\ mathcal {P}$ ${\ 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 solo si existe un perfil donde un determinado votante , al cambiar su papeleta por otra papeleta , puede obtener un resultado que prefiera (en el sentido de ). $F$ ${\ Displaystyle (P_ {1}, \ ldots, P_ {n}) \ in {\ mathcal {P}} ^ {n}}$ $I$ $Pi$ ${\ Displaystyle P_ {i} '}$ $Pi$

Observamos la imagen de , es decir, el conjunto de posibles resultados de la elección. Por lo tanto, decimos que tiene al menos tres resultados posibles si y solo si tiene al menos tres elementos. ${\ Displaystyle f ({\ mathcal {P}} ^ {n})}$ $F$ $F$ ${\ Displaystyle f ({\ mathcal {P}} ^ {n})}$

Se dice que es dictatorial si y solo si hay un votante que es un dictador , es decir que la alternativa ganadora es siempre su favorita entre los posibles desenlaces. Si el dictador tiene varias alternativas preferidas vinculadas entre los posibles resultados, entonces la alternativa ganadora es simplemente una de ellas. $F$ $I$

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

Ejemplos de

Dictadura en serie

El mecanismo de la dictadura en serie funciona de la siguiente manera. Si el votante 1 prefiere solo una alternativa, se elige esa alternativa. De lo contrario, restringimos los posibles resultados a nuestros candidatos favoritos empatados, y nos interesa la boleta del votante 2. Si este último tiene solo una alternativa preferida entre los que todavía están en la carrera, entonces esta es elegida. De lo contrario, restringimos aún más los posibles resultados, etc. Si aún quedan varios candidatos en la carrera después de haber consultado todas las papeletas, los candidatos se deciden según un criterio arbitrario.

Esta regla de votación no se puede manipular: un votante siempre tiene interés en anunciar sus preferencias reales. Ella también es dictatorial, y su dictador es el votante 1: la alternativa ganadora es siempre su favorita o, si prefiere varias iguales, elegida entre ellas.

Voto por mayoría simple

Si solo hay dos resultados posibles, una regla de votación puede ser no manipulable sin ser dictatorial. Este es el caso, por ejemplo, de la votación por mayoría simple: cada papeleta asigna 1 punto a la alternativa listada en la parte superior y 0 puntos a la otra. Esta regla no se puede manipular porque un votante siempre tiene interés en dar sus preferencias sinceras; y claramente no es dictatorial. Muchas otras reglas no son ni manipulables ni dictatoriales: por ejemplo, uno puede imaginar que la alternativa gana si recibe dos tercios de los votos y gana en caso contrario. $a$ $B$

Un mecanismo que muestra que lo contrario no es cierto

Considere la siguiente regla. Todos los candidatos son eliminados, excepto el candidato o candidatos colocados en la primera posición en la papeleta del votante 1. Los candidatos que aún están en la carrera se deciden por el método Borda . La regla así descrita es dictatorial por definición. Sin embargo, se puede manejar por las mismas razones que el método Borda. Por tanto, el teorema de Gibbard-Satterthwaite es de hecho una implicación y no una equivalencia.

Corolario

Ahora nos interesa el caso en el que se plantea la hipótesis de que un votante es indiferente entre dos candidatos. Denotamos el conjunto de órdenes estrictas totales en y definimos una estricta norma de votación como una función . Las definiciones de resultados dictatoriales posibles , manipulables , se extienden naturalmente dentro de este marco. $\ mathcal {L}$ ${\ 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 solo si siempre elige al candidato preferido del dictador de entre los posibles resultados; en particular, no depende en absoluto de las papeletas de otros votantes. Por tanto, no es manipulable: el dictador está perfectamente defendido con su voto sincero, y los demás votantes no influyen en el resultado, por lo que no tienen nada que perder votando con sinceridad. Por tanto, obtenemos el siguiente resultado de equivalencia.

Corolario : si una regla de votación estricta tiene al menos 3 resultados posibles, no se puede manipular si y solo si es dictatorial.

Tanto en el teorema como en el corolario, no es necesario suponer que se puede elegir ninguna alternativa. Simplemente se asume que al menos tres de ellos pueden serlo, es decir, son posibles resultados de la regla de votación. Es perfectamente posible que no se puedan elegir otras alternativas bajo ninguna circunstancia: el teorema y el corolario se aplican de todos modos. Sin embargo, el corolario a veces se presenta de una forma menos general: en lugar de suponer que la regla tiene al menos tres resultados posibles, a veces asumimos que contiene al menos tres elementos y que la regla de votación es sobreyectiva , es decir , es decir. , cualquier alternativa puede ganar. La sobrejetividad 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, éste debe ser elegido. ${\ mathcal {A}}$

Histórico

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

"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 votantes".

Durante la década de 1950, Robin Farquharson publicó artículos influyentes sobre la cuestión del voto estratégico. En un artículo escrito con Michael Dummett , conjetura que las reglas de votación deterministas con al menos tres resultados posibles enfrentan un problema intrínseco con la votación estratégica. Esta conjetura de Farquharson-Dummett está probada independientemente por Allan Gibbard y Mark Satterthwaite . En un artículo de 1973, Gibbard usa el teorema de Arrow para probar el teorema que ahora lleva su nombre y luego deduce el resultado actual, que es una consecuencia inmediata. Independientemente, Satterthwaite demuestra este mismo resultado en su tesis doctoral en 1973, luego lo publica como artículo en 1975. También se basa en el teorema de Arrow , pero sin exponer la versión más general dada por el teorema de Gibbard . Posteriormente, diversos autores desarrollan variantes de la demostración, generalmente más directas y breves, ya sea para el teorema en sí, o para los corolarios y versiones debilitadas mencionadas anteriormente.

Resultados relacionados

El teorema de Gibbard nos permite considerar los mecanismos de elección colectiva que pueden ser no ordinales, es decir, donde la acción de un votante no es necesariamente proporcionar 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, donde el resultado puede depender no sólo de los boletines sino también de un elemento de azar.

El teorema de Duggan-Schwartz extiende este resultado en otra dirección, al considerar reglas de votación deterministas, pero que seleccionan un subconjunto no vacío de candidatos en lugar de solo uno.

Posteridad

El teorema de Gibbard-Satterthwaite se presenta generalmente como resultado de la aplicación de la teoría de la elección social a los sistemas electorales, pero también puede verse como el resultado fundamental de la teoría del mecanismo de incentivos , que se ocupa del diseño de métodos colectivos de toma de decisiones, que posiblemente impliquen transferencias monetarias. . Noam Nisan presenta esta relación de la siguiente manera:

"El teorema de Gibbard-Satterthwaite parece anular cualquier esperanza de diseñar funciones de elección social que induzcan a revelar las verdaderas preferencias de uno. Todo el campo disciplinario de la teoría del mecanismo de incentivos intenta escapar de este teorema de imposibilidad mediante el uso de diversas modificaciones de este modelo".

La idea principal de estas lagunas es limitarse a clases restringidas de preferencias, a diferencia del teorema de Gibbard-Satterthwaite, que permite preferencias arbitrarias. Así, en esta disciplina, a menudo se asume que los agentes tienen preferencias cuasi-lineales , lo que significa que su función de utilidad varía linealmente con respecto a la cantidad de dinero. En este caso, las transferencias de efectivo se pueden utilizar para alentarlos a actuar con sinceridad. Esta idea se explota en la subasta Vickrey-Clarke-Groves .

Notas y referencias

(en) Allan Gibbard , “ Manipulación de sistemas de votación: Un resultado general ” , Econometrica , vol. 41,1973, p. 587-601
(en) Mark Allen Satterthwaite , “ Estrategia-impermeabilidad y las condiciones de Arrow: existencia y correspondencia teoremas para los procedimientos de votación y las funciones de bienestar social ” , Journal of Economic Theory , vol. 10, n o 21975, p. 187-217 ( DOI 10.1016 / 0022-0531 (75) 90050-2 )
(en) Tjark Weber , " Alternatives vs. Resultados: Una nota sobre el teorema de Gibbard-Satterthwaite ” , Informe técnico (Biblioteca de la Universidad de Munich) ,2009( leer en línea )
(en) Philip Reny , " de Arrow y el teorema de Gibbard-Satterthwaite Teorema: Un enfoque unificado " , Economics Letters , vol. 70, n o 1,2001, p. 99–105 ( leer en línea )
(en) Jean-Pierre Benoît , “ El Gibbard-Satterthwaite Teorema: Una prueba simple ” , Economics Letters , vol. 69, n o 3,2000, p. 319 –322 ( ISSN 0165-1765 , leer en línea )
(en) Arunava Sen , " Otra prueba directa del Gibbard-Satterthwaite Teorema " , Economics Letters , vol. 70, n o 3,2001, p. 381 –385 ( ISSN 0165-1765 , leer en línea )
(en) Duncan Black , La teoría de los comités y las elecciones , Cambridge University Press,1958
"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".
(En) Robin Farquharson , " sencillez en los procedimientos de votación " , Oxford Economic Papers, New Series , vol. 8, n o 1,1956, p. 80–89 ( JSTOR 2662065 )
(en) Michael Dummett y Robin Farquharson , " Estabilidad en la votación " , Econometrica , vol. 29, n o 1,1961, p. 33–43 ( DOI 10.2307 / 1907685 , JSTOR 1907685 )
(en) Michael Dummett , " El trabajo y la vida de Robin Farquharson " , Elección social y bienestar , vol. 25, n o 22005, p. 475–483 ( DOI 10.1007 / s00355-005-0014-x , JSTOR 41106711 )
(en) Peter Gärdenfors , " Una prueba concisa del teorema que manipulamos las funciones de la elección social " , Public Choice , vol. 32,1977, p. 137-142 ( ISSN 0048-5829 , leer en línea )
(en) Salvador Barberá , " Prueba de estrategia y votantes fundamentales: una prueba directa del teorema de Gibbard-Satterthwaite " , Revista Económica Internacional , vol. 24, n o 21983, p. 413–417 ( ISSN 0020-6598 , leer en línea )
(en) Michael Dummett , Procedimientos de votación , Oxford University Press ,1984( ISBN 978-0-19-876188-4 )
(en) Rudolf Fara y Maurice Hall , " Una entrevista con Michael Dummett: De la filosofía analítica al análisis de la votación y más allá " , Social Choice and Welfare , vol. 27, n o 22006, p. 347-364 ( DOI 10.1007 / s00355-006-0128-9 , JSTOR 41106783 )
(en) Herve Moulin , Axiomas de la toma de decisiones cooperativa , Cambridge University Press ,1991, 332 p. ( ISBN 978-0-521-42458-5 , leer en línea )
(en-GB) Alan D. Taylor , " La manipulabilidad de los sistemas de votación " , The American Mathematical Monthly , vol. 109,Abril de 2002, p. 321–337 ( DOI 10.2307 / 2695497 , JSTOR 2695497 )
(en) John Duggan y Thomas Schwartz , " Manipulabilidad estratégica sin determinación o creencias compartidas: Gibbard-Satterthwaite generalizado " , Elección social y bienestar , vol. 17, n o 1,2000, p. 85–93 ( ISSN 0176-1714 , leer en línea )
(en) Vijay Vazirani Noam Nisan , Tim Roughgarden y Éva Tardos , Teoría de juegos algorítmicos , Cambridge, Reino Unido, Cambridge University Press ,2007, 754 p. ( ISBN 978-0-521-87282-9 y 0-521-87282-0 ) , pág. 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 este resultado de imposibilidad utilizando varias modificaciones en el modelo".