L'algoritmo di Majority Voting di Boyer-Moore

by

Nel 1981 due ricercatori, Robert S. Boyer e J. Strother Moore, crearono un algoritmo che consente di determinare im modo estremamante efficiente se, in una votazione con un numero di candidati non noto a priori, ce ne sia uno che abbia raggiunto la maggioranza assoluta, cioè la metà dei voti più uno.

Il loro Majority Voting Algorithm trova applicazioni nel campo dell'informatica, meno in quello di reali votazioni, dove non basta dichiarare chi è il vincitore, ma occorre offrire trasparenza sul dettaglio dei risultati.

Ma quali vantaggi dal punto di vista informatico offre il Majority Voting Algorithm, rispetto a uno scrutinio tradizionale? Essenzialmente due, legati rispettivamente al tempo di esecuzione e alla quantità di memoria necessaria per l'esecuzione.

Il tempo di esecuzione dell'algoritmo è lineare

È sufficiente infatti scorrere due volte la sequenza di schede, per:

  • verificare, al primo passo, se esiste un potenziale vincitore o no;
  • confermare il vincitore, o concludere che nessuno ha raggiunto la maggioranza assoluta, al secondo passo.

La memoria necessaria non dipende dal numero di candidati, né dal numero di schede

In un algoritmo di scrutinio tradizionale, si predisporrebbe un contatore per il conteggio dei voti di ciascun candidato. Nell'algoritmo di Boyer-Moore, invece, si predispongono solo tre contatori, relativi a tre pile tra cui vengono spostate le schede durante i due passi.
Alla fine del secondo passo, in caso di presenza di un candidato che abbia raggiunto la maggioranza assoluta, in una delle pile si troverà un numero di schede pari al margine di quel candidato su tutti gli altri.

L'algoritmo: primo passo, il pairing

Si indichi con pila A, pila B e pila C le tre pile utilizzate nell'esecuzione dell'algoritmo.
Inizialmente si predispongono le schede sulla pila A, a faccia in su.

Fino a esaurimento della pila A, si operi come segue:

  • si sposti sulla pila B la scheda che si trova in cima alla pila A se:
    • la pila B è vuota;
    • oppure se in cima alla pila B c'è una scheda con la stessa preferenza della scheda che si sta spostando;
  • se, invece, la scheda in cima alla pila B ha una preferenza per un candidato diverso da quello della scheda che si sta spostando, allora tutte e due le schede vengono spostate sulla pila C.

Alla fine del primo passo la pila A sarà vuota, la pila C conterrà una serie di coppie di schede recanti preferenze discordanti, mentre la pila B sarà vuota oppure conterrà schede con preferenza per un unico candidato X.

In base a ciò, si può concludere che, a parte X, nessuno degli altri candidati può aver raggiunto la maggioranza assoluta, perché al massimo può esserci un candidato che ha ottenuto la metà dei voti. E questo accade se uno stesso candidato è presente in ciascuna delle coppie di schede che popolano la pila C.

Si esce dal primo passo, il pairing, con una di queste due condizioni:

  • nessun candidato ha raggiunto la maggioranza assoluta (la pila B è vuota);
  • nella pila B ci sono schede con preferenze per un unico candidato (X), che è quindi il potenziale vincitore.

L'algoritmo: secondo passo, il counting

Il secondo passo viene effettuato sostanzialmente con le stesse regole del primo, scambiando il ruolo tra le pile A e C, ma questa volta verificando chi ha ricevuto più preferenze, tra X e tutti gli altri candidati messi insieme.
Se ha prevalso X, allora X è il vincitore, in caso contrario non c'è nessun vincitore.

L'algoritmo in Python

Il codice Python, abbastanza elementare, si articola come segue:

  1. una prima sezione predispone l'insieme dei candidati e, in modo casuale, una serie di schede ciascuna indicante una preferenza; in questa sezione è possibile forzare se un candidato ha la maggioranza assoluta, e il relativo margine;
  2. nella seconda sezione, viene effettuato uno scrutinio tradizionale, per poter verificare successivamente il risultato dell'algoritmo;
  3. nella terza sezione si esegue il passo del pairing;
  4. nell'ultima sezione, eseguita solo se il pairing ha indicato un potenzale vincitore, si esegue il passo del counting.

Il codice Python

# Majority Voting Algorithm, Boyer-Moore 1981
# p.p. 25mar23
import random
#
candidati = ("A","B","C","D","E")
min_preferenze, max_preferenze = 0,10
majority = False
margin = 2
#
n_candidati = len(candidati)
schede = []
#
for c in candidati:
  schede = schede + random.randint(min_preferenze,max_preferenze)*list(c)
#
if majority:
  first_pref = schede.count(candidati[0])
  x = len(schede) - 2 * first_pref + margin
  schede += x * candidati[0]
random.shuffle(schede)
#
print ("Numero di candidati: {}".format(n_candidati))
print ("Numero di schede da scrutinare: {}".format(len(schede)))
print ("Maggioranza assoluta: {}".format(int(len(schede)/2)+1))
print ("Schede da scrutinare:\n{}".format(schede))
print ("\nDistribuzione dei voti:\n=======================")
max = -1
for c in candidati:
  voti = schede.count(c)
  print ("{} --> {}".format(c,voti))
  if voti > max:
    max, winner = voti, c
print ("Massimo dei voti: {}, ottenuto da {}".format(max, winner))
#
print ("\nPasso di pairing\n================")
pila_A = schede
pila_B = []
pila_C = []
#
for scheda in pila_A:
  if len(pila_B) == 0 or scheda == pila_B[0]:
    pila_B += list(scheda)
  else:
    pila_C += list(scheda) + list(pila_B[0])
    del pila_B[0]
pila_A = []
#
print ("pila_A:\n{}\npila_B:\n{}\npila_C:\n{}\n".format(pila_A,pila_B,pila_C))
print ("schede nella pila_A: {}, nella pila_B: {}, nella pila_C: {}".format(len(pila_A),len(pila_B),len(pila_C)))
#
if len(pila_B) > 0:
  x = pila_B[0]
  print ("potenziale vincitore: {}".format(x))
else:
  x = ""
#
if x == "":
  print ("nessun candidato ha raggiunto la maggioranza assoluta")
else:
  print ("\n\nPasso di counting\n=================")
  for scheda in pila_C:
    if len(pila_B) == 0 or (scheda == x and pila_B[0] == x) or (scheda != x and pila_B[0] != x):
      pila_B += list(scheda)
    else:
      pila_A += list(scheda) + list(pila_B[0])
      del pila_B[0]
  pila_C = []
#
  print ("pila_A:\n{}\npila_B:\n{}\npila_C:\n{}\n".format(pila_A,pila_B,pila_C))
  print ("schede nella pila_A: {}, nella pila_B: {}, nella pila_C: {}".format(len(pila_A),len(pila_B),len(pila_C)))
#
  if pila_B[0] == x:
    print ("{} è il vincitore! margine: {}".format(x,len(pila_B)))
  else:
      print ("nessun candidato ha raggiunto la maggioranza assoluta")

Un caso di votazione senza vincitori con maggioranza assoluta

Ecco di seguito l'output dell'algoritmo in un caso in cui, non avendo forzato la vittoria del candidato A, effettivamente non c'è stato un vincitore:

Numero di candidati: 5
Numero di schede da scrutinare: 29
Maggioranza assoluta: 15
Schede da scrutinare:
['E', 'C', 'C', 'D', 'A', 'A', 'E', 'D', 'A', 'E', 'B', 'D', 'A', 'C', 'C', 'D', 'A', 'A', 'C', 'C', 'D', 'D', 'C', 'D', 'D', 'D', 'E', 'D', 'C']

Distribuzione dei voti:
=======================
A --> 6
B --> 1
C --> 8
D --> 10
E --> 4
Massimo dei voti: 10, ottenuto da D

Passo di pairing
================
pila_A:
[]
pila_B:
['D', 'D', 'D']
pila_C:
['C', 'E', 'D', 'C', 'E', 'A', 'D', 'A', 'E', 'A', 'D', 'B', 'C', 'A', 'D', 'C', 'C', 'A', 'C', 'A', 'C', 'D', 'E', 'D', 'C', 'D']

schede nella pila_A: 0, nella pila_B: 3, nella pila_C: 26
potenziale vincitore: D


Passo di counting
=================
pila_A:
['C', 'D', 'E', 'D', 'C', 'D', 'E', 'D', 'D', 'A', 'D', 'A', 'D', 'E', 'D', 'A', 'D', 'B', 'D', 'C']
pila_B:
['A', 'C', 'C', 'A', 'C', 'A', 'C', 'E', 'C']
pila_C:
[]

schede nella pila_A: 20, nella pila_B: 9, nella pila_C: 0
nessun candidato ha raggiunto la maggioranza assoluta

Il pairing ha indicato D come potenziale vincitore, ma il counting mostra che D ha meno voti degli altri candidati messi insieme, perché la pila B contiene solo schede con preferenze diverse da D.

Ed ecco, invece, un caso in cui si è forzata la vittoria di A con il margine di 1 voto, modificando così il codice:

majority = True
margin = 1

L'output:

Numero di candidati: 5
Numero di schede da scrutinare: 39
Maggioranza assoluta: 20
Schede da scrutinare:
['A', 'C', 'B', 'A', 'A', 'D', 'A', 'A', 'A', 'C', 'C', 'B', 'A', 'A', 'A', 'A', 'D', 'A', 'B', 'B', 'E', 'C', 'B', 'A', 'C', 'B', 'A', 'A', 'A', 'D', 'A', 'A', 'A', 'A', 'D', 'C', 'A', 'C', 'D']

Distribuzione dei voti:
=======================
A --> 20
B --> 6
C --> 7
D --> 5
E --> 1
Massimo dei voti: 20, ottenuto da A

Passo di pairing
================
pila_A:
[]
pila_B:
['A', 'A', 'A']
pila_C:
['C', 'A', 'A', 'B', 'D', 'A', 'C', 'A', 'C', 'A', 'B', 'A', 'D', 'A', 'B', 'A', 'B', 'A', 'E', 'A', 'C', 'A', 'A', 'B', 'B', 'C', 'D', 'A', 'D', 'A', 'C', 'A', 'C', 'A', 'D', 'A']

schede nella pila_A: 0, nella pila_B: 3, nella pila_C: 36
potenziale vincitore: A


Passo di counting
=================
pila_A:
['C', 'A', 'B', 'A', 'D', 'A', 'C', 'A', 'C', 'A', 'B', 'A', 'D', 'A', 'B', 'A', 'B', 'A', 'E', 'A', 'C', 'A', 'B', 'A', 'B', 'A', 'C', 'A', 'D', 'A', 'D', 'A', 'C', 'A', 'C', 'A', 'D', 'A']
pila_B:
['A']
pila_C:
[]

schede nella pila_A: 38, nella pila_B: 1, nella pila_C: 0
A è il vincitore! margine: 1

L'immagine di apertura è di mohamed_hassan from Pixabay.

Pasquale

Dopo innumerevoli anni da informatico, tra Ivrea e Milano, finalmente a riposo sulle rive del lago di Lecco. Scrivimi a: 70plus@libero.it