Teorema de Gibbard

Ajustar Compartir Imprimir Citar

En los campos del diseño de mecanismos y la teoría de la elección social, el teorema de Gibbard es un resultado probado por el filósofo Allan Gibbard en 1973. Establece que para cualquier proceso determinista de decisión colectiva, al menos una de las siguientes tres propiedades debe cumplirse:

El proceso es dictatorial, es decir, existe un agente distinguido que puede imponer el resultado;
El proceso limita los posibles resultados a solo dos opciones;
El proceso está abierto a la votación estratégica: una vez que un agente ha identificado sus preferencias, es posible que no tenga ninguna acción a su disposición que defienda mejor estas preferencias independientemente de las acciones de los otros agentes.

Un corolario de este teorema es el teorema de Gibbard-Satterthwaite sobre las reglas de votación. La principal diferencia entre los dos es que el teorema de Gibbard-Satterthwaite se limita a las reglas de votación clasificadas (ordinales): la acción de un votante consiste en otorgar una clasificación de preferencia sobre las opciones disponibles. El teorema de Gibbard es más general y considera procesos de decisión colectiva que pueden no ser ordinales: por ejemplo, sistemas de votación donde los votantes asignan grados a los candidatos. El teorema de Gibbard se puede probar usando el teorema de imposibilidad de Arrow.

El teorema de Gibbard es generalizado por el teorema de Gibbard de 1978 y el teorema de Hylland, que extienden estos resultados a procesos no deterministas, es decir, donde el resultado no solo puede depender de las acciones de los agentes, sino que también puede involucrar un elemento de azar.

Visión de conjunto

Considere algunos votantes $1$ , $2$ y $3$ que deseen seleccionar una opción entre tres alternativas: $un$ , $b$ y $C$ . Supongamos que utilizan la votación de aprobación: cada votante asigna a cada candidato el grado 1 (aprobación) o 0 (rechazar la aprobación). Por ejemplo, $(1, 1, 0)$ es una papeleta autorizada: significa que el elector aprueba candidatos $un$ y $b$ no aprueba candidatos $C$ . Una vez recolectadas las papeletas, se declara ganador al candidato con la calificación total más alta. Los empates entre candidatos se rompen por orden alfabético: por ejemplo, si hay empate entre candidatos $un$ y $b$ , entonces $un$ gana.

Suponga que el votante $1$ prefiere la alternativa $un$ , luego $b$ y luego $C$ . ¿Qué boleta defenderá mejor sus opiniones? Por ejemplo, considere las dos situaciones siguientes.

Si los otros dos votantes emitieron sus votos respectivamente ${ estilo de visualización (0,1,1)}$ y $(1, 1, 1)$ , entonces el votante $1$ tiene solo una boleta que conduce a la elección de su alternativa favorita $un$ : $(1,0,0)$ .
Sin embargo, si asumimos en cambio que los otros dos votantes emitieron sus votos respectivamente $(0,0,1)$ , ${ estilo de visualización (0,1,1)}$ entonces el votante $1$ no debería votar $(1,0,0)$ porque hace que $C$ gane; ella debería más bien votar $(1, 1, 0)$ , lo que hace que $b$ gane.

En resumen, el votante $1$ se enfrenta a un dilema estratégico de votación: dependiendo de las papeletas que emitan los demás votantes, $(1,0,0)$ o $(1, 1, 0)$ puede ser una papeleta la que mejor defienda sus opiniones. Entonces decimos que el voto de aprobación no es a prueba de estrategias: una vez que el votante ha identificado sus propias preferencias, no tiene a su disposición una papeleta que defienda mejor sus opiniones en todas las situaciones; necesita actuar estratégicamente, posiblemente espiando a los demás votantes para determinar cómo piensan votar.

El teorema de Gibbard establece que un proceso determinista de decisión colectiva no puede ser a prueba de estrategias, excepto posiblemente en dos casos: si hay un agente distinguido que tiene un poder dictatorial, o si el proceso limita el resultado a solo dos opciones posibles.

Declaración formal

Sea ${ matemáticas {A}}$ el conjunto de alternativas, que también pueden llamarse candidatos en un contexto de votación. Sea ${displaystyle {mathcal {N}}={1,ldots,n}}$ el conjunto de agentes, que también pueden llamarse jugadores o votantes, según el contexto de aplicación. Para cada agente $i$ , ${displaystyle {mathcal {S}}_{i}}$ sea un conjunto que represente las estrategias disponibles para el agente $i$ ; supongamos que ${displaystyle {mathcal {S}}_{i}}$ es finito. Sea $gramo$ una función que, a cada $norte$ -tupla de estrategias ${displaystyle (s_{1},ldots,s_{n})in {mathcal {S}}_{1}times cdots times {mathcal {S}}_{n}}$ , mapea una alternativa. La función $gramo$ se llama forma de juego. En otras palabras, una forma de juego se define esencialmente como un n-juego de jugadores, pero sin utilidades asociadas a los posibles resultados: describe únicamente el procedimiento, sin especificar a priori la ganancia que cada agente obtendría de cada resultado.

Decimos que $gramo$ es a prueba de estrategia (originalmente llamado: sencillo) si para cualquier agente $i$ y para cualquier orden débil estricto $Pi}$ sobre las alternativas, existe una estrategia ${displaystyle s_{i}^{*}(P_{i})}$ que es dominante para el agente $i$ cuando tiene preferencias $Pi}$ : no hay un perfil de estrategias para los otros agentes tales que otra estrategia $si}$ , diferente de ${displaystyle s_{i}^{*}(P_{i})}$ , conduciría a un resultado estrictamente mejor (en el sentido de $Pi}$ ). Esta propiedad es deseable para un proceso de decisión democrático: significa que una vez que el agente $i$ ha identificado sus propias preferencias $Pi}$ , puede elegir una estrategia ${displaystyle s_{i}^{*}(P_{i})}$ que mejor defienda sus preferencias, sin necesidad de conocer o adivinar las estrategias elegidas por los demás agentes.

Dejamos ${displaystyle {mathcal {S}}={mathcal {S}}_{1}times cdots times {mathcal {S}}_{n}}$ y denotamos por ${displaystyle g({mathcal {S}})}$ el rango de $gramo$ , es decir, el conjunto de los posibles resultados de la forma de juego. Por ejemplo, decimos que $gramo$ tiene al menos 3 resultados posibles si y solo si la cardinalidad de ${displaystyle g({mathcal {S}})}$ es 3 o más. Dado que los conjuntos de estrategias son finitos, ${displaystyle g({mathcal {S}})}$ también es finito; por lo tanto, incluso si no se supone que el conjunto de alternativas ${ matemáticas {A}}$ es finito, el subconjunto de resultados posibles ${displaystyle g({mathcal {S}})}$ lo es necesariamente.

Decimos que $gramo$ es dictatorial si existe un agente $i$ que es un dictador, en el sentido de que para cualquier resultado posible ${displaystyle ain g({mathcal {S}})}$ , el agente $i$ tiene a su disposición una estrategia que asegura que el resultado sea $un$ cualquiera que sean las estrategias elegidas por los demás agentes.

Teorema de Gibbard : si una forma de juego no es dictatorial y tiene al menos 3 resultados posibles, entonces no es a prueba de estrategias.

Ejemplos

Dictadura en serie

Suponemos que cada votante comunica un estricto orden débil sobre los candidatos. 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 posibles resultados se restringen a sus candidatos ex-aequo más queridos y los demás candidatos son eliminados. Luego se examina la boleta del votante 2: si tiene un único candidato que más le gusta 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 forma de juego es a prueba de estrategias: sean cuales sean las preferencias de un votante, tiene una estrategia dominante que consiste en declarar su orden de preferencia sincero. También es dictatorial, y su dictador es el votante 1: si quiere ver $un$ elegido candidato, entonces solo tiene que comunicar un orden de preferencia donde $un$ está el único candidato que más gusta.

Voto por mayoría simple

Si solo hay 2 resultados posibles, una forma de juego puede ser a prueba de estrategias y no dictatorial. Por ejemplo, es el caso del voto de mayoría simple: cada votante emite su voto por la alternativa que más le gusta (entre los dos posibles resultados), y la alternativa con más votos es declarada ganadora. Esta forma de juego es a prueba de estrategia porque siempre es óptimo votar por la alternativa que más le gusta (a menos que uno sea indiferente entre ellos). Sin embargo, claramente no es dictatorial. Muchas otras formas de juego son a prueba de estrategias y no dictatoriales: por ejemplo, suponga que la alternativa $un$ gana si obtiene dos tercios de los votos y $b$ gana en caso contrario.

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

Considere la siguiente forma de juego. El votante 1 puede votar por un candidato de su elección o puede abstenerse. En el primer caso, el candidato especificado es elegido automáticamente. De lo contrario, los demás votantes utilizan una regla de votación clásica, por ejemplo, el conteo de Borda. Esta forma de juego es claramente dictatorial, porque el votante 1 puede imponer el resultado. Sin embargo, no es a prueba de estrategias: los demás votantes enfrentan el mismo problema de votación estratégica que en el conteo habitual de Borda. Así, el teorema de Gibbard es una implicación y no una equivalencia.