Método de Schulze

Origem: 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.

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.

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

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

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 ...
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[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 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.)

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

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:

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

Notas

  1. ↑ a b Erro de citação: Etiqueta <ref> inválida; não foi fornecido texto para as refs de nome nb
  1. ↑ 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.

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

  1. ↑ {{{1}}}

Referências

  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 Arquivado em 19 de julho de 2011, no Wayback Machine.), 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 Arquivado em 26 de abril de 2005, no Wayback Machine., January 2005
  19. ↑ Veja:
  20. ↑ Project Logo Arquivado em 3 de outubro de 2015, no Wayback Machine., October 2009
  21. ↑ «Codex Alpe Adria Competitions». 0xaa.org. 24 de janeiro de 2010. Consultado em 8 de maio de 2010 
  22. ↑ «Fellowship Guidelines» (PDF). Consultado em 1 de junho de 2011. Arquivado do original (PDF) em 28 de setembro de 2011 
  23. ↑ Report on HackSoc Elections Arquivado em 26 de julho de 2011, no Wayback Machine., December 2008
  24. ↑ Adam Helman, Family Affair Voting Scheme - Schulze Method
  25. ↑ appendix 1 of the constitution Arquivado em 18 de julho de 2011, no Wayback Machine.
  26. ↑ Logo Competition, May 2009
  27. ↑ Veja:
  28. ↑ «Guidance Document». Eudec.org. 15 de novembro de 2009. Consultado em 8 de maio de 2010. Arquivado do original em 20 de julho de 2011 
  29. ↑ article XI section 2 of the bylaws Arquivado em 26 de julho de 2011, no Wayback Machine.
  30. ↑ Democratic election of the server admins, July 2010
  31. ↑ article 51 of the statutory rules Arquivado em 24 de março de 2012, no Wayback Machine.
  32. ↑ Veja:
  33. ↑ GnuPG Logo Vote Arquivado em 16 de dezembro de 2006, no Wayback Machine., November 2006
  34. ↑ §14 of the bylaws Arquivado em 29 de abril de 2010, no Wayback Machine.
  35. ↑ «User Voting Instructions». Gso.cs.binghamton.edu. Consultado em 8 de maio de 2010. Arquivado do original em 2 de fevereiro de 2013 
  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 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:
  45. ↑ «Wahlmodus» (em (em alemão)). Metalab.at. Consultado em 8 de maio de 2010 
  46. ↑ Benjamin Mako Hill, Voting Machinery for the Masses, July 2008
  47. ↑ Veja:
  48. ↑ Veja:
  49. ↑ 2009 Director Elections
  50. ↑ NSC Jersey election Arquivado em 26 de março de 2009, no Wayback Machine., NSC Jersey vote, September 2007
  51. ↑ Online Voting Policy
  52. ↑ 2010 OpenStack Community Election, November 2010
  53. ↑ «Voting Procedures». Parkscholars.org. Consultado em 8 de maio de 2010. Arquivado do original em 13 de abril de 2013 
  54. ↑ §6(10) of the bylaws Arquivado em 6 de julho de 2011, no Wayback Machine.
  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 Arquivado em 13 de junho de 2010, no Wayback Machine., 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
Commons
O Commons possui imagens e outros ficheiros 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]

Obtida de "https://pt.wikipedia.org/w/index.php?title=Método_de_Schulze&oldid=64154648"