Loading AI tools
Da Wikipédia, a enciclopédia livre
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.
A tradução deste artigo está abaixo da qualidade média aceitável. (Setembro de 2021) |
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.
A entrada do método Schulze é a mesma utilizadas por outros métodos eletivos preferenciais de único vencedor: cada eleitor deve fornecer uma lista ordenada de preferencias sobre candidatos que permitem empates.
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
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:
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.
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:
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 |
Este aqui precisa ser desenhado ... mas ele contém os seguintes trajetos usando os campos vermelhos acima:
d[*,Thunder Bay] | d[*,Lakehead] | d[*,The Lakehead] | |
---|---|---|---|
d[Thunder Bay,*] | 0 | 23679 | |
d[Lakehead,*] | 23679 | 15302 | |
d[The Lakehead,*] | 0 | 0 |
Lakehead vence Thunder Bay e The Lakehead, enquanto Thunder Bay apenas vence The Lakehead. The Lakehead não vence ninguém. O vencedor é Lakehead.
Considere o seguinte exemplo, no qual 45 eleitores ordenam 5 candidatos.
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 é:
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.
... 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 |
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.
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.
for i from 1 to C
for j from 1 to C
if (i <> j) then
if (d[i,j] > d[j,i]) then
p[i,j] := d[i,j]
else
p[i,j] := 0
for i from 1 to C
for j from 1 to C
if (i <> j) then
for k from 1 to C
if (i <> k and j <> k) then
p[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.)
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:
O método Schulze satisfaz os seguintes critérios:
Uma vez que o método Schulze satisfaz o critério de Condorcet, ele automaticamente fracassa nos seguintes critérios:
Da mesma forma, já que o método Schulze não é uma ditadura e concorda com votos unânimes, o teorema de Arrow implica que ele fracassa no critério
A seguinte tabela compara o método Schulze com outros métodos eletivos preferenciais de único vencedor:
Comparação de Sistemas de Votação Preferencial de Ganhador Único | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Monotonico | Condorcet | Maioria | Perdedor de Condorcet | Perdedor de maioria | Mutual majority | Smith | IADS | ILAI | Clone independence | Simetria reversa | Participação, Consistência | Posterior-não-atrapalha | Posterior-não-ajuda | Tempo polinomial | Resolvabilidade | |
Schulze | Sim | Sim | Sim | Sim | Sim | Sim | Sim | Sim | Não | Sim | Sim | Não | Não | Não | Sim | Sim |
Pares Ranqueados | Sim | Sim | Sim | Sim | Sim | Sim | Sim | Sim | Sim | Sim | Sim | Não | Não | Não | Sim | Sim |
Smith alternativo | Não | Sim | Sim | Sim | Sim | Sim | Sim | Sim | Não | Sim | Não | Não | Não | Não | Sim | Sim |
Schwartz alternativo | Não | Sim | Sim | Sim | Sim | Sim | Sim | Sim | Não | Sim | Não | Não | Não | Não | Sim | Sim |
Kemeny-Young | Sim | Sim | Sim | Sim | Sim | Sim | Sim | Sim | Sim | Não | Sim | Não | Não | Não | Não | Sim |
Copeland | Sim | Sim | Sim | Sim | Sim | Sim | Sim | Sim | Não | Não | Sim | Não | Não | Não | Sim | Não |
Nanson | Não | Sim | Sim | Sim | Sim | Sim | Sim | Não | Não | Não | Sim | Não | Não | Não | Sim | Sim |
Instant-runoff voting | Não | Não | Sim | Sim | Sim | Sim | Não | Não | Não | Sim | Não | Não | Sim | Sim | Sim | Sim |
Borda | Sim | Não | Não | Sim | Sim | Não | Não | Não | Não | Não | Sim | Sim | Não | Sim | Sim | Sim |
Baldwin | Não | Sim | Sim | Sim | Sim | Sim | Sim | Não | Não | Não | Não | Não | Não | Não | Sim | Sim |
Bucklin | Sim | Não | Sim | Não | Sim | Sim | Não | Não | Não | Não | Não | Não | Não | Sim | Sim | Sim |
Pluralidade | Sim | Não | Sim | Não | Não | Não | Não | Não | Não | Não | Não | Sim | Sim | Sim | Sim | Sim |
Voto contingente | Não | Não | Sim | Sim | Sim | Não | Não | Não | Não | Não | Não | Não | Sim | Sim | Sim | Sim |
Coombs[n1 1] | Não | Não | Sim | Sim | Sim | Sim | Não | Não | Não | Não | Não | Não | Não | Não | Sim | Sim |
MiniMax | Sim | Sim | Sim | Não | Não | Não | Não | Não | Não | Não | Não | Não | Não | Não | Sim | Sim |
Anti-pluralidade[nota 1] | Sim | Não | Não | Não | Sim | Não | Não | Não | Não | Não | Não | Sim | Não | Não | Sim | Sim |
Sri Lankan | Não | Não | Sim | Não | Não | Não | Não | Não | Não | Não | Não | Não | Sim | Sim | Sim | Sim |
Suplementar | Não | Não | Sim | Não | Não | Não | Não | Não | Não | Não | Não | Não | Sim | Sim | Sim | Sim |
Dodgson[nota 1] | Não | Sim | Sim | Não | Não | Não | Não | Não | Não | Não | Não | Não | Não | Não | Não | Sim |
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.
O método Schulze foi desenvolvido por Markus Schulze em 1997. Ele foi primeiro discutido em listas de e-mail públicas em 1997–1998[4] e em 2000.[5] Subsequentemente, usuários do método Schulze incluíram Software in the Public Interest (2003),[6] Debian (2003),[7] Gentoo (2005),[8] TopCoder (2005),[9] Wikimedia (2008),[10] KDE (2008),[11] the Free Software Foundation Europe (2008),[12] the Partido Pirata da Suécia (2009),[13] e o Partido Pirata da Alemanha (2010).[14] Na Wikipédia Francófona, o método Schulze foi um dos dois métodos multi-candidatos aprovados por uma maioria em 2005,[15] e foi usando diversas vezes.[16]
Em 2011, Schulze publicou o método no periódico acadêmico Social Choice and Welfare.[1]
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:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.