Reti, Voti e la Magia della Coerenza: Svelando la Regola di Borda (e Molto Altro!)

Ciao a tutti! Oggi voglio portarvi con me in un viaggio affascinante, un’avventura intellettuale che mi ha recentemente catturato. Immaginate di poter trovare un legame nascosto, una sorta di codice segreto, che collega mondi apparentemente distanti come le classifiche sportive, l’analisi dei social network e… le elezioni politiche! Sembra fantascienza? Beh, tenetevi forte, perché la matematica, ancora una volta, ci regala sorprese incredibili.

Tutto parte da un nome noto agli appassionati di teoria della scelta sociale: H. Peyton Young. Nel lontano 1974, Young fece qualcosa di straordinario: dimostrò che un famoso sistema di voto, la Regola di Borda, non era solo un metodo tra tanti, ma l’unico a soddisfare alcune proprietà fondamentali, considerate desiderabili per un sistema “giusto”. Proprietà come la neutralità (il nome dei candidati non deve influenzare il risultato), la consistenza (se due gruppi separati di elettori concordano su un vincitore comune, quel vincitore deve essere scelto anche quando i gruppi votano insieme) e la cancellazione (se le preferenze si annullano a vicenda, tutti i candidati dovrebbero essere considerati alla pari).

Recentemente, mi sono imbattuto in un lavoro di ricerca che prende questa idea elegante e la spinge oltre, generalizzandola a un contesto molto più ampio: quello delle reti. Ed è qui che la storia si fa davvero intrigante.

Cos’è una Rete, in Questo Contesto?

Quando parlo di “reti”, non intendo solo Facebook o Twitter. In matematica, una rete è un concetto più astratto:

• Abbiamo un insieme di “nodi” o “vertici” (che possono rappresentare squadre, persone, alternative politiche, pagine web…).
• Abbiamo delle “connessioni” o “archi” tra questi nodi (che possono rappresentare partite giocate, amicizie, preferenze, link…).
• A queste connessioni associamo un “peso” o “capacità”, un numero che quantifica l’intensità o la direzione della relazione (ad esempio, il numero di goal segnati, il numero di volte che un candidato è preferito a un altro, ecc.).

Pensate a un campionato di calcio: le squadre sono i nodi, le partite giocate sono gli archi e il numero di vittorie di una squadra contro un’altra è la capacità. Oppure, immaginate un gruppo di esperti che valuta diverse opzioni per un progetto: le opzioni sono i nodi e la “forza” con cui l’opzione X è giudicata “almeno buona quanto” l’opzione Y (magari contando quanti esperti sono d’accordo) è la capacità dell’arco da X a Y.

Scegliere i “Migliori”: Le Soluzioni di Rete

Una volta che abbiamo questa rete, spesso vogliamo capire quali nodi sono i “migliori” o i “più importanti”. Qui entrano in gioco le cosiddette soluzioni di rete. Sono procedure che, data una rete, selezionano un sottoinsieme di nodi (i “vincitori”, le “alternative migliori”).

Una delle soluzioni più semplici e intuitive è quella basata sul net-outdegree (che potremmo tradurre rozzamente come “grado netto in uscita”). Per ogni nodo, calcoliamo la somma dei pesi degli archi uscenti (quanto “batte” gli altri) e sottraiamo la somma dei pesi degli archi entranti (quanto “viene battuto” dagli altri). I nodi con il punteggio più alto sono i prescelti. È un po’ come calcolare la differenza reti in un torneo.

Esiste anche la soluzione speculare, basata sul net-indegree (“grado netto in entrata”), che favorisce i nodi che “ricevono” di più o “perdono” di meno. E c’è anche la soluzione banale, chiamata total network solution, che seleziona semplicemente tutti i nodi, qualunque sia la rete.

Le Regole del Gioco: Neutralità, Consistenza, Cancellazione

Ora, torniamo alle proprietà magiche di Young: neutralità, consistenza e cancellazione. Possiamo definirle anche per le soluzioni di rete:

• Neutralità: Se rinominiamo i nodi (ad esempio, scambiamo i nomi di due squadre), la soluzione deve semplicemente restituire i nodi corrispondenti con i nuovi nomi. Nessun nodo ha un vantaggio “di nome”.
• Consistenza: Se abbiamo due reti (ad esempio, i risultati di due gironi di un torneo) e c’è almeno un nodo che è tra i “vincitori” in entrambe le reti, allora quel nodo (e solo quello, se ce ne sono altri in comune) deve essere il vincitore della rete “somma” (il torneo complessivo).
• Cancellazione: Se una rete è perfettamente bilanciata (ad esempio, per ogni coppia di squadre, la squadra A ha battuto B tante volte quante B ha battuto A), allora tutti i nodi devono essere selezionati. Non c’è un vero vincitore.

Queste proprietà sembrano molto ragionevoli, non trovate? Sono il tipo di “fair play” che ci aspetteremmo da un buon metodo di selezione o classificazione.

Il Cuore della Scoperta: Caratterizzare le Soluzioni

Ed ecco il risultato principale del lavoro che sto esplorando (che chiameremo Teorema A1): sotto condizioni tecniche abbastanza generali (che definiscono un insieme “regolare” di reti), le uniche soluzioni di rete che soddisfano simultaneamente Neutralità, Consistenza e Cancellazione sono proprio le tre che abbiamo menzionato: la soluzione net-outdegree, la soluzione net-indegree e la soluzione totale!

È un risultato potente! Ci dice che se vogliamo queste tre proprietà fondamentali, la nostra scelta è incredibilmente limitata. O usiamo il criterio “vittorie meno sconfitte”, o il suo opposto, o diciamo che “vincono tutti”. Non ci sono altre strade, almeno all’interno di questi insiemi “regolari” di reti.

Per distinguere ulteriormente la soluzione net-outdegree dalle altre due, basta aggiungere una condizione molto blanda, chiamata O-coerenza: basta che esista almeno una rete non banale (dove non tutti i nodi hanno lo stesso punteggio net-outdegree) per la quale la nostra soluzione coincida effettivamente con quella net-outdegree. Aggiungendo questa richiesta minima, il cerchio si stringe: l’unica soluzione possibile è proprio quella basata sul net-outdegree (Teorema A2).

Dalle Reti al Voto: Un Ponte Inaspettato

Ma cosa c’entra tutto questo con il voto e la Regola di Borda? L’idea geniale è che un profilo di preferenze elettorali può essere visto come una rete!
Immaginiamo un insieme di candidati (i nostri nodi) e un gruppo di elettori. Per ogni coppia di candidati (X, Y), possiamo contare quanti elettori preferiscono X ad Y (o giudicano X almeno buono quanto Y). Questo numero diventa la capacità dell’arco che va da X a Y. Voilà! Abbiamo trasformato un’elezione in una rete.

A questo punto, le “soluzioni di rete” diventano “corrispondenze di scelta sociale” (SCC), cioè regole di voto. La soluzione net-outdegree applicata a questa rete elettorale diventa una regola di voto specifica. E le proprietà di neutralità, consistenza e cancellazione si traducono naturalmente nel contesto del voto:

• Neutralità (voto): I nomi dei candidati non contano.
• Consistenza (voto): Se due gruppi disgiunti di elettori hanno un insieme non vuoto di candidati preferiti in comune, allora unendo i due gruppi, i candidati preferiti devono essere esattamente quelli in comune.
• Cancellazione (voto): Se per ogni coppia di candidati (X, Y), il numero di elettori che preferisce X a Y è uguale al numero di elettori che preferisce Y a X, allora tutti i candidati devono essere scelti.

Le Stesse Regole, un Nuovo Campo da Gioco: La Scelta Sociale

Il passo successivo è quasi magico. Applicando la stessa logica matematica usata per le reti, i ricercatori dimostrano un risultato analogo per le regole di voto (Teorema B1): su insiemi “regolari” di profili di preferenze, le uniche regole di voto che soddisfano Neutralità, Consistenza e Cancellazione sono la regola basata sul net-outdegree (calcolato sulla rete elettorale), quella basata sul net-indegree e quella banale che seleziona sempre tutti (total scc).

Anche qui, aggiungendo la condizione minima di O-coerenza (esiste almeno un profilo di preferenze non banale per cui la regola coincide con quella net-outdegree), si isola univocamente la regola di voto basata sul net-outdegree (Teorema B2).

La Sorpresa Finale: Tante Regole, Una Sola Anima?

E ora, il colpo di scena che collega tutto. Cos’è questa “regola di voto net-outdegree”? Si scopre che, a seconda del tipo di preferenze che permettiamo agli elettori di esprimere (cioè, a seconda del dominio (textbf{D}) su cui applichiamo la regola), essa coincide esattamente con molte regole di voto famose!

• Se gli elettori esprimono classifiche complete senza pareggi (ordini lineari), la regola net-outdegree È la Regola di Borda classica!
• Se ammettiamo pareggi (ordini), è la Regola di Borda generalizzata.
• Se usiamo ordini parziali, è la Regola di Borda Parziale.
• Se usiamo preferenze dicotomiche (approvo/non approvo), è l’Approval Voting!
• Se usiamo preferenze dicotomiche con un solo candidato approvato, è la regola della Pluralità (il classico “un voto per il preferito”).
• Se usiamo preferenze dicotomiche con un solo candidato non approvato, è la regola anti-Pluralità.

Incredibile, vero? Questo approccio basato sulle reti non solo generalizza la caratterizzazione di Young per la Borda, ma rivela una profonda connessione strutturale tra tutte queste regole di voto. Neutralità, Consistenza e Cancellazione (con piccoli aggiustamenti a seconda del contesto) diventano gli assiomi fondamentali che le caratterizzano, mostrando che, sotto questa lente matematica, condividono una radice comune.

Cosa Ci Portiamo a Casa?

Questo lavoro ci offre una prospettiva unificante e potente. Ci mostra come principi apparentemente semplici (neutralità, consistenza, cancellazione) abbiano conseguenze profonde, limitando drasticamente le possibili “buone” regole sia nell’analisi delle reti che nella scelta sociale. E, cosa forse più affascinante, svela l’anima nascosta e condivisa di sistemi di voto che pensavamo fossero distinti, riconducendoli a un unico principio fondamentale quando visti attraverso il prisma delle reti. È un bellissimo esempio di come l’astrazione matematica possa illuminare e connettere diverse aree della conoscenza. Spero che questo viaggio vi abbia incuriosito almeno quanto ha incuriosito me!

Fonte: Springer