Método de Schulze

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa


O método Schulze é um Sistema de votação desenvolvido em 1997 por Markus Schulze para selecionar um único vencedor usando votos que expressam preferencias. O método ṕode também ser usado para criar listas ordenadas de vencedores.

O método Schulze também é conhecido como Descartamento Sequencial Schwartz (em inglês: Schwartz Sequential Dropping (SSD)), Descartamento Sequencial Schwartz Imune a Clones (em inglês: Cloneproof Schwartz Sequential Dropping CSSD), o Método do Trajeto Superador, Vencedor do Trajeto Superador, Votação Trajetória, e Vencedor da Trajetória.

O método Schulze é um método de Condorcet, significando o seguinte: se há um candidato que é preferido a todo outro candidato em comparações emparelhadas, então este candidato será o vencedor quando o método Schulze está em aplicação.

Atualmente, o método Schulze é o método Condorcet mais disseminado (lista). O método Schulze é usado por diversas organizações incluindo Wikimedia, Debian, Gentoo, e Software in the Public Interest.

O resultado do método Schulze, definido abaixo, 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, para eleições de representação proporcional, uma variação de voto individual transferível foi proposta.

Descrição do método[editar | editar código-fonte]

Cédula eleitoral[editar | editar código-fonte]

Preferential ballot.svg

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

  • 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[editar | editar código-fonte]

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:

  1. C(1) = X e C(n) = Y.
  2. Para todo i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
  3. 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

  • 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[editar | editar código-fonte]

d[*,Thunder Bay] d[*,Lakehead] d[*,The Lakehead]
d[Thunder Bay,*] 0 23679
d[Lakehead,*] 23679 15302
d[The Lakehead,*] 0 0

Resultado[editar | editar código-fonte]

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[editar | editar código-fonte]

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 é:

Gráfico orientado rotulado com preferências emparelhadas d[*, *]
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 ...
Schulze method example1 AB.svg
A-(30)-D-(28)-C-(29)-B
Schulze method example1 AC.svg
A-(30)-D-(28)-C
Schulze method example1 AD.svg
A-(30)-D
Schulze method example1 AE.svg
A-(30)-D-(28)-C-(24)-E
de A ...
de B ...
Schulze method example1 BA.svg
B-(25)-A
Schulze method example1 BC.svg
B-(33)-D-(28)-C
Schulze method example1 BD.svg
B-(33)-D
Schulze method example1 BE.svg
B-(33)-D-(28)-C-(24)-E
de B ...
de C ...
Schulze method example1 CA.svg
C-(29)-B-(25)-A
Schulze method example1 CB.svg
C-(29)-B
Schulze method example1 CD.svg
C-(29)-B-(33)-D
Schulze method example1 CE.svg
C-(24)-E
de C ...
de D ...
Schulze method example1 DA.svg
D-(28)-C-(29)-B-(25)-A
Schulze method example1 DB.svg
D-(28)-C-(29)-B
Schulze method example1 DC.svg
D-(28)-C
Schulze method example1 DE.svg
D-(28)-C-(24)-E
de D ...
de E ...
Schulze method example1 EA.svg
E-(31)-D-(28)-C-(29)-B-(25)-A
Schulze method example1 EB.svg
E-(31)-D-(28)-C-(29)-B
Schulze method example1 EC.svg
E-(31)-D-(28)-C
Schulze method example1 ED.svg
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[editar | editar código-fonte]

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 gráficos, à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 seguinte pseudocódigo ilustra o algoritmo.

  1. # Entrada: d[i,j], o número de eleitores que preferem candidato i ao candidato j.
    
  2. # Saída: p[i,j], a força do trajeto mais forte do candidato i ao candidato j.
    
  3.  
    
  4. for i from 1 to C
    
  5.    for j from 1 to C
    
  6.       if (i <> j) then
    
  7.          if (d[i,j] > d[j,i]) then
    
  8.             p[i,j] := d[i,j]
    
  9.          else
    
  10.             p[i,j] := 0
    
  11.  
    
  12. for i from 1 to C
    
  13.    for j from 1 to C
    
  14.       if (i <> j) then
    
  15.          for k from 1 to C
    
  16.             if (i <> k and j <> k) then
    
  17.                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.)

Empates e implementações alternativas[editar | editar código-fonte]

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:

  1. desenhar um gráfico orientado completo com todos os candidatos, e todas as bordas possíveis entre candidatos
  2. 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
  3. o vencedor é o último candidato não-eliminado

Critérios satisfeitos e fracassados[editar | editar código-fonte]

Critérios satisfeitos[editar | editar código-fonte]

O método Schulze satisfaz os seguintes critérios:

Critérios fracassados[editar | editar código-fonte]

Uma vez que o método Schulze satisfaz o Condorcet criterion, 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

Tabela de comparação[editar | editar código-fonte]

A seguinte tabela compara o método Schulze com outros métodos eletivos preferenciais de único vencedor:

Monotonic Condorcet Majority Condorcet loser Majority loser Mutual majority Smith ISDA Clone independence Reversal symmetry Polynomial time Participation, Consistency
Schulze Sim Sim Sim Sim Sim Sim Sim Sim Sim Sim Sim Não
Ranked pairs Sim Sim Sim Sim Sim Sim Sim Sim Sim Sim Sim Não
Kemeny-Young Sim Sim Sim Sim Sim Sim Sim Sim Não Sim Não Não
Nanson Não Sim Sim Sim Sim Sim Sim Não Não Sim Sim Não
Baldwin Não Sim Sim Sim Sim Sim Sim Não Não Não Sim Não
Instant-runoff voting Não Não Sim Sim Sim Sim Não Não Sim Não Sim Não
Borda Sim Não Não Sim Sim Não Não Não Não Sim Sim Sim
Bucklin Sim Não Sim Não Sim Sim Não Não Não Não Sim Não
Coombs Não Não Sim Sim Sim Sim Não Não Não Não Sim Não
MiniMax Sim Sim Sim Não Não Não Não Não Não Não Sim Não
Plurality Sim Não Sim Não Não Não Não Não Não Não Sim Sim
Anti-plurality Sim Não Não Não Sim Não Não Não Não Não Sim Sim
Contingent voting Não Não Sim Sim Sim Não Não Não Não Não Sim Não
Sri Lankan contingent voting Não Não Sim Não Não Não Não Não Não Não Sim Não
Supplementary voting Não Não Sim Não Não Não Não Não Não Não Sim Não
Dodgson Não Sim Sim Não Não Não Não Não Não Não Não Não

A principal diferente entre o método e o método ranked pairs, 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 ranked pairs, 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.

História do método Schulze[editar | editar código-fonte]

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]

Uso do método Schulze[editar | editar código-fonte]

cédula de exemplo para as eleições do Conselho Administratido da Wikimedia

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:

Notas[editar | editar código-fonte]

  1. a b c d e f g h i j k l m n Markus Schulze, A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method, Social Choice and Welfare, volume 36, number 2, page 267–303, 2011. Preliminary version in Voting Matters, 17:9-19, 2003.
  2. Sob hipótese probabilística razoável quando o número de eleitores é muito superior ao número de candidatos
  3. a b c Douglas R. Woodall, Properties of Preferential Election Rules, Voting Matters, issue 3, pages 8-15, December 1994
  4. Veja:
  5. Veja:
  6. a b Process for adding new board members, January 2003
  7. a b Veja:
  8. a b Veja:
  9. a b Veja:
  10. a b Veja:
  11. a b section 3.4.1 of the Rules of Procedures for Online Voting
  12. a b Veja:
  13. a b Veja:
  14. a b 11 das 16 seções regionais e a seção federal do Partido Pirata da Alemanha estão usando LiquidFeedback para desvincular apurar votos de opiniões internas. Em 2010/2011, os Partidos Piradas de Neukölln (link), Mitte (link), Steglitz-Zehlendorf (link), Lichtenberg (link), and Tempelhof-Schöneberg (link) adotaram o método Schulze para suas eleições prévias. Em 2011, o Partido Piara de Berlin adotou este método para suas prévias (link).
  15. a b Choix dans les votes
  16. fr:Spécial:Pages liées/Méthode Schulze
  17. Election of the Annodex Association committee for 2007, February 2007
  18. Condorcet method for admin voting, January 2005
  19. Veja:
  20. Project Logo, October 2009
  21. Codex Alpe Adria Competitions. 0xaa.org (2010-01-24). Página visitada em 2010-05-08.
  22. Fellowship Guidelines (PDF). Página visitada em 2011-06-01.
  23. Report on HackSoc Elections, December 2008
  24. Adam Helman, Family Affair Voting Scheme - Schulze Method
  25. appendix 1 of the constitution
  26. Logo Competition, May 2009
  27. Veja:
  28. Guidance Document. Eudec.org (2009-11-15). Página visitada em 2010-05-08.
  29. article XI section 2 of the bylaws
  30. Democratic election of the server admins, July 2010
  31. article 51 of the statutory rules
  32. Veja:
  33. GnuPG Logo Vote, November 2006
  34. §14 of the bylaws
  35. User Voting Instructions. Gso.cs.binghamton.edu. Página visitada em 2010-05-08.
  36. Haskell Logo Competition, March 2009
  37. A club by any other name ..., April 2009
  38. Veja:
  39. Knight Foundation awards $5000 to best created-on-the-spot projects, June 2009
  40. Veja:
  41. article 8.3 of the bylaws
  42. Veja:
  43. Lumiera Logo Contest, January 2009
  44. The MKM-IG uses Condorcet with dual dropping. That means: The Schulze ranking and the ranked pairs ranking are calculated and the winner is the top-ranked candidate of that of these two rankings that has the better Kemeny score. Veja:
  45. Wahlmodus (em (em alemão)). Metalab.at. Página visitada em 2010-05-08.
  46. Benjamin Mako Hill, Voting Machinery for the Masses, July 2008
  47. Veja:
  48. Veja:
  49. 2009 Director Elections
  50. NSC Jersey election, NSC Jersey vote, September 2007
  51. Online Voting Policy
  52. 2010 OpenStack Community Election, November 2010
  53. Voting Procedures. Parkscholars.org. Página visitada em 2010-05-08.
  54. §6(10) of the bylaws
  55. 23 January 2011 meeting minutes
  56. Piratenversammlung der Piratenpartei Schweiz, September 2010
  57. 2006 Community for Pittsburgh Ultimate Board Election, September 2006
  58. LogoVoting, December 2007
  59. Veja:
  60. Squeak Oversight Board Election 2010, March 2010
  61. Veja:
  62. Election status update, September 2009
  63. See this mail.
  64. Veja:
  65. Veja ex. aqui (Maio de 2009), aqui (Agosto de 2009), e aqui (Dezembro de 2009).
  66. Veja aqui e aqui.
  67. Veja:

Ligações externas[editar | editar código-fonte]

Commons
O Commons possui imagens e outras mídias sobre Método de Schulze

Geral[editar | editar código-fonte]

Tutórios[editar | editar código-fonte]

Apoio[editar | editar código-fonte]

Livros[editar | editar código-fonte]

Software[editar | editar código-fonte]

Projetos legislativos[editar | editar código-fonte]