AR - 17 - Sistemi di Voto I

Lecture Info

Data: [2018-12-12 mer]
Capitolo Libro: Chapter 23 - Voting
Introduzione: In questa lezione abbiamo introdotto l'ultimo argomento del corso: i sistemi di voto. In particolare abbiamo descritto il modello matematico di riferimento e due dei più famosi possibili sistemi di voto, fermandoci per vedere le problematiche di ciascuno dei due sistemi di voto.

1 Modello Matematico di Voto

In una precedente lezione abbiamo discusso degli algoritmi di ranking nel contesto del Web. In particolare avevamo visto come gli algoritmi di ranking come il Page Rank e Hubs And Authorities utilizzavano le informazioni aggregate rappresentate dalla struttura della rete al fine di ottenere le informazioni di interesse per ogni singolo nodo della rete.

Consideriamo adesso il problema inverso: abbiamo tante singole informazioni, e vogliamo aggregarle. Il modello matematico che abbiamo in mente è quindi così descritto: Abbiamo $k$ giudici, o votanti, e $n$ scelte $v_1, v_2, ..., v_n$. Ogni votante deve scegliere un ordinamento delle scelte, partendo dalla scelta "migliore", per finire con quella "peggiore".

Andiamo adesso a rendere formale il modello appena descritto, notando prima di iniziare che la formalizzazione del modello può avvenire in due modi diversi, in quanto i votanti hanno due modi diversi in cui possono esprimere le loro preferenze.

1.1 Voto Tramite Ranking

In questa modalità di voto ciascun votante esprimere un giudizio globale su ogni alternativa, andando a listarle dalla "migliore" alla "peggiore". Formalmente troviamo,

$N := \{v_1, v_2, ..., v_n\}$, insieme delle possibili scelte.

$\Pi(N) := \text{ insieme delle permutazioni di } N$

$\forall i = 1, ..., k$, il giudice $i$ esprime il suo ranking tramite una permutazione delle alternative, ovvero con $r_i \in \Pi(N)$. In totale quindi i $k$ giudici esprimo un profilo formato da $k$ permutazioni $\{r_1, r_2, ..., r_k\} \in \Pi(N)^k$.

Un sistema di voto è quindi una funzione $F: \Pi(N)^k \to \Pi(N)$ che mappa un profilo di scelte ad una singola permutazione, ovvero ad un singolo ranking.

1.2 Voto Tramite Ordinamento

Un altro metodo di voto è quello in cui il giudice $i$ esprime le sue preferenze a coppie tramite una relazione binaria $\geq_i \subseteq N \times N$, che deve essere completa e transitiva.

Ricordiamo che una relazione binaria $\geq_i \subseteq N \times N$ è:

completa: se per ogni $a, b \in N$, deve valere che $a \geq_i b$ oppure $b \geq_i a$. In altre parole possiamo confrontare ogni coppia di elementi.

transitiva: se per ogni $a, b, c \in N$, se vale $a \geq_i b$, e $b \geq_i c$, allora vale anche $a \geq_i c$.

1.3 Equivalenza dei Metodi di Voto

Notiamo a questo punto che le due forme di voto che abbiamo appena descritto sono equivalenti, ovvero possiamo passare da una forma di votazione all'altra senza perdere nessuna informazione e mantendendo il giudizio complessivo effettuato dal votante. Procediamo quindi con la dimostrazione di questa equivalenza.

Teorema 1: Data una permutazione $r_i \in \Pi(N)$, esiste una relazione binaria $\geq_i \subseteq N \times N$ completa e transitiva che cattura le preferenze a coppie descritte dalla permutazione $r_i$.

Dimostrazione: Sia $r_i \in \Pi(N)$ il ranking espresso dal giudice $i$. Definiamo la relazione binaria $\geq_i \subset N \times N$ nel seguente modo

\[\forall v_j, v_l \in N: \,\, v_j \geq_i v_l \overset{\;\Delta}{\iff} r_i(v_j) \geq r_i(v_l)\]

dove con $r_i(v_j)$ e $r_i(v_l)$ intendiamo il ranking delle alternative $v_j$ e $v_l$ rispetto all'ordinamento $r_i$. Ad esempio, se $v_j$ è scelta come l'alternativa "migliore" dal votante $i$, allora $r_i(v_j) = n-1$, e se $v_l$ è scelta come l'alternativa "peggiore", allora $r_i(v_l) = 0$.

È possibile vedere che la relazione definita è una relazione completa e transitiva che preserva le preferenze del votante $i$ rispetto alle varie coppie di alternative.

\[\tag*{$\blacksquare$}\]

Teorema 2: Data una relazione binaria $\geq_i \subseteq N \times N$ completa e transitiva, esiste una permutazione $r_i \in \Pi(N)$ che descrive il ranking delle preferenze del votante $i$ come descritte da $\geq_i$.

Per dimostrare il teorema appena enunciato necessitiamo del seguente lemma tecnico.

Lemma: Dato un ordinamento $\geq_i$ delle preferenze coppia a coppia, se $v_j \in N$ è una alternativa tale che

\[|\{v_l : \,\, v_j \geq_i v_l \}| = \max_{h = 1...k} |\{v_l: \,\, v_h > v_l\}|\]

allora, per ogni $h = \in \{1, ..., n\} - \{j\}$ si ha che $v_j \geq_i v_h$.

Il lemma ci dice che se $v_j$ è la scelta che massimizza il numero di alternative battute tramite $\geq_i$, allora $v_j$ batte tutte le altre alternative. Procediamo quindi con la dimostrazione del lemma.

Dimostrazione: Sia $h$ tale che $v_h \geq_i v_j$. Dalla transitività di $\geq_i$ segue che se $v_j$ batte $v_l$ tramite $\geq_i$, allora anche $v_h$ batte $v_l$ tramite $\geq_i$. Ma allora,

\[\begin{split} \phantom{} |\{v_l: \,\, v_h > v_l\}| &\geq |\{v_l: \,\, v_j \geq_i v_l\} \cup \{v_j\}| \\ &> |\{v_l: \,\, v_j \geq_i v_l\}| \end{split}\]

Dunque $v_j$ non è l'alternativa che massimizza il numero di alternative battute. Avendo dimostrato il contrapositivo dell'enunciato, abbiamo terminato.

\[\tag*{$\blacksquare$}\]

L'ultima cosa che ci serve per dimostrare il teorema di interesse è notare che non possono esistere due alternative che battono lo stesso numero di alternative. Infatti, se per assurdo non fosse così, ovvero se esistono $v_l$ e $v_j$ tale che $v_l$ e $v_j$ battono lo stesso numero di alternative tramite $\geq_i$, allora per la completezza di $\geq_i$ abbiamo che $v_l \geq_i v_j$ oppure $v_j \geq_i v_l$. Data la simmetria dei due casi ne possiamo discutere solamente uno, e l'altro è trattato in modo analogo. Supponiamo quindi che $v_l \geq_i v_j$. In questo caso il numero di alternative battute da $v_l$ è almeno il numero di alternative battute da $v_j$ più uno, in quanto per transitività $v_l$ batte tutte quelle di $v_j$, e inoltre batte anche $v_j$. Dunque non può succedere che due alternative battono lo stesso numero di alternative.

Procediamo adesso con la dimostrazione del Teorema 2.

Dimostrazione: Sia $\geq_i$ una relazione binaria. Dal lemma e dall'osservazione precedente segue che l'alternativa con il ranking migliore è quella (unica) che massimizza il numero di alternative battute secondo $\geq_i$.

Procedendo in modo iterativo possiamo quindi costruire il ranking $r_i$ a partire dall'ordinamento $\geq_i$ semplicemente estraendo di volta in volta l'alternativa che massimizza il numero di alternative battute tramite la relazione $\geq_i$.

\[\tag*{$\blacksquare$}\]

2 Esempi di Sistemi di Voto

A prescindere dalla forma in cui viene espresso il voto (tramite ranking o ordinamento), il nostro obiettivo è quello di trovare delle funzioni $F$ che siano in grado di desumere da $k$ votazioni la votazione che rappresenta "meglio" le scelte dei giudici.

Andiamo quindi a descrivere alcuni dei sistemi di voto più famosi.

2.1 Voto a Maggioranza

Consideriamo votazioni effettuate tramite ordinamento. In particolare abbiamo un profilo contenente $k$ ordinamenti $\{\geq_i : \,\, i = 1,..., k\}$ e vogliamo capire il modo migliore per ottenere un ordinamento aggregato a partire dai singoli ordinamenti.

Si definisce quindi $F(\geq_1, \geq_2, ..., \geq_k)$ come la relazione $>$ tale che per ogni coppia di alternative $v_j, v_l \in N$, $v_j$ è maggiore di $v_l$ secondo l'ordinamento aggregato, $v_j > v_l$, se e solo se vale la seguente cosa

\[|\{h: v_j \geq_h v_l\}| > |\{h: v_l \geq_h v_j\}|\]

In altre parole quindi $v_j$ è meglio di $v_l$ secondo $>$ se $v_j$ batte $v_l$ per la maggior parte dei votanti. Il sistema di voto $F$ appena definito prende il nome di sistema di voto a maggioranza.

2.1.1 Esempio (Paradosso di Condorcet)

Consideriamo tre amici, $A, B$ e $C$. Ciascun amico deve dare la sua opinione rispetto a tre possibili scelte di cibo, che sono $\text{C} := \text{Cioccolata}$, $\text{Ma} := \text{Marmellata}$ e $\text{Mi} := \text{Miele}$.

Supponiamo che i tre amici scelgono di votare tramite un sistema di votazione a maggioranza tramite le seguenti scelte

$A:$ $C \geq_A \text{Ma} \geq_A \text{Mi}$
$B:$ $\text{Ma} \geq_B \text{Mi} \geq_B C$
$C:$ $\text{Mi} \geq_C C \geq_C \text{Ma}$

Notiamo che calcolando l'ordinamento aggregato $F(\geq_A, \geq_B, \geq_C)$ troviamo una relazione non transitiva. Infatti abbiamo che per l'ordinamento aggregato $C$ batte $\text{Ma}$, $\text{Ma}$ batte $\text{Mi}$ e $\text{Mi}$ batte $C$.

Il fatto che partendo da ordinamenti transitivi e aggregandoli si può ottenere un ordinamento non transitivo è un problema dei sistemi di voto a maggioranza che prende il nome di Paradosso di Condocert. Questo problema ci fa capire che trovare un buon sistema di voto aggregato non è un problema facile da risolvere.

2.2 Voto Posizionale

In questo sistema di voto il profilo dei vari votanti è espresso come un insieme di ranking $P = \{r_1, r_2, ..., r_k\}$. Il sistema di voto è quindi definito come segue

\[F(P)(v_j) = r(v_j) := \underbrace{\sum\limits_{i = 1}^k r_i(v_j)}_{\text{Il valore deve essere poi scalato} \\ \text{per avere che il top rank sia } n -1}\]

Questo sistema di voto prende il nome di sistema di voto posizionale, o anche Borda count. Esistono varie versioni del Borda count. Il nostro sistema politico è un esempio di Borda Count caratterizzato dal fatto che ciascun votante indica solamente l'alternativa migliore, ovvero è tale che per ogni votante $i$ e per ogni alternativa $v_j$

\[r_i(v_j) = \begin{cases} 1,& \,\, \text{ se } i \text{ sceglie } v_j \\ 0,& \,\, \text{ altrimenti } \end{cases}\]

2.2.1 Esempio (Alternative Irrilevanti)

Consideriamo due amici che devono scegliere quale film guardare. Inizialmente sono presi in considerazione due film, "Tempi Moderni", $\text{TM}$, e "Pulp Fiction", $\text{PF}$.

Inizialmente troviamo la seguente situazione

$\begin{cases} \text{TM} \geq_1 \text{PF} \\ \text{PF} \geq_2 \text{TM} \\ \end{cases} \implies \text{situazione di stallo}$

Il primo dei due amici poi introduce un terzo film, "Vacanze di Natale, $\text{VN}$. Il film non piace a nessuno dei due, però il primo amico mette $\text{VN}$ prima di $\text{PF}$. Il ranking viene quindi modificato come segue

$\begin{cases} \text{TM} \geq_1 \text{VN} \geq_1 \text{PF} \\ \text{PF} \geq_2 \text{TM} \geq_2 \text{VN} \\ \end{cases}$

Andando adesso calcolare il ranking di ciascuna alternativa troviamo la seguente situazione

$r(\text{TM}) = 3$
$r(\text{PF}) = 2$
$r(\text{VN}) = 1$

Possiamo quindi vedere come il primo amico è riuscito a modificare il ranking finale introducendo una alternativa extra, che però sapeva che non sarebbe mai finita in cima alla classifica. Questo esempio fa vedere come in un sistema di votazione posizionale è possibile introdurre delle alternative irrilevanti che però riescono comunque a modificare il ranking finale ottenuto.