A tradução deste artigo está abaixo da qualidade média aceitável. Talvez tenha sido feita por um tradutor automático ou alguém que não conhece bem o português ou a língua original. Caso queira colaborar com a Wikipédia, tente encontrar a página original e melhore este verbete conforme o guia de tradução.(Setembro de 2021)
O método Schulze[a] é um sistema de votação desenvolvido em 1997 por Markus Schulze para selecionar um único vencedor usando votos que expressam preferências. O método pode também ser usado para criar listas ordenadas de vencedores. O método Schulze é um método de Condorcet, ou seja, se há um candidato que é preferido a todo outro candidato em comparações emparelhadas, então este candidato será o vencedor. Atualmente, é o método Condorcet mais disseminado. Ele é usado por diversas organizações, como a Wikimedia, Debian, Gentoo e Software in the Public Interest.
O resultado do método Schulze dá uma ordenação de candidatos. Portanto, se vários cargos estão disponíveis, o método pode ser utilizado para este propósito sem passar por nenhuma modificação, deixando os candidatos melhor classificados k ganhar as vagas disponíveis k. Além disso, foi proposta uma variação de voto individual transferível para eleições de representação proporcional.
Uma maneira típica para que os eleitores especifiquem suas preferências em uma cédula eleitoral (veja a esquerda) é através do seguinte; cada cédula lista todos os candidatos, e cada eleitor ordena sua lista na ordem de sua preferência através de números: o eleitor preenche '1' ao lado do(s) candidato(s) que mais prefere, um '2' ao lado do(s) segundo(s) mais preferidos, e assim sucessivamente. Cada eleitor pode opcionalmente
dar mesma preferência para mais de um candidato, indicando que o eleitor é indiferente entre tais candidatos.
utilizar números não sucessivos para expressar preferências, sem qualquer impacto no resultado das eleições, visto que apenas a ordem na qual os candidatos são ordenados importa, e não os números absolutos das preferências.
manter todos os candidatos sem ordem. Quando um eleitor não ordena todos os candidatos, então é interpretado como se o eleitor (i) prefere estritamente todos os candidatos ordenados a todos os candidatos não ordenados, bem como (ii) é indiferente entre todos os candidatos não ordenados.
Método Schulze
Defina d[V,W] como o número de eleitores que preferem o candidato V ao candidato W.
Um trajeto do candidato X ao candidato Y de força p é um sequência de candidatos C(1),...,C(n) com as seguintes propriedades:
C(1) = X e C(n) = Y.
Para todo i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
Para todo i = 1,...,(n-1): d[C(i),C(i+1)] ≥ p.
p[A,B], a força do trajeto mais forte do candidato A ao candidato B, é o valor máximo tal que não há nenhum trajeto do candidato A para o candidato B dessa força. Se não há absolutamente nenhum trajeto do candidato A ao candidato B, então p[A,B] = 0.
O candidato D é melhor do que o candidato E se e somente se p[D,E] > p[E,D].
O candidate D é um vencedor em potencial se e somente se p[D,E] ≥ p[E,D] para cada outro candidato E.
Pode ser provado que p[X,Y] > p[Y,X] e p[Y,Z] > p[Z,Y] conjuntamente implicam p[X,Z] > p[Z,X].[1]:§4.1 Logo, é garantido (1) que a definição acima de "melhor" realmente define uma relação transitiva e (2) que sempre há pelo menos um candidato D com p[D,E] ≥ p[E,D] para cada outro candidato E.
Exemplo Lakehead vs. Thunder Bay
O novo nome da cidade fusão entre Fort William e Port Arthur foi determinado por um plebiscito. A cédula continha três possibilidades, "Thunder Bay" obteve 15.870, "Lakehead" 15.302, e "The Lakehead" 8.377 votos. Os votos divididos entre os clones (ex. bem similares) "Lakehead" e "The Lakehead", e Thunder Bay ganharam.
Usando o método Schulze uma ordenação foi aplicada e Lakehead teria ganhado.
Para ilustrar melhor, nós acompanhando a seguinte votação provável:
15.870 Thunder Bay - Lakehead - The Lakehead
15.302 Lakehead - The Lakehead - Thunder Bay
8.377 The Lakehead - Lakehead - Thunder Bay
Matriz Emparelhada
Uma tabela que compara cada candidato com cada outro. Os campos vermelhos conseguem chegar ao próximo passo. Por exemplo candidato "Lakehead" teria sigo preferido com 23000 votos contra "Thunder Bay".
d[*,Thunder Bay]
d[*,Lakehead]
d[*,The Lakehead]
d[Thunder Bay,*]
15870
15870
d[Lakehead,*]
23679
15302
d[The Lakehead,*]
23679
8377
Gráfico Emparelhado
Este aqui precisa ser desenhado ... mas ele contém os seguintes trajetos usando os campos vermelhos acima:
Thunder Bay --(23679)--> The Lakehead
Lakehead --(15302)--> The Lakehead
Lakehead --(23679)--> Thunder Bay
Os Trajetos Mais Fortes de Todos
De Thunder Bay para The Lakehead há apenas um trajeto direto, com 23679.
De Lakehead para Thunder Bay há apenas um trajeto via The Lakehead. Ambas ligações têm uma força de 23679, então a ligação mais fraca é 23679. Não há outro trajeto com uma ligação mais fraca o qual seria mais forte.
De Lakehead para The Lakehead há apenas um trajeto direto com 15302.
A ligação mais fraca dos trajetos mais fortes
d[*,Thunder Bay]
d[*,Lakehead]
d[*,The Lakehead]
d[Thunder Bay,*]
0
23679
d[Lakehead,*]
23679
15302
d[The Lakehead,*]
0
0
Resultado
Lakehead vence Thunder Bay e The Lakehead, enquanto Thunder Bay apenas vence The Lakehead. The Lakehead não vence ninguém. O vencedor é Lakehead.
Exemplo
Considere o seguinte exemplo, no qual 45 eleitores ordenam 5 candidatos.
5 ACBED (significando, 5 eleitores têm ordem de preferência: A > C > B > E > D)
5 ADECB
8 BEDAC
3 CABED
7 CAEBD
2 CBADE
7 DCEBA
8 EBADC
Primeiro, nós calculamos as preferências emparelhadas. Por exemplo, ao comparar A e B emparelhados, há 5+5+3+7=20 eleitores que preferem A em relação a B, e 8+2+7+8=25 eleitores que preferem B em relação a A. Então d[A, B] = 20 e d[B, A] = 25. O conjunto total das preferência emparelhadas é:
Matriz de preferências emparelhadas
d[*,A]
d[*,B]
d[*,C]
d[*,D]
d[*,E]
d[A,*]
20
26
30
22
d[B,*]
25
16
33
18
d[C,*]
19
29
17
24
d[D,*]
15
12
28
14
d[E,*]
23
27
21
31
Para ajudar a visualizar os trajetos mais fortes, o diagrama no lado direito mostra uma seta de A a B com rótulo d[A, B], no estilo de um gráfico orientado. (Para evitar tumultuar o diagrama nós só desenhados d[A, B] quando d[A, B] representa a maioria dos eleitores, o que parece não afetar o resultado neste caso.)
Lembre que força de um trajeto é a força de sua ligação mais fraca. Um exemplo de calcular o trajeto mais forte é p[B, D] = 33: o trajeto mais forte de B a D é o trajeto direto (B, D) que possui força 33. Para contraste, vamos também calcular p[A, C]. O trajeto mais forte de A a C não é o trajeto direto (A, C) de força 26, mas o trajeto mais forte é o trajeto indireto (A, D, C) que possui força min(30, 28) = 28.
Para cada par de candidatos X e Y, a seguinte tabela mostra o trajeto mais forte do candidato X ao candidato Y em vermelho, com a ligação mais fraca sublinhada.
Trajetos mais fortes
... para A
... para B
... para C
... para D
... para E
de A ...
A-(30)-D-(28)-C-(29)-B
A-(30)-D-(28)-C
A-(30)-D
A-(30)-D-(28)-C-(24)-E
de A ...
de B ...
B-(25)-A
B-(33)-D-(28)-C
B-(33)-D
B-(33)-D-(28)-C-(24)-E
de B ...
de C ...
C-(29)-B-(25)-A
C-(29)-B
C-(29)-B-(33)-D
C-(24)-E
de C ...
de D ...
D-(28)-C-(29)-B-(25)-A
D-(28)-C-(29)-B
D-(28)-C
D-(28)-C-(24)-E
de D ...
de E ...
E-(31)-D-(28)-C-(29)-B-(25)-A
E-(31)-D-(28)-C-(29)-B
E-(31)-D-(28)-C
E-(31)-D
de E ...
... para A
... para B
... para C
... para D
... para E
Forças dos trajetos mais fortes
p[*,A]
p[*,B]
p[*,C]
p[*,D]
p[*,E]
p[A,*]
28
28
30
24
p[B,*]
25
28
33
24
p[C,*]
25
29
29
24
p[D,*]
25
28
28
24
p[E,*]
25
28
28
31
Agora nós podemos determinar o resultado do método Schulze. Comparando A e B por exemplo,
como 28 = p[A,B] > p[B,A] = 25, para o método Schulze o candidato A é melhor do que o candidato B. Outro exemplo é que 31 = p[E,D] > p[D,E] = 24, então candidato E é melhor do que candidato D. Continuando neste caminho nós obtemos a classificação Schulze, que é E > A > C > B > D, e E vence. Em outras palavras, E vence já que p[E,X] ≥ p[X,E] para todo outros candidato X.
Implementação
A única etapa difícil na implementação do método Schulze é calcular as forças dos trajetos mais fortes. No entanto, esse é um problema bem conhecido na teoria dos grafos, às vezes chamado de problema do trajeto mais amplo. Logo, um modo simples de calcular as forças é a variante do algoritmo de Floyd-Warshall. O pseudocódigo a seguir ilustra o algoritmo.
# Entrada: d[i,j], o número de eleitores que preferem candidato i ao candidato j.# Saída: p[i,j], a força do trajeto mais forte do candidato i ao candidato j.forifrom1toCforjfrom1toCif(i<>j)thenif(d[i,j]>d[j,i])thenp[i,j]:=d[i,j]elsep[i,j]:=0forifrom1toCforjfrom1toCif(i<>j)thenforkfrom1toCif(i<>kandj<>k)thenp[j,k]:=max(p[j,k],min(p[j,i],p[i,k]))
Este algoritmo é eficiente, e possui tempo de execução proporcional a C3 onde C é o número de candidatos. (Isso não contabiliza pelo tempo de execução calculando os valores d[*,*], que se implementado na forma mais simples, possui tempo proporcional a C2 vezes o número de eleitores.)
Empates e implementações alternativas
Quando permitidos usuários a ter empates em suas preferências, o resultado do método Schulze naturalmente depende de como interpretamos estes empates ao definir d[*,*]. Duas escolhas naturais são que d[A, B] representa ou o número de eleitores que preferem terminantemente A em relação a B (A>B), ou a margem de (eleitores com A>B) menos (eleitores com B>A). Mas não importa como os ds são definidos, a ordenação Schulze não possui ciclos, e assumindo que os ds são únicos ele não possui empates.[1]
Muito embora empates na classificação Schulze sejam improváveis,[2] eles são possíveis. O artigo original do Schulze[1] propunha romper empates de acordo com um eleitor selecionado ao acaso, e repetindo conforme necessário.
Uma maneira alternativa, mais lenta, para descrever o vencedor do método Schulze é o seguinte procedimento:
desenhar um gráfico orientado completo com todos os candidatos, e todas as bordas possíveis entre candidatos
iterativamente [a] eliminar todos os candidatos que não façam parte do conjunto de Schwartz (ex. qualquer candidato que não pode alcançar todos os outros) e [b] elimina a ligação mais fraca
↑ abErro de citação: Etiqueta <ref> inválida; não foi fornecido texto para as refs de nome nb
↑Também chamado de Descartamento Sequencial Schwartz (Schwartz Sequential Dropping (SSD), no original), Descartamento Sequencial Schwartz Imune a Clones (Cloneproof Schwartz Sequential Dropping (CSSD), no original), Método do Trajeto Superador, Vencedor do Trajeto Superador, Votação Trajetória e Vencedor da Trajetória.
A principal diferente entre o método e o método pares ranqueados, ambos os quais possuem as mesmas caixas na tabela acima, podem ser vistas neste exemplo:
Supondo que a contagem MinMax de um conjunto X de candidatos é a força da vitória emparelhada mais forte de um candidato A ∉ X contra um candidato B ∈ X. Então o método Schulze, mas não o método de pares ranqueados, garante que o vencedor é sempre o candidato do conjunto com a mínima contagem MinMax.[1]:§4.8 Então, em algum sentido, o método Schulze minimiza a maior vitória emparelhada que precisa ser derrubada ao determinar o vencedor.
Em 2011, Schulze publicou o método no periódico acadêmico Social Choice and Welfare.[1]
Uso do método Schulze
O método Schulze não é atualmente utilizado em eleições parlamentares. No entanto, ele foi usado para as prévias palamentares no Partido Pirata sueco. Ele também está começando a receber apoio em outras organizações públicas. Organizações que utilizam o método Schulze atualmente:
Markus Schulze, Condorect sub-cycle rule, October 1997 (In this message, the Schulze method is mistakenly believed to be identical to the pares ranqueados method.)
↑
The MKM-IG uses Condorcet with dual dropping. That means: The Schulze ranking and the pares ranqueados ranking are calculated and the winner is the top-ranked candidate of that of these two rankings that has the better Kemeny score. Veja: