Método Kemeny-Young - Kemeny–Young method

O método Kemeny-Young é um sistema eleitoral que usa cédulas preferenciais e contagens de comparação entre pares para identificar as escolhas mais populares em uma eleição. É um método Condorcet porque se houver um vencedor do Condorcet, ele sempre será classificado como a escolha mais popular.

Este método atribui uma pontuação para cada sequência possível, em que cada sequência considera qual escolha pode ser a mais popular, qual opção pode ser a segunda mais popular, qual opção pode ser a terceira mais popular e assim por diante até qual opção pode ser a menos popular. A sequência com maior pontuação é a sequência vencedora, e a primeira escolha na sequência vencedora é a escolha mais popular. (Conforme explicado abaixo, empates podem ocorrer em qualquer nível de classificação.)

O método Kemeny-Young também é conhecido como regra de Kemeny , classificação de popularidade VoteFair , método de máxima verossimilhança e relação mediana .

Descrição

O método Kemeny-Young usa cédulas preferenciais nas quais os eleitores classificam as escolhas de acordo com sua ordem de preferência. Um eleitor pode classificar mais de uma escolha no mesmo nível de preferência. As escolhas não classificadas são geralmente interpretadas como menos preferidas.

Outra forma de visualizar a ordenação é aquela que minimiza a soma das distâncias tau de Kendall ( distância de classificação de bolha ) com as listas de eleitores.

Os cálculos de Kemeny-Young geralmente são feitos em duas etapas. O primeiro passo é criar uma matriz ou tabela que conte as preferências dos eleitores aos pares. A segunda etapa é testar todas as classificações possíveis , calcular uma pontuação para cada uma delas e comparar as pontuações. Cada pontuação de classificação é igual à soma das contagens de pares que se aplicam a essa classificação.

A classificação com a maior pontuação é identificada como a classificação geral. (Se mais de uma classificação tiver a mesma pontuação mais alta, todas essas classificações possíveis estão empatadas e, normalmente, a classificação geral envolve um ou mais empates.)

Para demonstrar como uma ordem de preferência individual é convertida em uma tabela de contagem, vale a pena considerar o exemplo a seguir. Suponha que um único eleitor tenha uma escolha entre quatro candidatos (ou seja, Elliot, Meredith, Roland e Selden) e tenha a seguinte ordem de preferência:

Ordem de preferência	Escolha
Primeiro	Elliot
Segundo	Roland
Terceiro	Meredith ou Selden (preferência igual)

Essas preferências podem ser expressas em uma tabela de contagem. Uma tabela de contagem, que organiza todas as contagens aos pares em três colunas, é útil para contar as preferências de voto (contagem) e calcular as pontuações da classificação. A coluna central rastreia quando um eleitor indica mais de uma escolha no mesmo nível de preferência. A ordem de preferência acima pode ser expressa como a seguinte tabela de contagem:

Todos os pares possíveis de nomes de escolha	Número de votos com preferência indicada
Todos os pares possíveis de nomes de escolha	Prefira X a Y	Preferência igual	Prefira Y em vez de X
X = Selden Y = Meredith	0	+1 voto	0
X = Selden Y = Elliot	0	0	+1 voto
X = Selden Y = Roland	0	0	+1 voto
X = Meredith Y = Elliot	0	0	+1 voto
X = Meredith Y = Roland	0	0	+1 voto
X = Elliot Y = Roland	+1 voto	0	0

Agora, suponha que vários eleitores tenham votado nesses quatro candidatos. Depois de todas as cédulas terem sido contadas, o mesmo tipo de tabela de contagem pode ser usado para resumir todas as preferências de todos os eleitores. Aqui está um exemplo de um caso que tem 100 eleitores:

Todos os pares possíveis de nomes de escolha	Número de votos com preferência indicada
Todos os pares possíveis de nomes de escolha	Prefira X a Y	Preferência igual	Prefira Y em vez de X
X = Selden Y = Meredith	50	10	40
X = Selden Y = Elliot	40	0	60
X = Selden Y = Roland	40	0	60
X = Meredith Y = Elliot	40	0	60
X = Meredith Y = Roland	30	0	70
X = Elliot Y = Roland	30	0	70

A soma das contagens em cada linha deve ser igual ao número total de votos.

Após a tabela de contagem ter sido completada, cada classificação possível de escolhas é examinada por sua vez, e sua pontuação de classificação é calculada adicionando o número apropriado de cada linha da tabela de contagem. Por exemplo, a possível classificação:

Elliot
Roland
Meredith
Selden

satisfaz as preferências Elliot> Roland, Elliot> Meredith, Elliot> Selden, Roland> Meredith, Roland> Selden e Meredith> Selden. As respectivas pontuações, retiradas da tabela, são

Elliot> Roland: 30
Elliot> Meredith: 60
Elliot> Selden: 60
Roland> Meredith: 70
Roland> Selden: 60
Meredith> Selden: 40

dando uma pontuação de classificação total de 30 + 60 + 60 + 70 + 60 + 40 = 320.

Calculando a classificação geral

Depois que as pontuações para cada classificação possível foram calculadas, a classificação que tem a maior pontuação pode ser identificada e se torna a classificação geral. Nesse caso, a classificação geral é:

Roland
Elliot
Selden
Meredith

com uma pontuação de 370 no ranking.

Se houver ciclos ou empates, mais de uma classificação possível pode ter a mesma maior pontuação. Os ciclos são resolvidos produzindo uma única classificação geral em que algumas das opções estão empatadas.

Matriz de resumo

Depois de calculada a classificação geral, as contagens de comparação entre pares podem ser organizadas em uma matriz de resumo, conforme mostrado abaixo, na qual as escolhas aparecem na ordem vencedora da mais popular (superior e esquerda) para a menos popular (inferior e direita). Este layout de matriz não inclui as contagens de pares de preferência igual que aparecem na tabela de contagem:

	... sobre Roland	... sobre Elliot	... sobre Selden	... sobre Meredith
Prefiro Roland ...	-	70	60	70
Prefiro Elliot ...	30	-	60	60
Prefiro Selden ...	40	40	-	50
Prefiro Meredith ...	30	40	40	-

Nesta matriz de resumo, a maior pontuação de classificação é igual à soma das contagens na metade triangular superior direita da matriz (mostrada aqui em negrito, com um fundo verde). Nenhuma outra classificação possível pode ter uma matriz de resumo que produza uma soma maior de números na metade superior direita triangular. (Se sim, essa seria a classificação geral.)

Nesta matriz de resumo, a soma dos números na metade triangular inferior esquerda da matriz (mostrada aqui com um fundo vermelho) é mínima. Os artigos acadêmicos de John Kemeny e Peyton Young referem-se a encontrar essa soma mínima, que é chamada de pontuação de Kemeny, e que se baseia em quantos eleitores se opõem (em vez de apoiar) cada ordem de pares:

Método	Vencedor do primeiro lugar
Kemeny – Young	Roland
Condorcet	Roland
Votação instantânea no segundo turno	Elliot ou Selden (dependendo de como o empate da segunda rodada é tratado)
Pluralidade	Selden

Exemplo

Imagine que o Tennessee esteja realizando uma eleição sobre a localização de sua capital . A população do Tennessee está concentrada em torno de suas quatro principais cidades, espalhadas por todo o estado. Para este exemplo, suponha que todo o eleitorado more nessas quatro cidades e que todos desejem morar o mais próximo possível da capital.

Os candidatos à capital são:

Memphis , maior cidade do estado, com 42% dos eleitores, mas localizada longe das demais cidades
Nashville , com 26% dos eleitores, perto do centro do estado
Knoxville , com 17% dos eleitores
Chattanooga , com 15% dos eleitores

As preferências dos eleitores seriam divididas assim:

42% dos eleitores (perto de Memphis)	26% dos eleitores (perto de Nashville)	15% dos eleitores (perto de Chattanooga)	17% dos eleitores (perto de Knoxville)
Memphis Nashville Chattanooga Knoxville	Nashville Chattanooga Knoxville Memphis	Chattanooga Knoxville Nashville Memphis	Knoxville Chattanooga Nashville Memphis

Esta matriz resume as contagens de comparação de pares correspondentes :

	... sobre Memphis	... sobre Nashville	... por Chattanooga	... sobre Knoxville
Prefiro Memphis ...	-	42%	42%	42%
Prefiro Nashville ...	58%	-	68%	68%
Prefere Chattanooga ...	58%	32%	-	83%
Prefiro Knoxville ...	58%	32%	17%	-

O método Kemeny-Young organiza as contagens de comparação de pares na seguinte tabela de contagem:

Todos os pares possíveis de nomes de escolha	Número de votos com preferência indicada
Prefira X a Y	Preferência igual	Prefira Y em vez de X
X = Memphis Y = Nashville	42%	0	58%
X = Memphis Y = Chattanooga	42%	0	58%
X = Memphis Y = Knoxville	42%	0	58%
X = Nashville Y = Chattanooga	68%	0	32%
X = Nashville Y = Knoxville	68%	0	32%
X = Chattanooga Y = Knoxville	83%	0	17%

A pontuação de classificação para a possível classificação de Memphis em primeiro, Nashville em segundo, Chattanooga em terceiro e Knoxville em quarto é igual a (o número sem unidade) 345, que é a soma dos seguintes números anotados.

42% (dos eleitores) preferem Memphis a Nashville

42% preferem Memphis a Chattanooga

42% preferem Memphis a Knoxville

68% preferem Nashville a Chattanooga

68% preferem Nashville a Knoxville

83% preferem Chattanooga a Knoxville

Esta tabela lista todas as pontuações de classificação:

Primeira escolha	Segunda escolha	Terceira escolha	Quarta escolha	Pontuação de classificação
Memphis	Nashville	Chattanooga	Knoxville	345
Memphis	Nashville	Knoxville	Chattanooga	279
Memphis	Chattanooga	Nashville	Knoxville	309
Memphis	Chattanooga	Knoxville	Nashville	273
Memphis	Knoxville	Nashville	Chattanooga	243
Memphis	Knoxville	Chattanooga	Nashville	207
Nashville	Memphis	Chattanooga	Knoxville	361
Nashville	Memphis	Knoxville	Chattanooga	295
Nashville	Chattanooga	Memphis	Knoxville	377
Nashville	Chattanooga	Knoxville	Memphis	393
Nashville	Knoxville	Memphis	Chattanooga	311
Nashville	Knoxville	Chattanooga	Memphis	327
Chattanooga	Memphis	Nashville	Knoxville	325
Chattanooga	Memphis	Knoxville	Nashville	289
Chattanooga	Nashville	Memphis	Knoxville	341
Chattanooga	Nashville	Knoxville	Memphis	357
Chattanooga	Knoxville	Memphis	Nashville	305
Chattanooga	Knoxville	Nashville	Memphis	321
Knoxville	Memphis	Nashville	Chattanooga	259
Knoxville	Memphis	Chattanooga	Nashville	223
Knoxville	Nashville	Memphis	Chattanooga	275
Knoxville	Nashville	Chattanooga	Memphis	291
Knoxville	Chattanooga	Memphis	Nashville	239
Knoxville	Chattanooga	Nashville	Memphis	255

A maior pontuação da classificação é 393, e essa pontuação está associada à seguinte classificação possível, portanto, esta classificação também é a classificação geral:

Ordem de preferência	Escolha
Primeiro	Nashville
Segundo	Chattanooga
Terceiro	Knoxville
Quarto	Memphis

Se um único vencedor for necessário, a primeira escolha, Nashville, é escolhida. (Neste exemplo, Nashville é a vencedora do Condorcet .)

A matriz de resumo abaixo organiza as contagens aos pares em ordem do mais popular (superior e esquerdo) ao menos popular (inferior e direito):

	... em Nashville ...	... por Chattanooga ...	... sobre Knoxville ...	... sobre Memphis ...
Prefiro Nashville ...	-	68%	68%	58%
Prefere Chattanooga ...	32%	-	83%	58%
Prefiro Knoxville ...	32%	17%	-	58%
Prefiro Memphis ...	42%	42%	42%	-

Nesse arranjo, a maior pontuação de classificação (393) é igual à soma das contagens em negrito, que estão na metade superior direita triangular da matriz (com um fundo verde).

Características

Em todos os casos que não resultam em um empate exato, o método Kemeny-Young identifica a escolha mais popular, a segunda escolha mais popular e assim por diante.

Um empate pode ocorrer em qualquer nível de preferência. Exceto em alguns casos em que ambigüidades circulares estão envolvidas, o método Kemeny-Young só produz um empate em um nível de preferência quando o número de eleitores com uma preferência corresponde exatamente ao número de eleitores com a preferência oposta.

Critérios satisfeitos para todos os métodos Condorcet

Todos os métodos Condorcet, incluindo o método Kemeny-Young, satisfazem estes critérios:

Não imposição: Existem preferências do eleitor que podem produzir todos os resultados gerais possíveis da ordem de preferência, incluindo empates em qualquer combinação de níveis de preferência.

Critério de Condorcet: Se houver uma escolha que vence todas as disputas de pares, essa escolha vence.

Critério de maioria: Se a maioria dos eleitores preferir estritamente a escolha X a todas as outras, a escolha X é identificada como a mais popular.

Não ditadura: Um único eleitor não pode controlar o resultado em todos os casos.

Critérios de satisfação adicionais

O método Kemeny-Young também satisfaz estes critérios:

Domínio irrestrito: Identifica a ordem geral de preferência para todas as opções. O método faz isso para todos os conjuntos possíveis de preferências do eleitor e sempre produz o mesmo resultado para o mesmo conjunto de preferências do eleitor.

Eficiência de Pareto: Qualquer preferência par a par expressa por cada eleitor resulta na escolha preferida sendo classificada em uma posição mais alta do que a escolha menos preferida.

Monotonicidade: Se os eleitores aumentam o nível de preferência de uma escolha, o resultado da classificação não muda ou a escolha promovida aumenta em popularidade geral.

Critério de Smith: A escolha mais popular é um membro do conjunto Smith , que é o menor conjunto não vazio de escolhas, de modo que cada membro do conjunto é preferido aos pares a cada escolha que não esteja no conjunto Smith.

Independência de alternativas dominadas por Smith: Se a opção X não estiver no conjunto Smith , adicionar ou retirar a opção X não altera o resultado em que a opção Y é identificada como a mais popular.

Reforço: Se todas as cédulas forem divididas em corridas separadas e a classificação geral para as corridas separadas for a mesma, então a mesma classificação ocorre quando todas as cédulas são combinadas.

Simetria reversa: Se as preferências em todas as cédulas forem invertidas, a escolha anteriormente mais popular não deve permanecer a mais popular.

Critérios de falha para todos os métodos de Condorcet

Em comum com todos os métodos de Condorcet, o método Kemeny-Young falha nesses critérios (o que significa que os critérios descritos não se aplicam ao método Kemeny-Young):

Independência de alternativas irrelevantes: Adicionar ou retirar a opção X não altera o resultado em que a opção Y é identificada como a mais popular.

Invulnerabilidade para enterrar: Um eleitor não pode deslocar uma escolha da mais popular dando à escolha uma classificação insinceravelmente baixa.

Invulnerabilidade ao compromisso: Um eleitor não pode fazer com que uma escolha se torne a mais popular atribuindo-lhe uma classificação insinceramente alta.

Participação: Adicionar cédulas que classificam a escolha X sobre a escolha Y nunca faz com que a escolha Y, em vez da escolha X, se torne a mais popular.

Mais tarde, sem danos: Classificar uma escolha adicional (que de outra forma não estava classificada) não pode impedir que uma escolha seja identificada como a mais popular.

Consistência: Se todas as cédulas forem divididas em corridas separadas e a escolha X for identificada como a mais popular em cada uma dessas corridas, então a escolha X é a mais popular quando todas as cédulas são combinadas.

Critérios de falha adicionais

O método Kemeny-Young também falha nesses critérios (o que significa que os critérios descritos não se aplicam ao método Kemeny-Young):

Independência de clones: Oferecer um número maior de opções semelhantes, em vez de oferecer apenas uma dessas opções, não altera a probabilidade de uma dessas opções ser identificada como a mais popular.

Invulnerabilidade para empurrar: Um eleitor não pode fazer com que a escolha X se torne a mais popular dando à escolha Y uma classificação insinceravelmente alta.

Schwartz: A escolha identificada como mais popular é um membro do conjunto de Schwartz.

Tempo de execução polinomial: Um algoritmo é conhecido para determinar o vencedor usando este método em um tempo de execução que é polinomial no número de escolhas.

Métodos de cálculo e complexidade computacional

Um algoritmo para calcular uma classificação de Kemeny-Young no polinômio do tempo no número de candidatos não é conhecido e é improvável que exista, uma vez que o problema é NP-difícil, mesmo se houver apenas 4 eleitores.

Foi relatado que os métodos de cálculo baseados na programação inteira às vezes permitiam o cálculo de classificações completas para votos em até 40 candidatos em segundos. No entanto, certas eleições de Quemeny com 5 eleitores e 40 candidatos geradas aleatoriamente não puderam ser resolvidas em um computador Pentium de 3 GHz em um período útil até 2006.

Observe que a complexidade do cálculo é dimensionada linearmente ao número de eleitores, de modo que o tempo necessário para processar um determinado conjunto de votos é dominado pelo número de candidatos e não pelo número de votos , limitando a importância dessa restrição para eleições onde os eleitores podem para efetivamente considerar significativamente mais do que os sete itens comuns da memória de trabalho .

O método Kemeny-Young pode ser formulado como uma instância de um problema mais abstrato, de encontrar conjuntos de arco de feedback ponderado em gráficos de torneio . Como tal, muitos métodos para o cálculo de conjuntos de arco de feedback podem ser aplicados a este problema, incluindo uma variante do algoritmo Held-Karp que pode calcular a classificação Kemeny-Young de candidatos no tempo , significativamente mais rápido para muitos candidatos do que o tempo fatorial de testar todas as classificações. Existe um esquema de aproximação de tempo polinomial para calcular uma classificação Kemeny-Young, e também existe um algoritmo de tempo subexponencial parametrizado com tempo de execução O ^* (2 ^{O (}^√^OPT⁾ ) para calcular tal classificação. ${\ displaystyle n}$ ${\ displaystyle O (n2 ^ {n})}$

História

O método Kemeny – Young foi desenvolvido por John Kemeny em 1959.

Em 1978, Peyton Young e Arthur Levenglick mostraram que este método era o único método neutro que satisfazia o reforço e uma versão do critério de Condorcet. Em outros artigos, Young adotou uma abordagem epistêmica para agregação de preferências: ele supôs que havia uma ordem de preferência objetivamente "correta", mas desconhecida, sobre as alternativas, e os eleitores recebem sinais ruidosos dessa ordem de preferência verdadeira (cf. teorema do júri de Condorcet . ) Usando um modelo probabilístico simples para esses sinais ruidosos, Young mostrou que o método Kemeny-Young era o estimador de máxima verossimilhança da verdadeira ordem de preferência. Young ainda argumenta que o próprio Condorcet estava ciente da regra de Kemeny-Young e de sua interpretação de probabilidade máxima, mas era incapaz de expressar claramente suas idéias.

Nos artigos de John Kemeny e Peyton Young, as pontuações de Kemeny usam contagens de quantos eleitores se opõem, em vez de apoiar, cada preferência pareada, mas a menor dessas pontuações identifica a mesma classificação geral.

Desde 1991, o método foi promovido sob o nome de "ranking de popularidade VoteFair" por Richard Fobes.

Tabela de comparação

A tabela a seguir compara o método Kemeny-Young com outros métodos de eleição de vencedor único preferencial :

Comparação de sistemas eleitorais preferenciais
Sistema	Monotônico	Condorcet	Maioria	Perdedor de Condorcet	Perdedor majoritário	Maioria mútua	Smith	ISDA	LIIA	Independência de clones	Simetria reversa	Participação , consistência	Mais tarde - sem danos	Mais tarde sem ajuda	Tempo polinomial	Capacidade de resolução
Schulze	sim	sim	sim	sim	sim	sim	sim	sim	Não	sim	sim	Não	Não	Não	sim	sim
Pares classificados	sim	sim	sim	sim	sim	sim	sim	sim	sim	sim	sim	Não	Não	Não	sim	sim
Ciclo Dividido	sim	sim	sim	sim	sim	sim	sim	sim	Não	sim	sim	Não	Não	Não	sim	Não
Alternativa do Tideman	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
Preto	sim	sim	sim	sim	sim	Não	Não	Não	Não	Não	sim	Não	Não	Não	sim	sim
Votação instantânea	Não	Não	sim	sim	sim	sim	Não	Não	Não	sim	Não	Não	sim	sim	sim	sim
Smith / IRV	Não	sim	sim	sim	sim	sim	sim	sim	Não	sim	Não	Não	Não	Não	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
Geller-IRV	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
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
Votação 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	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	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
Votação contingente do Sri Lanka	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
Votação complementar	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	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

links externos

VoteFair.org - Um site que calcula os resultados do Kemeny – Young. Para efeito de comparação, também calcula o vencedor de acordo com a pluralidade, Condorcet, contagem de Borda e outros métodos de votação.
VoteFair_Ranking.cpp - Programa C ++, disponível no GitHub sob a licença MIT, que calcula os resultados do ranking VoteFair, que incluem cálculos Condorcet-Kemeny.
Biblioteca Condorcet Class PHP com suporte a vários métodos Condorcet, incluindo o método Kemeny – Young.
Programa C ++ para Kemeny-Young Preference Aggregation - Programa de linha de comando para cálculo rápido dos resultados Kemeny-Young, como código-fonte e binários compilados para Windows e Linux. Open source, exceto usa receitas numéricas .
Programa C para Agregação de Preferências Kemeny-Young - implementa o algoritmo de Davenport sem outras dependências de biblioteca. Código aberto, com licença LGPL. Uma vinculação Ruby à biblioteca também é de código aberto, com licença LPGL.
Kemeny-Young Optimal Rank Aggregation em Python - Tutorial que usa uma formulação simples como um programa inteiro e é adaptável a outras linguagens com ligações para lpsolve.

Languages

In other projects