preâmbulo: retorno sobre a eleição presidencial francesa

em 6 de maio, François Hollande foi eleito presidente da República Francesa. Para nossos leitores estrangeiros, vamos recordar primeiro como uma eleição presidencial funciona na França. Um pequeno número de candidatos (10 neste caso) de várias arestas políticas foi previamente selecionado por funcionários eleitos locais, um prossegue uns com os outros para uma eleição de duas torre. Em tal votação, é organizada uma primeira rodada de votação em que cada eleitor deve escolher um dos candidatos (ou abster-se). Se um dos candidatos recebe a maioria absoluta dos votos expressos (que é raro na prática), este candidato é declarado vencedor. Caso contrário, segue-se para uma segunda rodada de votação em que os dois candidatos que receberam mais votos na primeira rodada competem em face a face; O candidato que recebe mais votação na segunda rodada é então declarado o vencedor.

Lembre-nos também quais foram os resultados da eleição de 2012. Para simplificar a apresentação, apenas manteremos os cinco principais candidatos ( Que às vezes nos resumiremos pela sua inicial), nomeadamente François Bayrou (B), François Hollande (H), Marine Le Pen (L), Jean-Luc Mélenchon (m) e Nicolas Sarkozy (s). Os resultados da primeira rodada foram os seguintes:

  1. holland (31%)
  2. sarkozy (28%)
  3. le caneta (19%)
  4. mélenchon (13%)
  5. BayRou (9%)

nenhum dos candidatos tendo ultrapassado 50% dos votos, há tinha uma segunda rodada contra a Holanda para Sarkozy, cujos resultados foram:

  1. holland (52%)
  2. sarkozy (48%)

JPEG - 32,4 KBFrançois Hollande Hollande, o candidato eleito pelo povo.

No final, foi Holanda que foi eleito presidente.

Vamos ser um pouco mais curioso, e perguntar o que poderia ter sido os resultados das outras faces face a faces. Além da segunda rodada H – s que realizou, na verdade, teria havido 9 outras possibilidades: B – H, B – L, B – M, B – S, H – L, H – M, L – M, L – S e M – S. Obviamente, nunca saberemos com certeza o que essas segundas torres fictícias teriam dado; No entanto, a fim de acreditar nos institutos de pesquisa, os resultados teriam sido praticamente do seguinte modo:

  • Bayrou bat holland 51 – 49;
  • bayrou bate a caneta 74 – 26;
  • BayRou Bat Mélenchon 75 – 25;
  • BayRou Bat Sarkozy 55 – 45;
  • holland bate le caneta 65 – 35;
  • holland morcego mélenchon 80 – 20;
  • le caneta morcego mélenchon 53 – 47;
  • le caneta é espancado por Sarkozy 32 – 68;
  • mélenchon é batido por Sarkozy 36 – 64.

Sintetizamos tudo isso sob a forma do “diagrama de preferência binária” abaixo, onde:

  • cada candidato é representado por uma posição separada;
  • entre cada par de candidatos, há uma seta apontando para a das duas que seriam com vista para o rosto a cara (negligenciamos a possibilidade de um ex); / li>
  • em cada flecha, indicamos a pontuação (em porcentagem) pelo qual o vencedor do rosto a cara em questão ganha.

Diagrama de preferências binárias para a eleição presidencial

O que eles poderiam ter dado as segundas torres imagináveis entre os cinco principais candidatos na eleição presidencial francês de 2012 ( As setas apontam para os vencedores).

JPEG - 28.4 KB François Bayrou Bayrou, o candidato querido pelo povo?

Achando greves: François Bayrou teria derrotado qualquer um de seus oponentes na segunda rodada! Como, na situação histórica, não foi qualificado, obviamente não foi eleito, mas vários editoriais enfatizaram que havia uma forma de paradoxo … não seria lógico, de fato, um candidato geralmente preferido a qualquer outro ser considerado O favorito de tudo?

Filosofia do critério Condorcet

Demonstração do critério

JPEG - 42.3 KO Nicolas de Condorcet Retrato de Condorcet Nicolas por Jean-Baptiste Greuze.

Foi em qualquer caso a opinião de Nicolas de Condorcet, estudioso francês do século XVIII, que foi um dos pioneiros do estudo matemático da democracia. Ele introduziu as seguintes definições (que nos adaptamos na linguagem moderna):

Definições (Vencedor do Condorcet; Critério Condorcet)

Se, entre os candidatos para uma eleição, há um que, enfrentado a qualquer Outro, é preferido pela maioria dos eleitores, então este candidato é chamado de vencedor do Condorcet.

Diz-se que um método eleitoral satisfaz o critério de concorceto quando, quando há um vencedor do Condorcet, é sempre ele que este método declara o vencedor (desde que os eleitores tenham votado de acordo com suas genuínas preferências ).

Primeiro de tudo, uma auditoria é necessária: estamos falando sobre o vencedor do Condorcet como se ele fosse único, mas é esse o caso? A resposta é “sim”:

Teorema (exclusividade do vencedor do Condorcet)

Não pode haver mais do que um vencedor do Condorcet com uma eleição.

Demonstração

Imagine uma situação em que haveria dois vencedores de Condorcet (pelo menos), chamados X e Y. Desde X é um vencedor do Condorcet, ele supera as importações de seus concorrentes na frente -Face-a-face, por isso, especialmente Y. Mas do mesmo, já que há um vencedor do condutor, ele deve derrotar x cara a cara … ou o rosto a cara entre x e y pode, obviamente, ter apenas Um vencedor: então é realmente impossível que haja mais de um vencedor de Condorcet.

A tese de Condorcet foi que, para um método eleitoral ser realmente justo, deve satisfazer o critério epônimo. Deixe-nos citar o grande homem:

Pode resultar do modo de votar nas eleições ordinárias Uma decisão realmente contrária à pluralidade. Assim, deve-se substituir nesta forma aquele em que cada voto, expressando a ordem segundo a qual coloca os candidatos, pronunciaria tanto a respectiva preferência que ela lhes dá. Quando você quer escolher o candidato mais digno, ele será suficiente que o sistema não implique a contradição pelo candidato que merece preferência em todos.

Condorcet, portanto, se oporia ao nosso método não conconcial com duas voltas, uma vez que o exemplo de BayRou mostra que não satisfaz seu critério! Mas antes de ir além, deve ser explicado quais são as justificativas teóricas sobre a tese de Condorcet.

Justificação Matemática do Critério Condorcet

Se você ler meu artigo anterior, você provavelmente se lembra Que um grande problema da teoria matemática das eleições é o seguinte: os eleitores às vezes têm interesse em “votação estratégica” expressando uma falsa opinião que traria o resultado do voto para ser melhor para eles do que o. O que teria dado sincero Sufrágio! No caso do voto não conconconco com duas torres, estávamos falando no preâmbulo, um exemplo típico é o que é chamado de “votação útil”. Imagine e no dia anterior às primeiras pesquisas da primeira rodada dão a Sarkozy longe da liderança, seguido pela caneta e na Holanda para o cotovelo-a-cotovelo, e muito mais longe, Mélenchon. Considere um eleitor fictício que é um grande fãs de Mélenchon, é misturado na Holanda, não gosta de Sarkozy e odeia a caneta. Este eleitor diz: “Se eu votar Mélenchon, não será suficiente para qualificar para a segunda rodada de qualquer maneira; Por outro lado, corro o risco de ver uma segunda rodada entre os dois candidatos que eu gosto menos. Por outro lado, votando a Holanda, diminui as chances de uma segunda rodada Sarkozy – Le Pen e promovo a eliminação do meu odiado candidato! Então, tenho interesse em votar Holland “.

Mas quando levamos em conta este fenômeno de votação estratégico, o vencedor do Condor (se houver um) pode providenciar para ser eleito com certeza! (Em qualquer caso em O método não conconcelional com duas rodadas).
de fato, imagine que há um vencedor do Condorcet chamado X, e supor as pesquisas prever a vitória de outro candidato. Como X é um vencedor do Condorcet, há uma maioria dos eleitores que preferem Para Y. Esta maioria pode então consultar e dizer “Vamos voltar a votos para X da primeira rodada; Então ele terá a maioria dos votos em seu nome e será eleito, o que mais interessante para nós! “Claro, isso não significa que todos os eleitores dessa maioria tenham x para o candidato preferido. Pode-se imaginar que um número substancial deles prefere um terceiro candidato Z, e pode ser tentado a ganhar z com a ajuda de Os velhos eleitores que também preferem z a x … mas dificilmente é perdido, porque X sendo um vencedor do Condorcet, há também a maioria (mas não composta dos mesmos eleitores, é claro) que prefere X a Z; se Z se tornar z Muito perigosas nas pesquisas, é a maioria que vai então ligore para votar x para evitar a eleição de z!

Então, um método satisfatório O critério condorceto tem isso vantajoso que os eleitores não têm que cavar Cérebros para saber se o seu voto é bem calculado: com tal método, se houver um vencedor do Condorcet, ele será necessariamente eleito!

Outra qualidade dos métodos que satisfazem o critério condorceto é o seguinte: enquanto métodos convencionais (incluindo métodos A, B, C, D e e do artigo anterior) estão sujeitos a um fenômeno de “vozes de espalhamento” quando o número de candidatos se torna grande, fenômeno que pode levar a um resultado irrelevante, o resultado de um método que satisfaz o critério do Condorcet não muda quando retiramos ou adicionamos “Pequenos” candidatos:

teorema (indiferença a pequenos candidatos)

  1. se começarmos a partir de uma situação em que um candidato é conquistado Condorcet, e um ou mais dos outros candidatos se retiram do Eleição, então o vencedor do Condorcet inicial permanece vencedor do Condorcet após esta retirada.
  2. vice-versa, se compartilharmos uma situação em que um candidato é conquistador de Condorcet, e um ou mais novos candidatos são introduzidos a cada dos quais o. E o vencedor inicial é preferido face a face, então o vencedor do Condorcet inicial permanece ao Condorcet vencedor após esta adição.

demonstração

A retirada ou adição de um candidato não altera as preferências binárias dos eleitores entre os outros candidatos. Pois ponto I, já que nosso vencedor inicial do condutor inicialmente bateu todos os seus oponentes no rosto a cara, de modo que continua sendo o caso se um ou mais de seus adversários se retiram. Para o ponto II, nosso vencedor inicial do Condorcet continua a bater todos os seus adversários iniciais, e assumimos que ele também estava batendo em seus novos oponentes, para que ele seja sempre vencedor do Condorcet na nova situação.

nota por outro lado, se o vencedor do prospectivo Condorcet é em um sentido um vencedor inevitável, é como não necessariamente aquele que é realmente o favorito das pessoas (no sentido de que tínhamos mencionado No artigo anterior, isto é, medindo a total felicidade que esse candidato traria ao público se eleito). Assim, se houver apenas dois candidatos x e y, e que 51% dos eleitores preferem um pouco X para Y e 49% dos eleitores preferem muito em grande parte Y para X, é x que será eleito quando queremos dizer que é bastante onde representa a vontade das pessoas. Dito isto, este fenômeno de “ditadura majoritária” é diretamente relacionado ao critério condutor: é de fato um vício inerente à democracia, como já incluído Kant.

No momento, conversamos muito sobre filosofia e poucas matemáticas (e até menos pesquisas!). Mas esta introdução foi necessária para entender por que o critério condorcet é um objeto matemático natural e importante. Na segunda parte deste artigo, agora falaremos sobre pesquisas muito mais recentes que giram em torno desse critério.

O paradoxo do condutor realmente existe?

o paradoxo do condutor

O critério Condorcet naturalmente nos leva a falar sobre o paradoxo do Condorcet, que já encontramos no artigo anterior. Este paradoxo afirma em substância que não há necessariamente um vencedor do condutor:

Paradox Condorcet (1785)

Assim que houver pelo menos 3 candidatos , há situações em que não há vencedor do Condorcet.

demonstração

Suponha que existam pelo menos 3 candidatos e escolha três candidatos específicos entre Eles, chamados X, Y e Z. Nós imaginamos que todos os eleitores preferem X, Y e Z a todos os outros candidatos, para que nenhum desses outros candidatos não possa ser conquistador de Condorcet. Agora podemos imaginar ainda que 40% dos eleitores tenham a ordem de preferência “x então y então z”, 35% “y então z então x” e 25% “z e depois x”. Em seguida, 65% dos eleitores preferem x para y (por isso não há um vencedor do Condorcet), 75% preferem Y para Z (então Z não é um vencedor do Condorcet), e 60% preferem Z para X (assim x não é um condutor Vencedor): Nenhum candidato é, portanto, conquistador de Condorcet.

No entanto, vimos no preâmbulo um caso de real eleição sem menos de 5 candidatos em que há de fato um vencedor do condutor! Isso sugere que poderia existir um fenômeno que proibia o paradoxo do condutor na prática, porque situações políticas realistas verificariam algumas suposições específicas sob as quais O paradoxo é impossível. Nos parágrafos seguintes, apresentaremos diferentes modelos de preferências políticas e veremos se permitem ou não a ocorrência do paradoxo do Condorcet.

paradoxo condorceto em um tabuleiro político

Vamos apresentar aqui uma modelagem bastante realista das preferências políticas dos eleitores, chamaremos de modelagem pelo tabuleiro de xadrez político, cuja ideia é simplesmente em geral, Estamos votando para o candidato cujas posições caem tanto quanto nossas opiniões. Será assumido que haverá um “tabuleiro de xadrez político” abstrato (que possibilita falar de “distância política”) na qual os candidatos podem ser colocados, assim como os eleitores, como as preferências de cada eleitor são candidatos que é o mais próximo de um mais distante.

Alguém poderia esperar que, com tal modelagem, nunca há um paradoxo de Condorcet … mas este não é o caso! Suponha que o tabuleiro de xadrez político corresponda a um verdadeiro tabuleiro de xadrez (cujas caixas medem, digamos, 5 cm de lado), onde um coloca um candidato x na caixa B7, um candidato y na caixa F7, um candidato c2 e um candidato C2 . Imaginamos que o eleitorado é dividido em quatro grupos de vários tamanhos, cada um deles tem exatamente a mesma posição que um dos candidatos:
34% dos eleitores estão no nível de X, 26% no nível de Y , 18% de z e 22% W. As distâncias entre os candidatos são então indicadas no desenho abaixo, de modo que as seguintes preferências para os eleitores (“X > Y” Significado “x é preferível a y “):

o exemplo do tabuleiro de xadrez

qui, à esquerda, um político Configuração de tabuleiro de xadrez De modo que, se houver 34% dos eleitores em X, 26% em Y, 18% em z e 22% em W, e que cada eleitor prefere os candidatos dos quais é mais próximo, então nenhum candidato é o condutor Vencedor: à direita, o diagrama de preferência binária correspondente.

  • x > y > z > w para 34% das eleições Rs;
  • y > z > x > w para 26% dos eleitores;
  • w > z > x > Por 22% dos eleitores;
  • z > w > y > x para 18% dos eleitores.

Então, nesta configuração, x não é um vencedor do Condorcet (porque ele é espancado por Z em 66%) nem y (batido por x a 56%), nem z (espancado por Y para 60%), nem W (batido por Z em 78%): por isso temos paradoxo de Condorcet!

os teoremas do eleitor mediano

No exemplo do tabuleiro de xadrez, fizemos um estágio político de dimensão 2, isto é, com 2 coordenadas (uma para as colunas e uma para as linhas). Não foi uma coincidência! Porque se o tabuleiro de xadrez político tiver apenas uma dimensão, pode-se demonstrar que ainda há um vencedor de Condorcet:

Teorema (primeiro o teorema do eleitor mediano; preto 1958)

quando o tabuleiro de xadrez político é um eixo graduado (que geralmente interpretamos como um posicionamento político da “mais esquerda” para o “mais direito”), há sempre um vencedor do Condorcet.

para demonstrar este teorema, nós primeiro introduzirá uma definição que será útil para nós na prova:

Definição (perfil de preferência em λ)

Dizem que um eleitor em um perfil de preferências em λ (ler “lambda” ) Quando, quando alguém viaja a lista de candidatos da esquerda para a direita para a direita, a preferência deste eleitor sobe até chegar ao seu candidato favorito e desce. (Possivelmente, o candidato preferido pode ser o mais à esquerda ou a direita à direita de tudo; o importante nunca é voltar depois de descer).

Por exemplo, se assumirmos que os candidatos do presidencial Eleitoral fileiras da esquerda para a direita de acordo com a ordem “M, H, B, S, L”, depois as preferências “B > h > s > o > m “ou” l > s > b > h > m “são perfis em λ, mas não” h > m > s > b > L, já que tal Uma preferência cai entre H e B antes de subir entre B e S.

Demonstração do primeiro teorema do eleitor mediano

o primeiro ponto é para observar que, quando o tabuleiro de xadrez político é um eixo graduado, todos os eleitores têm um PR Ofil de preferência em λ. De fato, considere qualquer eleitor.Quando passamos pelo tabuleiro político da esquerda para a direita, começamos aproximando-se deste eleitor antes de se afastar, para que as preferências do eleitor aumentem (contanto que fôssemos à esquerda do que este eleitor) antes de descer (uma vez que somos mais direito): Isso corresponde a um perfil de preferência em λ. (Se nenhum candidato estiver localizado exatamente da mesma posição que o eleitor, será necessário olhar para as distâncias precisas para saber se o candidato favorito deste eleitor é o imediatamente localizado à sua esquerda ou imediatamente à direita, mas no Dois casos, temos um perfil em λ).

Nós agora provamos o teorema. Para evitar os problemas de correr, suponha que haja um número ímpar de eleitores. Cada um desses eleitores tem um candidato favorito. Imagine que pedimos a cada eleitor para escrever o nome de seu candidato favorito em uma newsletter e classifica os boletins obtidos a partir do candidato mais esquerdo para o candidato mais à direita, e vamos chamar x o candidato que está no boletim candidato localizado no meio de Este ranking. Eu afirmo que x é um vencedor do Condorcet. De fato, considere um candidato localizado, por exemplo, mais direito do que X (para um candidato à esquerda, seria suficiente para inverter “direito” e “esquerda” no resto). Como X está no meio da nossa classificação de boletins, há uma maioria absoluta de boletins informativos que são em nome de X ou um candidato mais esquerdo do que X, o que significa que há uma maioria absoluta dos eleitores cujo candidato preferido é X , ou um candidato localizado mais à esquerda do que X. Então considere esse eleitor, do qual chamamos Z o candidato preferido (Z que pode ser o mesmo que X). Sabemos através do parágrafo acima que nosso eleitor tem um perfil de preferências em λ, então quando se afasta da Z para a direita, as preferências do eleitor só diminuem. Mas aqui x é pelo menos tão certo quanto z e y é ainda mais direito que x, então vamos atravessar mais tarde para x durante esse afastamento; Portanto, nosso eleitor prefere X a Y. Como é o mesmo para uma maioria absoluta dos eleitores, significa que X é predominantemente preferido a y, e como podemos fazer o mesmo raciocínio para todos possíveis lá, isso prova que X é um condutor vencedor. Observe que esta demonstração mostra que o teorema permanece válido assim que todos os eleitores têm um perfil de preferências em λ.

a falta Deste primeiro teorema do eleitor mediano (e modelagem de xadrez político em geral) é que ele considera que a única qualidade dos candidatos que interessam aos eleitores é seu posicionamento político. No entanto, com posição política igual, alguns candidatos podem ser “melhores” ou “pior”, por exemplo, por causa de suas qualidades intelectuais ou carismáticas. Um modelo mais fino é, portanto, o seguinte: Por um lado, há um eixo graduado no qual os candidatos e os eleitores são colocados, e por outro lado também estão associados a cada candidato “valor intrínseco”. Cada eleitor calcula então para os vários candidatos uma “pontuação” igual ao valor intrínseco do candidato menos a distância do candidato e classificou os candidatos por escore descendente: um exemplo é fornecido no desenho abaixo.

Eixo político com valores intrínsecos

Aqui está um exemplo levando em conta tanto a colocação de candidatos no eixo político “esquerda – direita” e o valor intrínseco dos candidatos. Neste exemplo, existem cinco candidatos manchados por pontos, o valor intrínseco de cada um deles sendo indicado entre parênteses. Se considerarmos um eleitor localizado na posição “E”, este eleitor dá uma pontuação igual a 9 (valor) – 5 (distância) = 4, a uma pontuação de 8 – 1 = 7, a B uma pontuação de 5 – 1 = 4, e dos mesmos para S e L dos respectivos escores de 5 e 3. Portanto, a ordem das preferências deste eleitor é “H > M > s > b > l “- que não é um perfil em λ.

Bem, neste modelo, ainda estamos assegurados da existência de um vencedor do Condorcet:

teorema (segundo teorema do eleitor mediano; Roberts 1977)

Se candidatos e eleitores forem colocados no mesmo eixo graduado, por um lado, para cada candidato estiver associado a um valor intrínseco por outro, e que as preferências de cada eleitor são determinadas pela diferença “Valor intrínseco – distância do candidato “, então há sempre um vencedor do Condorcet.

Para demonstrar este teorema, também estamos começando aqui introduzindo uma definição:

definição (preferências arquivadas)

Ser dado candidatos classificados da esquerda para a direita e Os eleitores também classificaram da esquerda para a direita, diz que a configuração das preferências é impedida se é impossível encontrar um candidato X à esquerda que outro candidato y e um eleitor tiver mais à esquerda do que outro B eleitor que prefere Y para x, mas B prefere x para y (em outras palavras, que são tal que o eleitor à esquerda prefere o candidato certo e o eleitor certo o candidato à esquerda).

Demonstração do segundo teorema do eleitor mediano

O primeiro ponto é observar que, sob as hipóteses do teorema, a configuração das preferências é privada. Considere os dois candidatos x e y, com você mais do que X. Diga que a configuração das preferências é descrita significa que, como um eleitor fictício, se move da esquerda para a direita no eixo político, ele não pode não ser uma preferência “Y > x “para uma preferência” x > y “; Para mostrar que, basta estabelecer que a diferença “pontuação de pontuação X” só pode aumentar quando vamos da esquerda para a direita. Agora, nessa diferença na pontuação, a única coisa que muda de um eleitor para outra é a parte da pontuação que depende da distância: aquela que depende da pontuação é a mesma! Então, é suficiente mostrar que a diferença “distância de y – distância de X” está apenas diminuindo quando se vai da esquerda para a direita. Então, o que acontece quando vamos da esquerda para a direita? A princípio, desde que ainda forem deixados de X, cada passo para a direita mais perto de X a partir de Y, e, portanto, a diferença “a distância até Y – distância para X” não varia. Então, quando você estiver entre X e Y, cada passo para a direita não diminui apenas a distância para Y, mas também aumenta a única a x, de modo que a diferença “distância para a distância de Y” diminui. Finalmente, além de Y, cada passo para a direita nos leva como muitos x a partir de Y, e, portanto, novamente a diferença de distâncias permanece constante. Assim, temos uma configuração de preferências desgastadas.

Agora provamos o teorema. Para evitar os problemas do ex-æquo, suponha que haja um número ímpar de eleitores. Se classificarmos esses eleitores da esquerda para a direita no eixo político, então há um que é encontrado no meio dessa classificação, que chamaremos o “Eleitor Mediano”. Eu digo que as preferências maioritárias são exatamente as mesmas que as desta mediana eleitor, e, portanto, em particular o candidato favorito do mediano eleitor é um vencedor do Condorcet. De fato, suponha que entre dois candidatos x e y, o eleitor mediano prefere x; Para corrigir as idéias, digamos que seja mais justo que X (caso contrário, inverter “direito” e “esquerda”). Assim, de acordo com o resultado intermediário acima, ainda mais sobre os eleitores esquerdos que o Eleitor Mediano também prefere X a Y, e por isso há uma maioria dos eleitores que preferem X para y, o que queríamos demonstrar. Note que esta demonstração mostra que o teorema permanece válido assim que a configuração das preferências é privada.

Além de demonstrar a existência da existência da existência da existência de A existência da existência da existência de conquistador do Condorcet, as evidências acima nos dizem o que este vencedor é: é o candidato favorito do eleitor localizado “no meio” de todos no eixo das preferências (daí o nome de “Teorema” do eleitor mediano “). Um fenômeno semelhante ocorreu para o primeiro teorema do eleitor mediano, onde o resultado da eleição correspondia à mais central escolha entre os candidatos favoritos dos vários constituintes. Uma moralidade que podemos no desenho é que o critério condorcet promove os candidatos “centristas” em comparação com os candidatos mais orientados ou extremamente Istas É comportamento desejável? As opiniões diferem nesta questão:
para alguns, promover os centristas riscos repugnantes eleitores não centristos que teriam a impressão de nunca ser levado em conta, e promover a política do consenso de MOU à custa de mais ambiciosos projetos; Outros, pelo contrário, acreditam que uma política centrista apaziaia o debate, permitindo que todos navemguem um pouco, e que grande estabilidade política seria mais propício para o estabelecimento de projetos de longo prazo..

e Quando não há vencedor do Condorcet?

Os teoremas do eleitor mediano tendem a indicar que em situações concretas, teremos a maior parte do tempo um vencedor do Condorcet, o que a história das eleições é realmente corroborando.Antecipando a modelagem puramente unidimensional em que estes descanso dos teoremas é claramente reduzindo demais, e o exemplo do tabuleiro de xadrez nos mostra que é apenas um caso mais complexo para ver reaparecer o paradoxo do Condorcet. .. em suma, Se quisermos aplicar um método eleitoral satisfazendo o critério Condorcet, será necessário dar uma regra para designar o candidato eleito quando não há vencedor do Condorcet. Mas qual ? Esta questão começou a ser estudada apenas algumas décadas, especialmente porque antes da invenção da ciência da computação, era praticamente impossível tornar a contagem de um voto, onde os eleitores indicam suas preferências entre todos os candidatos. Esta é uma pesquisa sobre este tópico que agora falaremos.

O método de mínimo

Vamos começar com uma abordagem muito simples. Pode-se dizer: “Na base, um vencedor do Condorcet é um candidato que realiza mais de 50% contra todos os outros. Se nenhum dos candidatos for bem-sucedidos, poderemos diminuir o limite de 50% para dizer:” Se houver apenas um dos candidatos que conseguem alcançar, por exemplo, 45% contra qualquer outro, então é esse candidato que deve ser eleito “”. Em outras palavras, o protocolo é o seguinte: Para cada um dos candidatos, olhamos para o pior das pontuações que ele faria em suas diferentes faces faces, então nós declaramos que os candidatos cuja pior pontuação é o melhor. Este método é chamado de método minimax, porque ela parece quem é o melhor (“max”) no Situação onde é o menos bom (“mini”).

Então, para o exemplo do tabuleiro de xadrez apresentado acima (onde não há vencedor do Condorcet), a pior derrota de X é realizada contra Z por 66 %, a pior derrota de Y contra x 56%, a pior derrota de Z contra y em 60% e a pior derrota de W contra Z 78%. A mais leve dessas piores derrotas é a de Y, que é, portanto, o vencedor mínimo.

Parece natural! Infelizmente, este método abre o caminho para uma forma de “manipulação” (pejorativa sinônima de “votação estratégica”) particularmente perigosa. Suponha que, de fato, que no exemplo do tabuleiro de xadrez previamente abordado, temos mais do que um grupo V composto de “” Anarquistas “. Estes anarquistas são relativamente numerosos, uma vez que constituem 40% da população total, para que tenhamos a seguinte distribuição global: x 20%, Y 16%, Z 11%, W 13%, V 40%, V 40%. No entanto, os anarquistas são unânimes contra eles fora de seu grupo: assim como os defensores de X e Y a partir de Z o de W classificar v última posição em sua ordem de preferências! É aqui que os anarquistas têm uma ótima idéia tomar poder apesar desse importante handicap. Eles dizem: “Em vez de votar de forma equilibrada entre nossos concorrentes, providenciaremos para ampliar as piores derrotas, tanto quanto possível!”.

Para fazer isso, os eleitores do grupo V são divididos em Três subgrupos (por outro lado, eles ainda têm apenas um candidato):

  • subgrupo $ v_1 $ conta 18% de todos os eleitores e votação “v > z > y > x > w “;
  • O subgrupo $ v_2 $ tem 12% dos eleitores e voto “v > y > x > z > w “;
  • o subgrupo $ v_3 $ conta 10% eleitores e vote” v > x > z > y > w “.

com esta estratégia, temos os seguintes votos:

  • x y > z > w > V Para 20% dos eleitores;
  • v > x > y > z > w para 18% dos eleitores;
  • y > z > x > w > v para 16% dos eleitores;
  • w > z > x > y > v para 13% dos eleitores;
  • v > z > x > Y > w para 12% dos eleitores;
  • z > w > y > x > v para 11% dos eleitores;
  • v > y > z > x > w para 10% dos eleitores.

Isso leva ao seguinte diagrama de preferência binária (direita):

a manipulação de anarquistas

Aqui estão os diagramas correspondentes ao exemplo do tabuleiro de xadrez com anarquistas, à esquerda no caso em que os anarquistas votam sinceramente (assumimos que as preferências dos anarquistas entre x, y e z são aleatórias e W ainda é seu odiado candidato), e bem com a manipulação que explicamos (as mudanças são indicadas em vermelho). No primeiro caso, o vencedor do Minimax está lá; No segundo, é v, a quem são todos os outros candidatos ainda!

Então, as piores derrotas de X, Y e Z são respectivamente 62%, 63% e 64% (respectivamente contra z, x e y), a pior derrota de W é 87% (contra Z) e a pior derrota de V é de 60% (contra qualquer um dos seus oponentes): é, portanto, V que se torna o vencedor do Minimax ! “Obviamente, os partidários de x, y, z e então têm a oportunidade de designar y como um candidato comum e falhar no plano de V, mas dissemos alguns parágrafos mais altos do que a filosofia do critério de Condorcet era Economize tanto quanto possível para eleitores os tormentos do voto estratégico! Parece, portanto, de acordo com este ponto de vista, que o método minimox não é relevante quando não há vencedor do Condorcet.

o método Schulze

Agora vamos agora apresentar um método Concebido em 1997 por um estudante de física alemã chamado Markus Schulze, que não tem a deficiência com o método Minix. A filosofia por trás do método Schulze é a seguinte: “Na parte inferior, uma eleição, nunca é um truque para evitar a inconveniência das revoluções: consultamos os constituintes para saber quem eventualmente ganharia a revolução sem ter que vencer!”.

O que será chamado de “revolução” aqui, é quando um grande número de eleitores concorda em derrubar o presidente e substituí-lo por outro, em cuja identidade concordaram antes. Nesse sentido, é fácil entender o critério Condorcet: se um candidato (chamado) é vencedor do Condorcet, qualquer outro candidato que acontecesse ao poder seria rapidamente revertido pela maioria que prefere X a este candidato, enquanto uma vez x estará no poder, nunca haverá a maioria para derrubá-lo, o que tornará seu assento muito mais estável. No final, desde que rapidamente tenhamos transições de n ‘importações que para x e raramente x transições para qualquer um, é X que estará no poder a maior parte do tempo. (Note que aqui não afirmamos que é impossível derrubar um presidente sem ter uma maioria ligada contra ele: nós apenas dizemos que isso é muito mais fácil fazer isso assim que tivermos mais algumas pessoas para liderar a revolução) .

Vamos ver o que aconteceria em tal quadro para o exemplo do tabuleiro de xadrez com anarquistas. As revoluções tendem a derrubar os presidentes na direção indicada pelas flechas, e muito mais raramente na direção oposta. Portanto, no final de algumas revoluções, o presidente é necessariamente x, y ou z, desde uma vez que chegamos a um desses três não há caminho ao longo das flechas que traz em W ou V! Então, vemos já (como parecia natural para nós) que não é v que as revoluções trarão para o poder a maior parte do tempo.

Vamos continuar. Sabemos que será essencialmente x, y e z que compartilharão poder, mas em que proporções? Se apenas olharmos para as flechas sobre esses três candidatos, temos o diagrama esquerdo abaixo:

O método Schulze contra a manipulação dos anarquistas

Estes diagramas explicam o que acontece quando o método Schulze é aplicado à situação em que os anarquistas estão tentando lidar com o manuseio. O grupo chefe do diagrama de preferências binárias nesta situação é então composta dos três candidatos {x, y, z}: em particular V é eliminado desde que foi espancado por todos os outros candidatos! Em um segundo passo, olhamos para o diagrama das preferências binárias entre esses três candidatos. Para trazer um grupo de cabeça menor, excluímos a flecha mais fraca. O novo diagrama tem um grupo de cabeça que consiste no único candidato x: por isso é aquele que é declarado vencedor pelo método.

Agora a ideia é que, similarmente, foi Muito mais difícil fazer uma revolução com menos de 50% das pessoas do que mais de 50%, é muito mais difícil fazer uma revolução com 62% do que com 63% ou 64%. ..Assim, apagamos a seta marcada “62%” para significar que esta revolução é rara, e chegamos ao diagrama certo acima. No final de algumas revoluções, é necessariamente x que é presidente: a ideia do método Schulze é dizer que é ele quem deve ser proclamado vencedor da eleição!

Agora que explicamos o princípio do método Schulze, vamos acabar dando uma definição rigorosa e certificar-se de que ele fornece um vencedor único em todos os casos. Nós simplesmente assumimos que nunca há dois candidatos exatamente amarrados ou duas flechas tendo exatamente a mesma força no diagrama de preferências binárias, que é sempre o caso na prática quando há muitos eleitores.

Observe que neste Parágrafo, às vezes atenderemos diagramas incompletos de preferência binária, ou seja, onde alguns candidatos não estão conectados por setas.

Definição (grupo de cabeça)

em um diagrama de preferências binárias (possivelmente incompleta), Diz-se que um candidato (chamado aqui x) pertence ao grupo líder quando, a partir de qualquer outro candidato, é possível seguir um caminho de acordo com as setas que inicia desse candidato e termina em x.

Aqui é importante notar que, se o diagrama estiver concluído, o rodoviário nunca é vazio:

Teorem

em um diagrama de preferência binária completo, o rodoviário de cabeça nunca é vazio. / p>

demonstração

Vamos apresentar uma maneira de construir o grupo de cabeça que mostra que este nunca é vazio. Vou ligar aqui qualquer grupo de candidatos como, quando começamos a partir de qualquer candidato que não esteja neste grupo, podemos alcançar qualquer candidato em grupo após as flechas.

Eu primeiro observo que o grupo de todos os candidatos é uma grama de cabeça, já que não há candidato que não pertence a este grupo!

Agora, eu digo o seguinte: Quando você tem um alto overgrown,

  • ou este upgroup é o grupo real de cabeça;
  • ou, entre este upgroup, podemos selecionar um determinado número diferente de zero de candidatos que formam um rigor rentamente menor.
  • De fato, suponha que nosso grupo superior não seja o verdadeiro rompão. A única maneira como isso acontece é que há pelo menos um candidato x neste grupo superior ao qual não é possível ter sucesso de outro candidato y, que é necessariamente no ongroup, já que sabemos que podemos levar a qualquer candidato ao atual de qualquer candidato fora do grupo superior. Agora, seleciono os candidatos do upgroup que são tal que, quando começamos a partir de um desses candidatos, não podemos chegar em X. Este novo grupo não está vazio, pois contém lá, e é estritamente menor que o grupo de cabeça inicial Como não contém X. Eu digo que este novo grupo ainda é uma avisadora da cabeça. De fato, considere um candidato Z que não está neste novo grupo. Ou este candidato não estava em nosso upground inicial, e então sabe que podemos ir de Z em qualquer ponto do nosso grupo superior inicial e, portanto, especialmente em qualquer ponto em nosso novo grupo. Esse candidato estava em nosso upgroup inicial, mas não no novo grupo. Assim, candidato Z, podemos retornar ao candidato x seguindo as flechas (por definição do novo grupo). Mas o candidato x, podemos ir a qualquer candidato w do novo grupo: na verdade, há uma flecha entre x e w porque o nosso diagrama está completo, e necessariamente aponta para x a w desde que não há como W para X ! No final, mostramos que para qualquer candidato Z que não esteja em nosso novo grupo, podemos ir desse candidato a qualquer candidato ao novo grupo após as setas, o que significa que o novo grupo é um upgroup.

    Vamos no toproup da cabeça formada por todos os candidatos, e desde que ainda não encontrássemos o verdadeiro grupo de ouvido, aplique o método acima para formar superagrupos de leads mais e mais pequenos, mas todos não vazios. Necessariamente de cada vez teremos que parar e, nesse momento, o nosso upgroup será o verdadeiro de cabeça de cabeça de acordo com a alternativa acima, e este grupo de cabeça estará bem vazio, o que prova o teorema.

    Definição (método Schulze)

    De um diagrama completo de preferência binária (onde todas as setas carregam pontuações diferentes), definimos o vencedor do Schulze pelo seguinte método:

    1. começamos a partir do diagrama das preferências binárias para todos os candidatos.
    2. Se houver, na verdade, apenas um candidato, o único -ci é proclamado vencedor e parada.
    3. de outra forma, olhamos para o grupo de cabeça: Se estritamente menor que o conjunto inicial, apagarmos todos os candidatos que não estão neste grupo de ouvido (assim como as flechas sobre eles), e o método é iniciado novamente por Não havia mais candidatos restantes.
    4. Se, por outro lado, o grupo de cabeça contenha todos os candidatos, as setas de escores menores são gradualmente apagadas até que o líder do diagrama obtido pela apagamento das setas excluídas pelo menos um dos os candidatos (que necessariamente acontece, porque uma vez todos As flechas seriam apagadas que não haveria ninguém no grupo principal). Naquela época, apagamos todos os candidatos que não estão neste novo grupo de cabeça (bem como as flechas sobre eles), e o método é iniciado novamente por se houvesse mais do que os candidatos restantes.

    Para garantir que o método leva à designação de um vencedor, resta ver-se que durante o procedimento de apagamento de flechas, não é provável que caia em um grupo vazio:

    Teorema

    Se alguém tiver um diagrama de preferência binária para vários candidatos (possivelmente incompletos) em que o grupo de cabeça contém todos os candidatos, então apague uma das setas não pode trazer para uma situação em que o novo grupo de cabeça estaria vazio . Portanto, quando se começa a partir de um diagrama de preferências binárias em que o grupo de cabeça contém todos os candidatos e que um apaga suas flechas, um por um, o primeiro momento em que o grupo de cabeça deixa de conter todos os candidatos dá uma cabeça não vazia Grupo.

    Demonstração

    Demonstramos apenas o início da declaração, a seguinte parte “Consequentemente” resultando imediatamente. Vamos sair de um diagrama de preferência binário em que o grupo de ouvido contém todos os candidatos e apaga-se – em uma flecha, que chamamos X o candidato à esquerda. Vamos mostrar que X é necessariamente no novo grupo de cabeça, que será, portanto, não vazio. Para fazer isso, considere qualquer candidato y, e mostre que podemos ir de y para x seguindo as flechas apesar do apagamento feito. Como, antes do apagamento da flecha, o grupo da cabeça continha todos os candidatos, então tínhamos um caminho que passou de Y para X. Mas inevitavelmente este caminho não pediu emprestado a flecha apagada, já que esta flecha começa a partir de x então que em nosso maneira x é o ponto de chegada! É portanto, que o caminho sempre seja seguido quando a seta é apagada, o que queríamos.

    Deitamos que o interesse do método Schulze era evitar manipulações como as dos anarquistas no exemplo do tabuleiro de xadrez. Pode-se realmente provar que tal manipulação é impossível com este método:

    teorema (robustez à manipulação)

    Suponha que existam dois tipos de candidatos: os candidatos “irracionais” e os candidatos “razoáveis” (nós Suponha que haja pelo menos um candidato razoável), e chame “eleitor razoável” um eleitor que classifica todos os candidatos irracionais no final de sua ordem de preferências. Então, se há uma maioria absoluta de eleitores razoáveis e esses eleitores votam sinceramente, nenhum candidato irracional pode ganhar com o método Schulze.

    demonstração

    Da definição do método Schulze, basta mostrar que nenhum candidato irracional pertence ao grupo de cabeça em tal situação. No entanto, quando começamos a partir de um candidato razoável e a flecha do diagrama das preferências binárias, inevitavelmente levamos a outro candidato razoável: na verdade, a maioria dos eleitores razoáveis garante que nenhuma flecha possa apontar um candidato razoável para um candidato razoável para um candidato razoável. Portanto, é impossível ter um caminho que deixa um candidato razoável e leva a um candidato irracional, o que queríamos.

    Conclusão

    o Condorcet Critério para um método eleitoral democrático, que afirma que um candidato preferido em qualquer outro face a face deve sempre ser eleito, permite uma certa medida para evitar os problemas do voto estratégico.Quando não há vencedor do Condorcet, podemos imaginar vários métodos diferentes “Condorcet”: Entre eles, o método Schulze tem a vantagem de ter uma simples justificação heurística e ser mais robusta para algumas formas de manipulação, por exemplo, o mínimo método. Este é atualmente um dos métodos de voto mais populares por teóricos de democracia, e é usado, por exemplo, por desenvolvedores de sistema operacional livre do Debian – Geeks ainda na vanguarda do progresso bizarro …; -)

    em um Artigo futuro, apresentaremos outros métodos originais, não satisfaz necessariamente o critério condutor, mas que também foram defendidos por teóricos por suas propriedades matemáticas.

    Referências

    • em Track azul: os páginas da Wikipedia “Método Condorcet”, “Condorcet Paradox” e “Schulze método” (esta última página sendo bastante na pista vermelha).
    • Nos Teoremas do Eleitor Mediano: Fundamentos da Escolha Social Teoria, por Roger B. Myerson (1996); Texto livre disponível na internet (off-pista).
    • wiki.electorma.com: um wiki que tem os diferentes métodos condorcet e suas propriedades respectivas (off-pista).

    Leave a comment

    O seu endereço de email não será publicado. Campos obrigatórios marcados com *