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

Riassunto Tecnico: Geometria Metrica per il Voto Basato su Classifiche

1. Il Problema

Il problema centrale affrontato dai ricercatori è la mancanza di un quadro teorico e computazionale robusto per analizzare le elezioni basate su classifiche (ranked-choice elections) quando i voti sono incompleti (ballot parziali). Nella teoria della scelta sociale computazionale, molti modelli assumono preferenze complete, ma nelle elezioni reali gli elettori spesso indicano solo i primi $k$ candidati.

L'obiettivo è sviluppare una geometria metrica che permetta di:

• Estendere le distanze statistiche classiche (Kendall tau e Spearman footrule) alle classifiche parziali.
• Identificare in modo oggettivo i blocchi di elettori (voter blocs) e le liste di candidati (candidate slates) preferite.
• Fornire strumenti per misurare la polarizzazione e la proporzionalità senza fare affidamento su etichette politiche preesistenti (party labels).

2. Metodologia

Gli autori sviluppano due approcci complementari per rappresentare le preferenze in uno spazio metrico:

A. Embedding Coordinati (Coordinate Embeddings):
Vengono definiti due modi per mappare una scheda elettorale ($\sigma$) in uno spazio vettoriale $\mathbb{R}^m$:

1. Embedding di Borda ($b$): Assegna a ogni candidato un punteggio basato sulla sua posizione. Per gestire le schede parziali, viene utilizzata la convenzione pessimistica: i candidati non menzionati ricevono 0 punti. La distanza di Borda ($d_B$) è definita come metà della distanza $L_1$ tra i vettori di punteggio.
2. Embedding Head-to-Head ($h$): Mappa la scheda in uno spazio $\mathbb{R}^{\binom{m}{2}}$ dove ogni coordinata rappresenta un confronto a due a due ($\pm 1$ per vittoria/sconfitta, $0$ per pareggio). La distanza $d_H$ è metà della distanza $L_1$ tra questi vettori, recuperando la distanza di Kendall tau.

B. Realizzazioni su Grafi (Ballot Graphs):
Gli autori costruiscono grafi in cui i nodi sono le possibili schede elettorali:

• Ballot Graph ($G_m$): Un grafo dove gli archi rappresentano scambi di vicini (neighbor swaps) o estensioni/troncamenti di schede. La metrica del cammino in questo grafo corrisponde a $d_H$.
• Shortcut Ballot Graph ($G^+_m$): Introduce "scorciatoie" (scambi non adiacenti) per recuperare la metrica di Borda ($d_B$).
• Generalized Ballot Graphs: Estensioni che permettono di gestire i pareggi (ties) tra gruppi di candidati.

C. Tecniche di Clustering:

• Per gli elettori: Utilizzo di algoritmi di clustering (come $k$-means o PAM - Partitioning Around Medoids) nello spazio delle coordinate per raggruppare schede simili.
• Per i candidati: Definizione di una metrica di dissimilarità tra candidati ($D_B$) basata sulla differenza media di rango, permettendo di raggrupparli in "slates" (liste) tramite clustering gerarchico o basato su centri.

3. Contributi Chiave

1. Estensione Metrica: Dimostrazione che le distanze di Kendall tau e Spearman si estendono naturalmente alle classifiche parziali tramite grafi e embedding, mantenendo proprietà matematiche fondamentali.
2. Teorema di Stabilità della Classificazione: Dimostrazione che in elezioni sufficientemente polarizzate, il clustering ottimale è unico e stabile anche se si cambia la metrica (entro limiti di bi-Lipschitz equivalence).
3. Unificazione dei Framework: Connessione tra la teoria delle preferenze metriche (distorsione), la misura della polarizzazione e la proporzionalità attraverso la geometria delle classifiche.

4. Risultati

Il paper valida i metodi attraverso due canali:

• Validazione Sintetica: Utilizzando modelli di Mallows misti, gli autori dimostrano che i loro algoritmi di clustering identificano correttamente i centri e i gruppi di elettori anche in presenza di cluster sbilanciati.
• Elezioni Reali (Scozia): Analizzando oltre 1000 elezioni locali scozzesi (2012-2022), i risultati mostrano che:
  • I metodi di clustering sono estremamente robusti: diverse scelte di embedding e algoritmi producono raggruppamenti quasi identici.
  • I metodi sono "party-agnostic": riescono a ricostruire le coalizioni politiche esistenti (es. SNP e Verdi) senza conoscere le etichette dei partiti, scoprendo strutture inter-partitiche non ovvie.
  • Esiste un alto grado di accordo tra la regola di Borda e la regola di Kemeny (Condorcet-consistente) anche con schede parziali.

5. Significato e Implicazioni

Il lavoro fornisce un toolkit matematico per la scelta sociale computazionale. La capacità di gestire schede parziali rende questi metodi applicabili alla democrazia reale. La metodologia permette di trasformare dati elettorali grezzi in mappe geometriche interpretabili, consentendo ai ricercatori di quantificare scientificamente la polarizzazione di una società e di valutare se un sistema elettorale sia proporzionale rispetto ai blocchi di elettori effettivamente formati sul territorio.