64
1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de Matemática Pura da Faculdade de Ciências da Universidade do Porto

1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

Embed Size (px)

Citation preview

Page 1: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

1

Teoria Matemática das Eleições: Geometria e

Paradoxos

Métodos finitos em Matemática, disciplina do

Mestrado em Ensino da Matemática do

Departamento de Matemática Pura da

Faculdade de Ciências da Universidade do Porto

Page 2: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

2

Haverá alguma dificuldade em VOTAR?

O que pode correr mal quando votamos?

Page 3: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

3

Gaius Plinius Caecilius Secundus, Plínio o Jovem (61 ou 62 - 113)

Page 4: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

4

“Uma moção foi colocada perante o Senado sobre os escravos libertos do consul Afranius Dexter que foi encontrado morto, ou pelas suas próprias mãos, ou pela mão dos seus escravos, morto num acto criminoso, ou em obediência aos seus desejos.”

“Uma pessoa (…) pensou que, depois do inquérito, deviam ser perdoados. Uma segunda pessoa pensou que deviam ser desterrados para uma ilha, uma terceira pessoa que deviam ser executados. A diversidade das propostas significa que tinham de ser votadas individualmente.”

Page 5: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

5

Suponhamos que a proporção das preferências era:Perdão - 40%Desterro - 35%Execução - 25%

E se a votação fosse apenas entre Perdão e Desterro?Ou apenas entre Perdão e Execução?Ou apenas entre Desterro e Execução?Ou com a agenda: Desterro/Execução/Perdão?

Page 6: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

6

O matemático francês Jean-Charles Borda (1733-1799) foi o primeiro a estudar sistematicamente o problema. O que descobriu surpreendeu os seus contemporâneos. Olhando para o sistema eleitoral como um método de agregar opiniões para encontrar uma escolha colectiva, notou que métodos diferentes conduzem a resultados diferentes. O paradoxo de Borda, como veio a ser conhecido, foi muito discutido na época, sem se encontrar uma solução satisfatória.

Paradoxos

Page 7: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

7

Borda apresentou o problema à Academia Real Francesa em 16 de Junho de 1770. Colocou um exemplo em que 21 votantes escolhiam entre 3 candidatos. Considerou as preferências relativas de cada votante, isto é a forma como cada eleitor hierarquizava os candidatos. O que reparou foi que era possível eleger um candidato que a maioria dos eleitores colocava em último lugar. Bastava para isso que os votos dos outros dois estivessem suficientemente divididos.

Analisemos o exemplo apresentado por Borda. Onde significa que X é preferido a Y.X Y

O sistema usado nas democracias baseia-se no chamado voto plural, que é mais conhecido pela sigla “Um homem um voto”.

Page 8: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

8

Votos Preferência

1

7

7

6

A B C

A C B

B C A

C B A

Apenas uma pessoa coloca o candidato A em primeiro lugar, seguido do B e, depois, do C. Na segunda linha vemos que há 7 votantes que preferem o candidato A, que põem em segundo lugar o candidato C e em terceiro o B.

Neste exemplo, o candidato mais votado segundo o sistema plural (um homem um voto) é A, com 8 votos a favor, contra 7 em B e 6 em C.

No entanto, esse é o candidato mais detestado pela maioria do eleitorado, uma vez que 13 votantes em 21 o colocam em último lugar!

Consideremos a seguinte tabela com as preferências dos 21 eleitores de Borda:

Page 9: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

9

Voto pluralA ordenação das alternativas é feita contando, para cada uma, o número de boletins de voto em que esta ficou colocada em primeiro lugar. As alternativas são ordenadas por ordem crescente do correspondente número de votos obtidos.

Sistemas de votação

Sistema Sequencial aos Pares com AgendaDepois de acordada uma ordenação preliminar das alternativas, a que se chama uma agenda consideram-se os resultados de eleições de pares de alternativas, pela ordem dada na agenda, eliminando as derrotadas da agenda e prosseguindo até a agenda conter apenas um elemento. As alternativas são finalmente ordenadas por ordem inversa de eliminação da agenda.

Page 10: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

10

Sistemas de votação

Expresso, suplemento Economia

Sábado, 11 de Maio de 2002

Sistema de HareElimina(m)-se, em eleições sucessivas, a(s) alternativa(s) com o menor  número de primeiros lugares, sendo as alternativas ordenadas por ordem  inversa de eliminação.

O SISTEMA de eleição presidencial francês produziu este ano a situação insólita de que a maioria dos franceses possa não se rever neste acto eleitoral.O resultado da lotaria da primeira volta…Este sistema é usado na Irlanda para as eleições presidenciais desde 1938, e apresento de seguida os resultados oficiais da eleição de 1990, para o leitor poder ver como funciona na prática. Neste caso, Mary Robinson ganhou a Brian Lenihanl na segunda contagem, porque a maioria dos eleitores que colocaram Austin Currie em primeiro lugar a tinham colocado em segundo.

Page 11: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

11

Sistemas de votação

Contagem de BordaAtribui-se a cada posição do boletim de voto, um número de pontos: 0 para a última, 1 para a penúltima, …, n-1 para a primeira. Os pontos “ganhos” por cada alternativa são totalizadas e as alternativas são ordenadas por ordem crescente de pontos obtidos.

Page 12: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

12

Analisemos um exemplo em onde quinze pessoas seleccionam a sua bebida preferida entre L (leite), C (cerveja), e V (vinho). As preferências dos eleitores são dadas pela tabela:

Votos Preferência

6

5

4

L V C

C V L

V C L

Será mesmo o leite a bebida preferida dos votantes?

Então o resultado da maioria (onde cada pessoa vota na sua bebida favorita) é:

L C V

Aparentemente, o leite é a bebida escolhida!

Problemas

Page 13: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

13

Se é, seria de esperar que os votantes preferissem o leite à cerveja. Mas como mostra a tabela seguinte, estes votantes preferem realmente a cerveja ao leite.

Votos Preferência Leite Cerveja

6 6 0

5 0 5

4 0 4

Total 6 9

L V C

B V L

V B C

Do mesmo modo, 9 votantes preferem o vinho ao leite e 10 preferem o vinho à cerveja. Isto cria uma contradição e uma potencial controvérsia entre os votantes, porque estas comparações entre pares sugerem que os eleitores preferem realmente o , o resultado oposto ao da maioria.V C L

O que correu mal?

Page 14: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

14

Modernamente chama-se a isso a eleição de um perdedor de Condorcet, isto é, de um candidato que perde em comparações bilaterais com todos os outros.

Aqui, o leite é preterido em relação à cerveja se apenas estas duas hipóteses se colocassem, era preterido de novo se só se colocasse a hipótese de escolha entre leite e vinho, mas era preferido se todas as hipóteses fossem colocadas em simultâneo.

No exemplo de Borda, o candidato A perdia as eleições se apenas as disputasse com o candidato B, perdê-las-ia de novo se apenas se defrontasse com o candidato C, mas ganhá-las-ia se fosse às urnas contra os dois em simultâneo.

Page 15: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

15

Marie Jean Antoine Nicolas de CaritatMarquês de Condorcet (1743-1794)

Método de CondorcetOs resultados são decididos estritamente nos termos de uma comparação entre pares de candidatos.O vencedor de Condorcet é o candidato que vence todos os candidatos restantes em eleições um contra um.

Sistemas de votação

Page 16: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

16

Sistema de votação (im)perfeito…

Votos Preferência

6

5

4

L V C

C V L

V C L

Consideremos, novamente, o perfil envolvendo 15 eleitores e 3 alternativas.

Plural

L

C

V

Procuremos as ordenações finais, para este perfil, usando cada um dos sistemas eleitorais acima descritos.

Contagem de Borda

L

V

C

6 2 5 0 4 0 12 6 0 5 2 4 1 14 6 1 5 1 4 2 19

Hare

C

L

V

S. S. P. A.

LVC

V

C

L

S. S. P. A.

VCL

L

V

C

Borda

V

C

L

Condorcet

V

C

L

Page 17: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

17

Conclusão…

Arranjar um processo, método ou algoritmo, um sistema eleitoral ou de votação, que decida, a partir do conjunto das listas de preferência, a que se chama o perfil eleitoral, uma ordenação das alternativas que reflicta o melhor possível as preferências dos eleitores

Desafio

O resultado de uma eleição pode depender bastante do sistema eleitoral usado!

Page 18: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

18

Condições…Numa primeira análise, as seguintes condições parecem ser imprescindíveis para que um sistema de votação democrático traduza as preferências dos eleitores:

Condição de Pareto (ou de unanimidade):Se a alternativa X ficou colocada acima da alternativa Y em todos os boletins de voto então na lista final deve ter-se .X Y

Monotonia: Se de uma eleição para outra, envolvendo os mesmos eleitores e os mesmos candidatos, a posição de um dos candidatos for alterada, em um ou mais boletins de voto, mas sempre a favor desse candidato, então a sua posição na ordenação final não deve ser inferior à posição em que ficou colocado na primeira eleição.

Critério do Vencedor de Condorcet (CVC):Se existir um vencedor de Condorcet, este deve ser o vencedor da eleição.

Page 19: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

19

Condições…

Simetrias:

Igualdade (ou Anonimato): Permutar as listas de preferência, sem as alterar, não deve ter nenhum efeito no resultado da eleição.

Neutralidade:Se todos os eleitores cometerem o erro de trocar as alternativas X e Y, então basta trocar X com Y no resultado final para corrigir o erro.

Independência das Alternativas Irrelevantes (IAI): Se em duas eleições distintas, envolvendo os mesmos eleitores e os mesmos candidatos, a ordem relativa de dois dos candidatos não foi alterada em nenhum boletim de voto, então a ordem relativa desses mesmos candidatos no resultado final deve ser a mesma.

Page 20: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

20

Questão:Será que algum dos métodos satisfaz estas condições?

Kenneth ArrowEm 1951, (prémio Nobel da Economia em 1972) provou o seguinte resultado:

Teorema:Não existe nenhum sistema de votação que satisfaça simultaneamente as condições de Pareto, IAI e igualdade! 

Ideia da demonstração:As condições de Pareto e a da Independência de Alternativas Irrelevantes conduzem a uma ditadura!!!

Page 21: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

21

Exemplos…O Sistema Sequential aos Pares com Agenda não satisfaz a condição de Pareto!

4 4 4

A C B

B A D

D B C

C D A

ACD

Com agenda: ABCD.

Tem-se: ABCD CD D D C A B

D é o vencedor apesar de todos os eleitores preferirem B a D !

Considere-se o seguinte perfil:

Page 22: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

22

Exemplos…

O Sistema de Hare não satisfaz a condição de Monotonia!

Considere-se o seguinte par de eleições, em que na segunda delas 3 dos eleitores alteram os seus boletins de voto de para , uma mudança favorável a A, enquanto os outros eleitores não alteram as suas listas de preferências

B A C A B C

1ª Eleição

12 9 7 3

A C B B

B A C A

C B A C

2ª Eleição

15 9 7

A C B

B A C

C B A

Page 23: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

23

Exemplos…

1ª Volta

A: 12

B: 10

C: 9

12 9 7 3

A A B B

B B A A

2ª Volta

A: 21

B: 10

1ª Eleição

12 9 7 3

A C B B

B A C A

C B A C

2ª Eleição

15 9 7

A C B

B A C

C B A

1ª Volta

A: 15

B: 7

C: 9

15 9 7

A C C

C A A

2ª Volta

A: 15

B: 16

O candidato A, que ganhou a primeira eleição, perde a segunda quando só houve alterações a seu favor !

Page 24: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

24

Exemplos…A contagem de Borda não satisfaz IAI!

Considere-se o seguinte par de eleições, em que alguns dos eleitores (4) mudam a sua lista de preferências, mas ninguém altera a posição relativa de A versus B.

1ª Eleição

7 4

A C

B B

C A

2ª Eleição

7 4

A B

B C

C A

C: 8

B: 11

A: 14

C: 4

B: 15

A: 14

A B C B A C

Resultados:

Vê-se assim que a posição relativa de A e B é alterada de uma eleição para a outra.

Page 25: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

25

Sistema de votação (im)perfeito II

Sistemas/Condições Pareto CVC Mono IAI

Plural Sim Não Sim Não

Borda Sim Não Sim Não

Hare Sim Não Não Não

Seq. Pares c/ agenda Não Não Sim Não

Page 26: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

26

IAI não é realista…Teorema:Quando o número de candidatos (ou alternativas) é igual ou superior a 3, qualquer sistema que satisfaça as condições IAI e Pareto é um sistema que não admite empates.

Demonstração:Suponhamos que tal não acontecia, ou seja que existia um perfil para o qual há duas alternativas, X e Y, que resultam empatadas:

... ...

X Y

... ... ... ... ... X = Y

Y X

... ...

Na figura acima, a parte esquerda representa o perfil da eleição, ou seja o conjunto de todos os boletins de voto, havendo alguns onde a alternativa X está acima de Y e outros onde o contrário acontece, mas admite-se que uma dessas possibilidades não ocorra.

Page 27: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

27

Seja Z uma terceira alternativa qualquer (cuja existencia é garantida por uma das hipóteses feitas). Uma vez que o sistema satisfaz IAI e a condição de Pareto, resulta que se, numa nova eleição, os eleitores com X > Y colocassem Z entre X e Y, enquanto que aqueles com X < Y colocassem Z acima de Y, ter-se-ia:

  ...   ...      

  X   Z      

  ...   ...      

... Z ... Y ... X = Y , Z > Y

  ...   ...      

  Y    X      

  ...   ...    

e portanto Z > X

Page 28: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

28

Agora, se todos os eleitores trocarem Y com Z, o que não altera as posições relativas de X vs. Y e de X vs. Z...

... ...

X Y

... ...

... Y ... Z ... Z > X , X=Y

... ...

Z X

... ...

e portanto Z > Y…

o que contradiz a hipótese de o sistema verificar a condição de Pareto.

Page 29: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

29

O Critério de Condorcet não é inquestionável...Saari, dá um exemplo semelhante ao que se segue, mostrando que o vencedor de Condorcet não é invariante para a “adição de empates”.

31

A

B

C

+

10

A

C

B

10

B

A

C

31

A

B

C

32

B

A

C

22

B

A

C

10

C

B

A

10

A

C

B

10

C

B

A

A é o vencedor de Condorcet

(58.5%)

Perfil empatado

B é o vencedor de Condorcet (50.6%)

Isto mostra que a condição CVC não é tão indiscutivelmente razoável quanto possa parecer numa primeira análise...

Page 30: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

30

Geometria, Eleições e Paradoxos

Do breve estudo que realizamos a contagem de Borda parece ser a ideal. Questionemo-nos sobre esta contagem para o caso de termos três candidatos; estudar casos com mais de três candidatos é uma generalização deste caso.

Mas o que acontece em geral? Há exemplos das disposições de preferências dos eleitores, chamados perfis, para os quais a contagem de Borda é fraca?

Porque não usar outros pesos, tais como (6; 5; 0) ou (4; 1; 0), em vez da escolha de Borda de (2; 1; 0)?

Registando os métodos que atribuem um número de pontos ao primeiro, ao segundo, e ao terceiro candidato ordenados pela ordem de preferência do eleitor, são chamados métodos eleitorais posicionais.

Page 31: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

31

Quando normalizados para atribuir um único ponto ao candidato mais preferido de um eleitor, o ponto atribuído define um vector de voto:

,1, 0 , 0 1pW p p

Por exemplo, os formulários normalizados de (6; 5; 0) e a contagem de Borda são, respectivamente,

5 1

6 2

, ,5 1

1, 0 e 1, 06 2

W W

O sistema plural “um Homem um voto” é representado pelo vector:

0 ,1, 0 0W

Qual o sistema representado representa o vector 1 ,1,1 0 ?W

Este vector representa o método antiplural, pois um eleitor vota contra o seu candidato menos preferido!

Matemática

Page 32: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

32

A normalização do Wp torna claro que há uma continuidade de métodos de registo onde cada um é caracterizado pelo peso (o valor de p ) colocado no candidato segundo posicionado de um eleitor.

Defrontado com todas estas possibilidades, era natural que os colegas matemáticos de Borda, tais como Laplace, Condorcet, e outros, questionassem qual o método Wp que era óptimo no sentido de que os seus resultados melhor reflectissem as opiniões os eleitores.

O debate que começaram continua hoje!

Marie-Jean-Antoine-Nicolas de Caritat Condorcet, matemático francês, filósofo, e político, acrescentou à controvérsia em 1780, o seu método, que produzia o chamado “vencedor de Condorcet”. Este vencedor estava aceite como escolha universal. Mas tem problemas!!!

Matemática

Page 33: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

33

Para ilustrar as dificuldades vejamos um exemplo:

Uma escola pretende comprar um livro de um lote de três possíveis {A, B, C}.

Os 15 membros do Conselho Pedagógico têm que decidir…

Uma maneira natural para seleccionar o livro é por eliminação, onde após ter comparado duas escolhas, {A, B}, o vencedor é comparado com a escolha restante, C.

Suponha-se que as opiniões do conselho Pedagógico são:

Votos Preferência

5

5

5

A B C

B C A

C A B

Matemática

Page 34: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

34

Contemos os votos:

A B C

B C A

C A B

Votos Preferência

5

5

5

Total

A B

5 0

0 5

5 0

10 5

A C

5 0

0 5

0 5

5 10

Em ambas as eleições o vencedor vence com dois terços dos votos, portanto parece seguro dizer que o resultado da votação do Conselho Pedagógico é: C A B.

Matemática

Page 35: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

35

Embora o resultado pareça ser inquestionável, vamos questioná-lo. Nós sabemos já que C vence A e A vence B, assim só falta determinar se C vence B. Podemos não esperar surpresas, mas…

Votos Preferência

5

5

5

Total

B C

5 0

5 0

5 5

10 5

A B C

B C A

C A B

… na verdade encontramos uma: B bate C pelos mesmos dois terços dos votos.

Matemática

Page 36: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

36

Ou seja noutras palavras, este perfil define os resultados eleitorais cíclicos,

, ,A B B C C A

Portanto, seja qual for o candidato votado em último (nesta eleição por agenda aos pares), vence decididamente. Em particular, não há nenhum vencedor ou perdedor de Condorcet.Condorcet compreendeu que os ciclos poderiam acontecer em caso de votação entre pares; ele demonstrou este comportamento introduzindo o exemplo anterior. Tal exemplo é conhecido agora como um perfil de Condorcet.Os ciclos não permitem seleccionar um candidato “óptimo”!!!

Representando por um grafo esta eleição vemos que não existe nem vencedor nem perdedor de condorcet!

C

A B

Matemática

Page 37: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

37

Qual o melhor método?

Os estudos no campo da Teoria Matemática das eleições fora retardados pela complexidade do cálculo combinatório envolvido!

Uma maneira tradicional para comparar procedimentos é construir perfis que mostrem como um método tem uma falha provocada por outro.

Mas para construir exemplos, necessitamos determinar quantos eleitores devemos ter de cada tipo de modo que os resultados resultantes da eleição exprimam o fenómeno desejado.

Complexidade e Geometria

Page 38: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

38

Questões:

Podem os vencedores de Borda e de Condorcet ser diferentes?

Existe alguma explicação para que os resultados de uma eleição mudem com o uso de diferentes vectores Wp?

Há perfis dos eleitores onde cada candidato é o “vencedor” para um Wp apropriado?

Os exemplos que os suportam são fracos ou fortes?

Podemos caracterizar todos os exemplos possíveis?

Qual é o número mínimo de eleitores necessários para criar cada particularidades interessantes em eleições?

Complexidade e Geometria

Page 39: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

39

Complexidade e GeometriaProcurando respostas…

Recentemente, o progresso no estudo da matemática das eleições foi sendo feito com base na procura de respostas para as questões anteriores substituindo o método combinatório tradicional por uma perspectiva geométrica.

Nesta apresentação tentaremos mostrar como a geometria reduz assuntos anteriormente complicados a formas mais simples para assim poderem ser apresentados aos estudantes que as podem representar graficamente com equações algébricas elementares.

Donald Saari, um matemático da Universidade de Califórnia em Irvine que se tem dedicado a estudar os problemas eleitorais, mostrou, usando a geometria, que pequenas mudanças em qualquer sistema eleitoral podem trazer grandes alterações nos resultados das eleições. Saari é um dos matemáticos e especialistas de ciência política que se têm dedicado a estudar os problemas da chamada escolha pública, uma área que sofreu um grande desenvolvimento na segunda metade do século XX.

Page 40: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

40

Geometria (Donald Saari)

Tipos de Eleitores

O “tipo” de eleitor é definido pela forma como os candidatos {A, B, C} são ordenados. Por conveniência denotem-se os tipos pelos números de 1, 2, 3, 4, 5 e 6.

Tipo Preferência

1

2

3

4

5

6

A B C

A C B

C A B

C B A

B C A

B A C

1

3

52

6

4

C

BA

Estes tipos estão reflectidos na geometria do triângulo equilátero, onde cada candidato está identificado como um vértice.

Page 41: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

41

Page 42: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

42

Geometria – Exemplos de Condorcet

Dos seis tipos de preferências que referimos para três candidatos vamos estudar só três tipos. Das vinte hipóteses que temos de escolher três tipos, a nossa escolha recai sobre os tipos que geram o perfil de Condorcet.

O perfil de Condorcet é gerado pelos tipos: 1, 3 e 5.

Estes três tipos de perfis geram uma configuração simétrica – em moinho de vento – no triângulo considerado.

Page 43: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

43

Geometria – Exemplos de CondorcetConsideremos n eleitores. Sejam nj o número de eleitores do tipo j, o número de eleitores é então n1+n2+n3 = n.

5 31 ,n nn

x y e zn n n

Em vez de trabalharmos com inteiros, dividimos por n de modo que:

representam as fracções de todos os eleitores que são de cada tipo.

A restrição x+y+z = 1, ou z = 1– (x+y), permite-nos representar todos os perfis possíveis como pontos – racionais – do triângulo:

1 , | , 0, 1T x y x y x y

Para um ponto (x, y) T1, a fracção de todos os eleitores com preferências do tipo 1 e 5 são dadas, respectivamente, pelos valores de x e de y; a fracção de todos os eleitores do tipo3 é 1– x– y.

Page 44: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

44

Page 45: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

45

Eleições um contra um…

Page 46: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

46

Page 47: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

47

Page 48: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

48

Page 49: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

49

Teoria Matemática das Eleições

Page 50: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

50

Teoria Matemática das Eleições

Resultados de eleições entre pares

Page 51: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

51

Teoria Matemática das Eleições

Resultados de eleições entre pares - Paradoxos

Page 52: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

52

Teoria Matemática das Eleições

Resultados de eleições entre pares - Paradoxos

Suponhamos que só um eleitor numa população grande (n eleitores) tem tipo 3:

Page 53: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

53

Teoria Matemática das Eleições

Probabilidades - Paradoxos

Caso discreto:

Page 54: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

54

Teoria Matemática das Eleições

Probabilidades - Paradoxos

Caso discreto:

Page 55: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

55

Teoria Matemática das Eleições

Probabilidades - Paradoxos

Caso discreto:

Page 56: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

56

Teoria Matemática das Eleições

Probabilidades - Paradoxos

Resultados Posicionais:

Os registos de para todos os candidatos são:w

Page 57: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

57

Teoria Matemática das Eleições

Probabilidades - Paradoxos

Resultados Posicionais:

Os resultados para todos os pares de candidatos são:

Page 58: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

58

Teoria Matemática das Eleições

Paradoxos

Apesar do método plural e da eleição um contra um

identificarem o mesmo candidato como sendo o

melhor classificado e deste facto parecer abonar a

favor do método uninominal, não devemos esquecer

que o ranking de um perfil por unanimidade

também assemelha-se bastante importante,

devendo assim esperar que os resultados da eleição

favoreçam os três tipos particulares representados

no perfil.

Resultados Posicionais:

Page 59: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

59

Teoria Matemática das Eleições

“Nas questões matemáticas não se compreende a

incerteza nem a dúvida, assim como tão pouco se

podem estabelecer distinções entre verdades

médias e verdades de grau superior.”

Hilbert

Page 60: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

60

Lewis Carrol (1876)

• (as eleições) “são mais um jogo de habilidade que um teste real aos desejos dos eleitores.”

• “na minha opinião é preferível que as eleições sejam decididas de acordo com os desejos da maioria do que os daqueles que têm mais habilidade no jogo, por isso penso ser desejável que todos devam saber as regras pelas quais este jogo se pode ganhar.”

Page 61: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

61

Referências Bibliográficas

ASSUNÇÃO, J. B.2002 O Plebescito Francês. Caderno Economia do

Semanário Expresso de 11 de Maio de 2002BUESCU, J.

2001 O Mistério do Bilhete de identidade e Outras Histórias, crónicas as Fronteiras das

Ciências. Gradiva. LisboaCONDORCET, J.-M.

1785 Éssai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. ParisCONDORCET, J.-M.

1789 Sur la forme des élections. Paris

Page 62: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

62

Referências Bibliográficas

CRATO, N.2002 Paradoxos eleitorais. Revista do Semanário

Expresso do dia 13 de Fevereiro de 2002GEANAKOPLOS, J

2001 Three Brief Proofs of ARROW’S IMPOSSIBILITY THEOREM. Cowles Foundation Discussion Paper No. 1123RRR. Cowles Foundation For Research In Economics. Yale UniversityMACHIAVELO, A.

2004 Sistemas de votação,www.fc.up.pt\cmup\home\machia\

SistemasVot.html Página acedida em 18 de Janeiro de 2004SAARI, D.

1991 A Fourth Grade Experience. CiteSeer (?)

Page 63: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

63

Referências Bibliográficas

SAARI, D.1995 Basic Geometry of Voting. Springer-Verlag

SAARI, D.1997 Are Individual Rights Possible?. Mathematics

Magazine; Vol. 70, No. 2; 83-92 SAARI, D.

1997 The Symmetry and Complexity of Elections. Complexity 2; 13-21

SAARI, D. & VALOGNES, F.1998 Geometry, Voting, and Paradoxes.

Mathematics Magazine; Vol. 71, No. 4; 243-259SAARI, D.

2001 ChaoticElections!A Mathematician Looks at Voting. Americam Mathematical

Society

Page 64: 1 Teoria Matemática das Eleições: Geometria e Paradoxos Métodos finitos em Matemática, disciplina do Mestrado em Ensino da Matemática do Departamento de

64

Referências Bibliográficas

SAARI, D. & BARNEY, S.2003 Consequences os Reversing Preferences.

Mathematical Intelligencer; Vol. 25, No. 4; 32-42TAYLOR, A. D.

1995 Mathematics and Politics – Stategy, Voting, Power and Proff. Springer-Verlag

TAYLOR, A. D.2002 The manipulability of voting systems, to

appear in The American. Mathematical Monthly, 109 (April), 321- 337