🔢 mathematics

Counting Votes with Multisets

Questo articolo dimostra come le proprietà categoriali dei multiset — specificamente la loro struttura come monoide commutativo libero, funtore e monade — possano essere applicate efficacemente per derivare ed esprimere i risultati in vari sistemi di voto, inclusi il ballottaggio, il metodo De Borda e il voto unico trasferibile.

Autori originali: Bart Jacobs, Michael Johnson, Richard Buckland

Pubblicato 2026-06-05

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Bart Jacobs, Michael Johnson, Richard Buckland

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di gestire un voto, ma invece di contare i singoli schede cartacee, stai gestendo un enorme sacchetto di biglie colorate. Questa è l'idea centrale del documento: Multiset.

Ecco una semplice scomposizione di ciò che gli autori, Bart Jacobs, Michael Johnson e Richard Buckland, propongono, utilizzando analogie quotidiane.

1. Il Sacchetto Magico (Cos'è un Multiset?)

Di solito, in matematica, un "insieme" (set) è come una lista di elementi unici. Se hai un insieme di frutta, puoi avere una mela e una banana, ma non puoi avere "due mele" nella definizione dell'insieme; c'è solo "mele".

Un Multiset è come un sacchetto di biglie.

Se metti 4 biglie rosse, 3 blu e 2 verdi in un sacchetto, l'ordine non conta.
Ciò che conta è il conteggio.
Gli autori lo scrivono così: 4|R⟩ + 3|B⟩ + 2|G⟩.
In un'elezione, questo sacchetto rappresenta i voti. Non importa chi ha votato o quando ha votato; l'unica cosa che conta è che ci sono 4 voti per il Rosso, 3 per il Blu e 2 per il Verde.

Perché è un bene?
Se tieni i voti in una lista (come un foglio di calcolo), l'ordine della lista potrebbe accidentalmente rivelare chi ha votato cosa. Ma se versi tutto in un "sacchetto multiset", l'ordine scompare. Ottieni un conteggio pulito e anonimo che è impossibile risalire ai singoli individui.

2. I Tre Giochi di Voto

Il documento mostra come questo approccio del "sacchetto di biglie" renda molto più semplici da comprendere e calcolare tre sistemi di voto complessi. Usano alcuni termini matematici sofisticati (come "functor" e "monad"), ma pensateli come regole per spostare le biglie in giro.

Gioco A: Voto con Scelta Immediata (Il gioco dell' "Eliminazione")

Come funziona: Gli elettori classificano i candidati (1°, 2°, 3°). Se nessuno ottiene il 50% dei voti, la persona con meno voti viene eliminata. I suoi voti vengono quindi assegnati alla seconda scelta degli elettori.
Il trucco del Multiset: Immagina che il tuo sacchetto di schede sia una pila di liste.
1. Guardi la parte superiore di ogni lista (la 1ª scelta) e conti le biglie.
2. Trovi il perdente (Candidato C).
3. Usi un "cancella magico" (chiamato functor nel documento) per cancellare il Candidato C da ogni singola lista nel sacchetto.
4. Ora le 2ª scelte diventano le nuove 1ª scelte. Conti di nuovo il sacchetto.
5. Ripeti finché qualcuno non ha una maggioranza.
Il vantaggio: Invece di cancellare manualmente i nomi su migliaia di fogli, applichi la regola di "cancellazione" all'intero sacchetto in un colpo solo.

Gioco B: Conteggio De Borda (Il gioco dei "Punti Pesati")

Come funziona: Gli elettori classificano i candidati. La 1ª scelta ottiene 4 punti, la 2ª ottiene 3 punti, la 3ª ottiene 2, ecc. Tutti i punti vengono sommati.
Il trucco del Multiset:
1. Invece di contare solo i voti, trasformi ogni singola scheda in un mini-sacchetto di biglie pesate. Una scheda che dice "A, B, C, D" diventa 4|A⟩ + 3|B⟩ + 2|C⟩ + 1|D⟩.
2. Versi tutti questi mini-sacchetti in un unico grande super-sacchetto.
3. Usi uno strumento di "appiattimento" (chiamato monad) per schiacciare tutti gli strati insieme.
4. Il risultato è un unico grande conteggio dei punti totali per ogni candidato.
Il vantaggio: Trasforma un problema matematico complesso in una semplice operazione di "somma tutto".

Gioco C: Voto Singolo Trasferibile (Il gioco della "Condivisione del Surplus")

Come funziona: Questo viene usato per eleggere più persone (come un consiglio comunale). C'è una "quota" (un numero minimo di voti necessari per vincere). Se un candidato ottiene molti più voti del necessario, i suoi voti extra non dovrebbero essere sprecati; dovrebbero essere trasferiti alla successiva scelta degli elettori.
Il trucco del Multiset:
1. Immagina che un candidato vinca con 93 voti, ma la quota sia solo 63. Ha 30 voti di "surplus".
2. Invece di scegliere 30 fogli a caso da trasferire (il che sarebbe ingiusto), gli autori suggeriscono un trucco matematico: Svalutare i voti.
3. Prendi tutti i 93 voti per quel vincitore e rimpiccioliscili secondo una specifica frazione (come rimpicciolire una foto).
4. Poi, "cancelli" il vincitore dalle liste e trasferisci questi voti "rimpiccioliti" ai candidati successivi.
5. Questo permette alla matematica di gestire perfettamente le frazioni di voto, assicurando che nessun voto venga sprecato o contato due volte.

3. Perché questo è importante?

Gli autori non stanno cercando di inventare un nuovo tipo di matematica; stanno dimostrando che la matematica vecchia (Teoria delle Categorie) è lo strumento perfetto per il voto moderno.

Trasparenza: Poiché i multiset ignorano l'ordine dei voti, il processo di conteggio è matematicamente garantito come anonimo.
Semplicità: Regole complesse (come eliminare i perdenti o dividere i voti in eccesso) diventano semplici operazioni su un sacchetto di biglie.
Correttezza: Se scrivi un programma per computer per contare i voti usando queste regole del "sacchetto", è molto più difficile commettere errori rispetto al cercare di smistare pile di carta.

In sintesi: Il documento sostiene che se smettiamo di pensare ai voti come a un disordinato mucchio di carta e iniziamo a pensarli come a un sacchetto di biglie colorate, possiamo usare semplici e potenti regole matematiche per contarli in modo equo, veloce e senza errori.

Sintesi Tecnica: Conteggio dei Voti con i Multiset

Problematica
Il documento affronta la sfida di descrivere, spiegare e implementare algoritmi di conteggio dei voti per sistemi elettorali complessi, in particolare quelli che coinvolgono il voto preferenziale (preferendum) e molteplici opzioni pesate. Mentre le elezioni semplici (ad esempio, due candidati, voto singolo) possono essere descritte tramite liste o semplici conteggi, i meccanismi come l'Instant-Runoff Voting (IRV), il conteggio De Borda e il Single Transferable Vote (STV) comportano il trasferimento di voti in eccesso, l'eliminazione di candidati e la ricalibrazione dei pesi delle preferenze. Gli autori sostengono che i tipi di dati standard come le liste siano subottimali per questi compiti perché mantengono l'ordine (che è irrilevante per l'esito) e possono far trapelare informazioni riguardanti la sequenza di voto, compromettendo potenzialmente la riservatezza. Inoltre, l'implementazione di questi algoritmi con le liste porta spesso a un codice complesso e ad hoc, difficile da verificare per correttezza e trasparenza.

Metodologia
Il documento propone di modellare gli esiti elettorali e i processi di conteggio dei voti utilizzando i multiset (insiemi in cui gli elementi possono occorrere più volte) piuttosto che le liste. Gli autori impiegano tecniche elementari della teoria delle categorie per formalizzare le operazioni su questi multiset. La metodologia centrale prevede:

Selezione del tipo di dato: Rappresentare una collezione di voti come un multiset $N(X)$ (o $M(X)$ per i voti frazionari), dove gli elementi sono i candidati e le molteplicità sono i conteggi dei voti. Ciò astrae l'ordine dei voti.
Strutture Categoriche: Gli autori utilizzano tre specifiche proprietà categoriali dei multiset per derivare ed esprimere gli algoritmi di voto:
- Monoido Commutativo: I multiset formano un monoido commutativo libero, consentendo l'addizione dei conteggi dei voti (unione di urne) dove l'ordine è irrilevante.
- Funzionalità (Functoriality): La costruzione del multiset $N$ agisce come un funttore. Ciò permette alle funzioni definite sui candidati (ad esempio, "testa della lista" o "elimina candidato") di essere elevate a funzioni su multiset di liste. Questa proprietà è utilizzata per aggregare le prime preferenze e per ridistribuire i voti quando un candidato viene eliminato.
- Struttura di Monade: I multiset formano una monade con unit (creazione di un multiset singolo) e flatten (collasso di un multiset di multiset). Questa struttura è utilizzata per gestire i conteggi pesati, dove un singolo voto (una lista di preferenze) viene scomposto in contributi pesati a più candidati.

Contributi Chiave e Risultati
Il documento dimostra l'applicazione di queste strutture categoriali attraverso tre specifici meccanismi di voto, utilizzando piccoli esempi (verificati tramite script Python della libreria EfProb) per illustrare l'astrazione:

Instant-Runoff Voting (IRV):
- Meccanismo: I candidati con il minor numero di prime preferenze vengono eliminati iterativamente, e i loro voti vengono trasferiti alla preferenza successiva.
- Applicazione: Gli autori utilizzano la funzionalità dei multiset. La funzione head (selezione della prima preferenza) e la funzione delete (rimozione di un candidato eliminato) sono elevate per operare sul multiset di liste di preferenze. Ciò consente di esprimere l'aggregazione delle prime preferenze e la successiva ridistribuzione dei voti come semplici composizioni funzionali ( $N(\text{hd})$ e $N(\text{del } c)$ ), evitando complessi processi iterativi su liste.
Conteggio De Borda:
- Meccanismo: Gli elettori classificano i candidati e vengono assegnati punti in base al rango (ad esempio, il 1° posto ottiene $n$ punti, il 2° ottiene $n-1$ , ecc.).
- Applicazione: Viene utilizzata la struttura di monade. Ogni lista di preferenze è mappata in un multiset di candidati pesati (tramite unit e assegnazione dei punti). La collezione di tutti tali multiset pesati forma un multiset di multiset. L'operazione di flatten collassa poi questa struttura in un singolo multiset di punteggi totali, sommando efficientemente i contributi pesati.
Single Transferable Vote (STV):
- Meccanismo: Utilizzato per collegi plurinominali. I candidati che superano una quota (quota Droop) vengono eletti, e i loro voti in eccesso vengono trasferiti alla preferenza successiva.
- Applicazione: Gli autori estendono il tipo di dato ai multiset frazionari ( $M(X)$ ) per gestire il "valore di trasferimento" (una frazione di un voto). Utilizzano la struttura del monoido per la sottrazione (svalutazione dei voti usati per eleggere un candidato) e la funzionalità per la ridistribuzione. Il processo è modellato come una sottrazione iterativa dei voti pesati rispetto alla quota del candidato eletto dal multiset totale, seguita dalla rimozione del candidato eletto e dal trasferimento dei pesi frazionari rimanenti alla preferenza successiva.

Significatività e Rivendicazioni
Il documento rivendica modestamente che il suo contributo primario non risiede nella teoria delle categorie profonda, ma nel riconoscimento e nello sfruttamento delle strutture categoriali esistenti (funttori, monadi, monoidi) all'interno del dominio dei sistemi di voto. Gli autori sostengono che:

Astrazione: Descrivere questi algoritmi in termini di multiset li rende "astratti", permettendo a meccanismi complessi di essere descritti in poche righe di notazione matematica.
Correttezza e Trasparenza: L'approccio dei multiset garantisce intrinsecamente la stabilità rispetto alla permutazione dei voti (indipendenza dall'ordine), un requisito fondamentale per un conteggio equo. Esso separa la logica del conteggio dalla rappresentazione fisica o sequenziale delle schede.
Implementazione: L'astrazione facilita la creazione di implementazioni provabilmente corrette in linguaggi di programmazione funzionale (ad esempio, Haskell) che supportano i multiset.
Accessibilità: Il documento mira a rendere queste tecniche categoriali accessibili anche ai non esperti, dimostrando che sono strumenti pratici per garantire la trasparenza e l'accuratezza degli esiti elettorali, piuttosto che costrutti puramente teorici.

Il documento conclude che, sebbene siano state fatte ipotesi semplificative (ad esempio, lunghezze delle liste uniformi), l'approccio dei multiset offre un quadro robusto per future implementazioni di riferimento e per l'analisi degli algoritmi elettorali, andando oltre il tradizionale affidamento alla smistazione fisica delle schede elettorali.