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
Haverá alguma dificuldade em
VOTAR?
O que pode correr mal quando
votamos?
Gaius Plinius Caecilius Secundus,
Plínio o Jovem (61 ou 62 - 113)
“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.”
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?
Paradoxos
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.
O sistema usado nas democracias baseia-se no chamado voto
plural, que é mais conhecido pela sigla “Um homem um voto”.
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 X Y significa que X é preferido a Y.
Consideremos a seguinte tabela com as preferências dos 21
eleitores de Borda:
Votos
Preferência
7
A
A
B
B
C
C
C
B
A
6
C
B
A
1
7
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!
Sistemas de votação
Voto plural
A 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.
Sistema Sequencial aos Pares com Agenda
Depois 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.
Sistemas de votação
Sistema de Hare
Elimina(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.
Expresso, suplemento Economia
Sábado, 11 de Maio de 2002
Sistemas de votação
Contagem de Borda
Atribui-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.
Problemas
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
6
5
4
Preferência
L V
C V
V C
C
L
L
Então o resultado da maioria
(onde cada pessoa vota na sua
bebida favorita) é:
L
C
V
Aparentemente, o leite é a bebida escolhida!
Será mesmo o leite a bebida preferida dos votantes?
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
6
5
4
Preferência
L V C
B
V
V
B
Leite
Cerveja
6
0
L
C
0
5
0
4
Total
6
9
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 V C L , o resultado oposto ao da maioria.
O que correu mal?
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.
Sistemas de votação
Marie Jean Antoine Nicolas de Caritat
Marquês de Condorcet (1743-1794)
Método de Condorcet
Os 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.
Sistema de votação (im)perfeito…
Consideremos, novamente, o perfil envolvendo 15 eleitores e 3 alternativas.
Votos
6
5
4
Procuremos as ordenações finais, para
este perfil, usando cada um dos
sistemas eleitorais acima descritos.
Preferência
L V
C V
V C
C
L
L
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
Plural
Hare
S. S. P. A.
LVC
S. S. P. A.
VCL
Borda
Condorcet
L
C
V
L
V
V
C
L
C
V
C
C
V
V
L
C
L
L
Conclusão…
O resultado de uma eleição pode depender bastante do
sistema eleitoral usado!
Desafio
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
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 .
Critério do Vencedor de Condorcet (CVC):
Se existir um vencedor de Condorcet, este deve ser o vencedor da eleição.
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.
Condições…
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.
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.
Questão:
Será que algum dos métodos satisfaz estas condições?
Kenneth Arrow
Em 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!!!
Exemplos…
O Sistema Sequential aos Pares com Agenda não satisfaz a condição de
Pareto!
Considere-se o seguinte perfil:
4
4
4
A
C
B
B
A
D
D
B
C
C
D
A
Com agenda: ABCD.
Tem-se: ABCD
ACD
CD
D
D
D é o vencedor apesar de todos os eleitores preferirem B a D !
C
A
B
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 B A C para A B C ,
uma mudança favorável a A, enquanto os outros eleitores não alteram as
suas listas de preferências
1ª Eleição
2ª Eleição
12
9
7
3
15
9
7
A
C
B
B
A
C
B
B
A
C
A
B
A
C
C
B
A
C
C
B
A
Exemplos…
1ª Eleição
2ª Eleição
12
9
7
3
15
9
7
A
C
B
B
A
C
B
B
A
C
A
B
A
C
C
B
A
C
C
B
A
1ª Volta
1ª Volta
A: 12
A: 15
B: 10
B: 7
C: 9
C: 9
12
9
7
3
15
9
7
A
A
B
B
A
C
C
B
B
A
A
C
A
A
2ª Volta
2ª Volta
A: 21
A: 15
O candidato A, que
ganhou a primeira
eleição, perde a segunda
quando só houve
alterações a seu favor !
B: 10
B: 16
23
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
2ª Eleição
7
4
7
4
A
C
A
B
B
B
B
C
C
A
C
A
Resultados:
Vê-se assim que a posição
relativa de A e B é alterada de
uma eleição para a outra.
A
A: 14
A: 14
B: 11
B: 15
C: 8
C: 4
B
C
B
A
C
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
25
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
...
...
Y
X
...
...
...

X=Y
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.
26
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
...
...
Y
X
...
...
...

X=Y,Z>Y
e portanto Z > X
27
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
...
...
...
 Z > X , X=Y
e portanto Z > Y…
o que contradiz a hipótese de o sistema verificar a condição de Pareto.
28
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
22
10
10
10
A
B
A
B
C
B
A
C
A
C
C
B
C
A é o vencedor
de Condorcet
(58.5%)
+
Perfil
empatado
31
32
10
10
A
B
A
C
B
B
A
C
B
A
C
C
B
A

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...
29
Geometria, Eleições e Paradoxos
30
31
32
Teoria Matemática das Eleições
Aos métodos que atribuem um número de pontos aos candidatos
ordenados pela ordem de preferência do eleitor, chamamos métodos
eleitorais posicionais.
Quando normalizados para atribuir um único ponto ao candidato mais
preferido de um eleitor, o ponto atribuído define um vector de voto
w  1,  , 0
.
Teoria Matemática das Eleições
Consideremos o seguinte exemplo:
Teoria Matemática das Eleições
Perfis dos eleitores:
C
3
4
5
2
1
A
6
B
Teoria Matemática das Eleições
Teoria Matemática das Eleições
Resultados de eleições entre pares
Teoria Matemática das Eleições
Resultados de eleições entre pares - Paradoxos
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:
Teoria Matemática das Eleições
Probabilidades - Paradoxos
Caso discreto:
Teoria Matemática das Eleições
Probabilidades - Paradoxos
Caso discreto:
Teoria Matemática das Eleições
Probabilidades - Paradoxos
Caso discreto:
Teoria Matemática das Eleições
Probabilidades - Paradoxos
Resultados Posicionais:
Os registos de
w para todos os candidatos são:
Teoria Matemática das Eleições
Probabilidades - Paradoxos
Resultados Posicionais:
Os resultados para todos os pares de candidatos são:
Teoria Matemática das Eleições
Paradoxos
Resultados Posicionais:
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.
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
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.”
Referências Bibliográficas
ASSUNÇÃO, J. B.
2002
O Plebescito Francês. Caderno Economia do
Semanário Expresso de 11 de Maio de 2002
BUESCU, J.
2001
O Mistério do Bilhete de identidade e Outras
Histórias, crónicas as Fronteiras das Ciências.
Gradiva. Lisboa
CONDORCET, J.-M.
1785
Éssai sur l’application de l’analyse à la probabilité
des décisions rendues à la pluralité des voix. Paris
CONDORCET, J.-M.
1789
Sur la forme des élections. Paris
Referências Bibliográficas
CRATO, N.
2002
Paradoxos eleitorais. Revista do Semanário Expresso
do dia 13 de Fevereiro de 2002
GEANAKOPLOS, J
2001
Three Brief Proofs of ARROW’S IMPOSSIBILITY
THEOREM. Cowles Foundation Discussion Paper No.
1123RRR. Cowles Foundation For Research In
Economics. Yale University
MACHIAVELO, A.
2004
Sistemas de votação,
www.fc.up.pt\cmup\home\machia\SistemasVot.html
Página acedida em 18 de Janeiro de 2004
SAARI, D.
1991
A Fourth Grade Experience. CiteSeer (?)
Referências Bibliográficas
SAARI, D.
1995
SAARI, D.
1997
Basic Geometry of Voting. Springer-Verlag
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-259
SAARI, D.
2001
ChaoticElections!A Mathematician Looks at
Voting. Americam Mathematical Society
Referências Bibliográficas
SAARI, D. & BARNEY, S.
2003
Consequences os Reversing Preferences.
Mathematical Intelligencer; Vol. 25, No. 4; 32-42
TAYLOR, 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), 321337