Metric geometry for ranking-based voting: Tools for learning electoral structure

Resumo Técnico: Geometria Métrica para Votação Baseada em Rankings

Título Original: Metric Geometry for Ranking-Based Voting: Tools for Learning Electoral Structure
Autores: Moon Duchin e Kristopher Tapp

1. O Problema

O estudo de preferências em sistemas de votação por ranking enfrenta um desafio fundamental: a maioria das teorias de escolha social foca em rankings completos (onde todos os candidatos são ordenados), mas em eleições reais, os eleitores frequentemente utilizam rankings parciais (votos de "bullet" ou listas curtas).

Além disso, existe a necessidade de ferramentas descritivas para entender a estrutura de uma eleição, como a identificação de blocos de eleitores (grupos com preferências similares) e listas de candidatos (slates — grupos de candidatos que tendem a ser votados juntos), bem como a medição de polarização e proporcionalidade. O problema central é como estender as métricas de distância de rankings (como Kendall tau e Spearman) para o domínio de rankings parciais e como usar essa geometria para aprendizado não supervisionado de estruturas eleitorais.

2. Metodologia

Os autores desenvolvem um arcabouço geométrico baseado em duas abordagens principais para representar os votos em espaços métricos:

A. Embeddings de Coordenadas (Representação Vetorial):
Os autores propõem duas formas de mapear um boletim de voto ($\sigma$) em um espaço euclidiano ($\mathbb{R}^m$ ou $\mathbb{R}^{\binom{m}{2}}$):

1. Embedding de Borda ($b$): Atribui a cada candidato uma coordenada baseada na sua posição (usando a convenção "pessimista" para candidatos não mencionados, atribuindo-lhes pontuação zero). Isso permite recuperar a distância de Spearman footrule ($d_B$).
2. Embedding Head-to-Head ($h$): Mapeia cada par de candidatos para $\{-1, 0, 1\}$ dependendo de quem foi preferido. Isso permite recuperar a distância de Kendall tau ($d_H$).

B. Realizações em Grafos (Ballot Graphs):
Para lidar com a natureza discreta dos votos, os autores constroem grafos onde os nós são os possíveis boletins:

• Ballot Graph ($G_m$): Um grafo esparso onde as arestas representam trocas de vizinhos (neighbor swaps) ou extensões/truncamentos de listas. A métrica de caminho neste grafo recupera a distância $d_H$.
• Shortcut Ballot Graph ($G^+_m$): Adiciona arestas de "trocas gerais" (não apenas de vizinhos), cuja métrica de caminho recupera a distância $d_B$.
• Generalized Ballot Graphs: Uma extensão para lidar com empates (ties) e preferências entre conjuntos de candidatos (listas).

C. Algoritmos de Agrupamento (Clustering):

• Para Eleitores: Utilizam técnicas de partição como PAM (Partitioning Around Medoids) e k-means nos espaços de embedding para identificar centros de massa de preferências (blocos).
• Para Candidatos: Definem uma métrica de dissimilaridade entre candidatos ($D_B$) baseada na diferença média de seus rankings, permitindo o uso de agrupamento aglomerativo para formar listas (slates).

3. Principais Contribuições

1. Extensão Teórica: Prova que as métricas clássicas de estatística (Kendall e Spearman) se estendem naturalmente para rankings parciais e empates através de construções de grafos e embeddings.
2. Unificação de Métricas: Estabelece relações de equivalência bi-Lipschitz entre as métricas, provando que, em eleições suficientemente polarizadas, diferentes métodos de agrupamento produzirão resultados consistentes.
3. Ferramentas de Aprendizado: Introduz métodos robustos para identificar automaticamente blocos de eleitores e listas de candidatos sem depender de rótulos partidários prévios.
4. Formalização de Empates: Desenvolve o conceito de "convenção pessimista" para rankings parciais, que se mostra matematicamente superior para a construção de grafos em comparação à convenção de média.

4. Resultados e Validação

Os autores validaram o modelo de duas formas:

• Simulações Sintéticas: Utilizando modelos de Mallows, demonstraram que os algoritmos de agrupamento conseguem recuperar com precisão os centros de polarização e a estrutura de clusters, mesmo com tamanhos de grupos desequilibrados.
• Dados Reais (Eleições na Escócia): Analisaram mais de 1.000 eleições locais escocesas (2012-2022). Os resultados mostraram que:
  • Os métodos de agrupamento são altamente estáveis (independente da métrica $d_B$ ou $d_H$ usada).
  • O agrupamento de candidatos conseguiu identificar quase perfeitamente as coalizões partidárias existentes, mas também revelou estruturas interpartidárias (ex: a proximidade entre o SNP e os Verdes).
  • Em 73,5% das eleições, os centros de Borda e Kendall coincidiram perfeitamente para $k=2$.

5. Significância

O trabalho é significativo por transformar a teoria de escolha social de uma análise de "pior caso" (distorção métrica) para uma ferramenta de análise descritiva e aprendizado de máquina. Ele fornece uma base matemática rigorosa para que cientistas políticos e cientistas de dados possam visualizar a polarização, medir a proporcionalidade e entender a estrutura invisível de preferências em sistemas de votação complexos, tratando o boletim de voto não apenas como um dado ordinal, mas como um ponto em um espaço geométrico estruturado.