Teorema de Gibbard

O teorema de Gibbard é um resultado fundamental da teoria dos jogos que mostra que não existe um mecanismo universal não ditatorial. Ele afirma que, para qualquer forma de jogo (ou mecanismo) na qual os jogadores podem ter qualquer conjunto de preferências, pelo menos uma das seguintes condições deve valer:

  1. O mecanismo é uma ditadura: um único jogador sempre dita o resultado.
  2. O mecanismo é um duplo: há apenas dois resultados possíveis.
  3. O mecanismo não é direto: a ação ótima para um eleitor requer comportamento estratégico, ou seja, depende de suas crenças sobre os outros jogadores.

Um corolário deste teorema é o teorema de Gibbard–Satterthwaite sobre regras de votação. A principal diferença entre os dois teoremas é que Gibbard–Satterthwaite se aplica apenas à votação por ordem de preferência. Devido ao seu escopo mais amplo, o teorema de Gibbard não faz nenhuma afirmação sobre se os eleitores precisam inverter sua ordenação de candidatos, apenas que suas cédulas ótimas dependem das cédulas dos outros eleitores.

O teorema de Gibbard é mais geral e considera processos de decisão coletiva que podem não ser ordinais: por exemplo, sistemas de votação em que os eleitores atribuem notas ou de outra forma avaliam os candidatos (votação cardinal). O teorema de Gibbard pode ser provado usando o teorema da impossibilidade de Arrow.[carece de fontes]?

O teorema de Gibbard é ele próprio generalizado pelo teorema de Gibbard de 1978 e pelo teorema de Hylland, que estendem esses resultados a processos não determinísticos, ou seja, onde o resultado pode não depender apenas das ações dos agentes, mas também envolver um elemento de acaso.

Visão geral

Considere alguns eleitores , e que desejam selecionar uma opção entre três alternativas: , e . Suponha que eles usem a votação por aprovação: cada eleitor atribui a cada candidato a nota 1 (aprovação) ou 0 (sem aprovação). Por exemplo, é uma cédula autorizada: significa que o eleitor aprova os candidatos e , mas não aprova o candidato . Uma vez coletadas as cédulas, o candidato com maior nota total é declarado vencedor. Empates entre candidatos são desfeitos por ordem alfabética: por exemplo, se há um empate entre os candidatos e , então vence.

Suponha que o eleitor prefira a alternativa , depois e depois . Qual cédula defenderá melhor suas opiniões? Por exemplo, considere as duas situações a seguir.

Resumindo, o eleitor enfrenta um dilema de voto estratégico: dependendo das cédulas que os outros eleitores irão depositar, ou pode ser uma cédula que melhor defende suas opiniões. Dizemos então que a votação por aprovação não é à prova de estratégia: uma vez que o eleitor identificou suas próprias preferências, ela não tem à sua disposição uma cédula que melhor defenda suas opiniões em todas as situações; ela precisa agir estrategicamente, possivelmente espionando os outros eleitores para determinar como pretendem votar.

O teorema de Gibbard afirma que um processo determinístico de decisão coletiva não pode ser à prova de estratégia, exceto possivelmente em dois casos: se há um agente distinto que tem poder ditatorial (unilateral), ou se o processo limita o resultado a apenas duas opções possíveis (duplo).

Enunciado formal

Seja o conjunto de alternativas, que também podem ser chamadas de candidatos em um contexto de votação. Seja o conjunto de agentes, que também podem ser chamados de jogadores ou eleitores, dependendo do contexto de aplicação. Para cada agente , seja um conjunto que representa as estratégias disponíveis para o agente ; assuma que é finito. Seja uma função que, para cada -tupla de estratégias , mapeia uma alternativa. A função é chamada de forma de jogo. Em outras palavras, uma forma de jogo é essencialmente definida como um jogo de n jogadores, mas sem utilidades associadas aos resultados possíveis: ela descreve apenas o procedimento, sem especificar a priori o ganho que cada agente obteria de cada resultado.

Dizemos que é à prova de estratégia (originalmente chamada: direta) se, para qualquer agente e qualquer ordem fraca estrita sobre as alternativas, existe uma estratégia que é dominante para o agente quando ela tem preferências : não há perfil de estratégias para os outros agentes tal que outra estratégia , diferente de , levaria a um resultado estritamente melhor (no sentido de ). Essa propriedade é desejável para um processo de decisão democrático: significa que, uma vez que o agente identificou suas próprias preferências , ela pode escolher uma estratégia que melhor defende suas preferências, sem necessidade de conhecer ou adivinhar as estratégias escolhidas pelos outros agentes.

Seja e denote por o contradomínio de , ou seja, o conjunto dos resultados possíveis da forma de jogo. Por exemplo, dizemos que tem pelo menos 3 resultados possíveis se e somente se a cardinalidade de é 3 ou mais. Como os conjuntos de estratégias são finitos, também é finito; assim, mesmo que o conjunto de alternativas não seja assumido como finito, o subconjunto de resultados possíveis é necessariamente finito.

Dizemos que é ditatorial se existe um agente que é um ditador, no sentido de que, para qualquer resultado possível , o agente tem uma estratégia à sua disposição que garante que o resultado seja , quaisquer que sejam as estratégias escolhidas pelos outros agentes.

Teorema de Gibbard — Se uma forma de jogo não é ditatorial e tem pelo menos 3 resultados possíveis, então ela não é à prova de estratégia.

Exemplos

Ditadura serial

Assumimos que cada eleitor comunica uma ordem fraca estrita sobre os candidatos. A ditadura serial é definida como segue. Se o eleitor 1 tem um único candidato mais preferido, então esse candidato é eleito. Caso contrário, os resultados possíveis são restritos aos seus candidatos igualmente mais preferidos e os outros candidatos são eliminados. Então, a cédula do eleitor 2 é examinada: se ele tem um único candidato mais preferido entre os não eliminados, então esse candidato é eleito. Caso contrário, a lista de resultados possíveis é reduzida novamente, etc. Se ainda houver vários candidatos não eliminados após todas as cédulas terem sido examinadas, então uma regra de desempate arbitrária é usada.

Essa forma de jogo é à prova de estratégia: quaisquer que sejam as preferências de um eleitor, ele tem uma estratégia dominante que consiste em declarar sua ordem de preferência sincera. Ela também é ditatorial, e seu ditador é o eleitor 1: se ele deseja ver o candidato eleito, então ele só precisa comunicar uma ordem de preferência na qual é o único candidato mais preferido.

Votação por maioria simples

Se há apenas 2 resultados possíveis, uma forma de jogo pode ser à prova de estratégia e não ditatorial. Por exemplo, é o caso da votação por maioria simples: cada eleitor vota em sua alternativa mais preferida (entre os dois resultados possíveis), e a alternativa com mais votos é declarada vencedora. Essa forma de jogo é à prova de estratégia porque é sempre ótimo votar em sua alternativa mais preferida (a menos que se seja indiferente entre elas). No entanto, é claramente não ditatorial. Muitas outras formas de jogo são à prova de estratégia e não ditatoriais: por exemplo, assuma que a alternativa vence se obtiver dois terços dos votos, e vence caso contrário.

Uma forma de jogo mostrando que a recíproca não vale

Considere a seguinte forma de jogo. O eleitor 1 pode votar em um candidato de sua escolha, ou pode se abster. No primeiro caso, o candidato especificado é automaticamente eleito. Caso contrário, os outros eleitores usam uma regra de votação clássica, por exemplo a contagem de Borda. Essa forma de jogo é claramente ditatorial, porque o eleitor 1 pode impor o resultado. No entanto, ela não é à prova de estratégia: os outros eleitores enfrentam o mesmo problema de voto estratégico que na contagem de Borda usual. Assim, o teorema de Gibbard é uma implicação e não uma equivalência.

Extensões

O teorema de Gibbard de 1978 afirma que um método de votação não determinístico só é à prova de estratégia se for uma mistura de regras unilaterais e duplas. Por exemplo, a regra que joga uma moeda e escolhe um ditador aleatório se a moeda der cara, ou escolhe o vencedor do confronto direto entre dois candidatos aleatórios se a moeda der coroa, é à prova de estratégia. Métodos não determinísticos foram concebidos que aproximam os resultados de métodos determinísticos enquanto são à prova de estratégia.

Ver também