Método de Schulze

O método Schulze é 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 Cédula eleitoral 140px|left|thumb 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 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]. 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.

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

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

Muito embora empates na classificação Schulze sejam improváveis,Sob hipótese probabilística razoável quando o número de eleitores é muito superior ao número de candidatos eles são possíveis. O artigo original do Schulze 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 o vencedor é o último candidato não-eliminado

Critérios satisfeitos e fracassados Critérios satisfeitos O método Schulze satisfaz os seguintes critérios:

Unrestricted domain Não-imposição (conhecido como soberania cidadã) Non-dictatorship Critério de Pareto Monotonicity criterion Majority criterion Majority loser criterion Critério de Condorcet Condorcet loser criterion Schwartz criterion Smith criterion Independence of Smith-dominated alternatives Mutual majority criterion Independence of clones Reversal symmetry Mono-appendDouglas R. Woodall, Properties of Preferential Election Rules, Voting Matters, issue 3, pages 8-15, December 1994 Mono-add-plump Resolvability criterion Polynomial runtime Woodall's plurality criterion if winning votes are used for d[X,Y] Symmetric-completion if margins are used for d[X,Y]

Critérios fracassados Uma vez que o método Schulze satisfaz o critério de Condorcet, ele automaticamente fracassa nos seguintes critérios: Participation Consistency Invulnerabilidade ao comprometimento

Método de Schulze

Źródło i licencja