AR - 19 - Sistemi di Voto III

Lecture Info

  • Data: [2018-12-19 mer]

  • Capitolo Libro: Chapter 23 - Voting

  • Introduzione: In questa ultima lezione del corso abbiamo concluso la trattazione dei sistemi di voto, andando ad introdurre un nuovo contesto in cui i sistemi di voto posso essere utilizzati. La lezione è stata quindi incentrata sulla descrizione di un paio di situazioni in cui i votanti potrebbero essere incentivati a mentire. Infine, si è brevemente menzionato il teorema della giuria di Condorcet.

1 Sistemi di Voto per Aggregare Informazioni

Nelle scorse due lezioni abbiamo studiato i sistemi di voto come sistemi utilizzati per aggregare opinioni diverse in modo da produrre un particolare giudizio. In alcuni contesti però i sistemi di voto possono anche essere utilizzati per individuare la scelta giusta tra un insieme di alternative.

Notiamo come questi due contesti di utilizzo sono diversi tra loro, in quanto nel primo ci basiamo principalmente su opinioni, che quindi non possono essere "giustificate", mentre nel secondo caso ci basiamo su delle opinioni che possono essere "giustificate" dalla presenza di determinali segnali, il cui ruolo è proprio quello di informare i votanti rispetto a quale sia la scelta corretta.

Per analizzare questo nuovo contesto utilizziamo un modello matematico molto simile a quello già utilizzato nel corso per la trattazione delle cascate informative. Tale modello è formato dai seguenti componenti:

  • Due alternative \(x, y\).

  • Due eventi, \((x > y)\) e \((y > x)\), dove il primo sta ad indicare l'evento "\(x\) è la scelta giusta", e il secondo l'evento "\(y\) è la scelta giusta", con le seguenti probabilità

    \[P(x > y) = P(y > x) = \frac12\]

  • Due segnali \(sx\) e \(sy\), ciascuno dei quali indica la "verità" di una particolare alternativa tramite le seguenti probabilità

    \[P(sx \,\,|\,\, x) = P(sy \,\,|\,\, y) = q > \frac12\]

Iniziamo quindi la nostra analisi di tale modello calcolando la probabilità che l'alternativa \(x\) è vera se riceviamo il segnale \(sx\). Utilizzando Bayes troviamo

\[\begin{split} P(x \,\, | \,\, sx) &= \frac{P(sx \,\, | \,\, x) \cdot P(x)}{P(sx)} \\ &= \frac{P(sx \,\, | \,\, x) \cdot P(x)}{P(sx \,\, | \,\, x) \cdot P(x) + P(sx \,\, | \,\, y) \cdot P(y)} \\ &= \frac{q \cdot \frac12}{q \cdot \frac12 + (1-q) \cdot \frac12} \\ &= q \end{split}\]

Per capire come si dovrebbe comportare un votante in questa situazione consideriamo i due seguenti esperimenti

1.1 Esperimento delle Urne

Abbiamo \(2\) urne, composte come segue:

  • Una urna bianca \(\text{UB}\), composta da \(10\) palline bianche \(\text{B}\).

  • Una urna verde \(\text{UG}\), composta da \(9\) palline verdi \(\text{G}\) e \(1\) pallina bianca \(\text{B}\).

Inizialmente si sceglie in modo uniforme una delle \(2\) urne, e si fanno entrare \(3\) giocatori nella stanza. Ciascun giocatori estrae una pallina dall'urna e la rimette a posto, senza dire nulla agli altri giocatori. Una volta che tutti hanno estratto la loro pallina, i tre giocatori dicono qual'è secondo loro l'urna che è stata scelta inizialmente. Il voto finale corrisponde alla maggioranza dei singoli voti, e il premio viene dato ai partecipanti solamente se il voto finale è quello corretto.

Cosa conviene dire ad uno di questi giocatori per massimizzare la probabilità di successo? Notiamo che se il giocatore pesca la pallina verde, allora sicuramente l'urna è verde, e quindi non abbiamo dubbi su cosa dire. Cosa succede però se la pallina pescata è di colore bianco? Continuamo il ragionamento con qualche calcolo

\[\begin{split} P(\text{UB} \,\, | \,\, \text{B}) &= \frac{P(\text{B} \,\, | \,\, \text{UB}) \cdot P(\text{UB})}{P(\text{B} \,\, | \,\, \text{UB}) \cdot P(\text{UB}) + P(\text{B} \,\, | \,\, \text{UG}) \cdot P(\text{UG})} \\ &= \frac{1 \cdot \frac12}{1 \cdot \frac12 + \frac1{10} \cdot \frac12} \\ &= \frac{10}{11} \end{split}\]

Dunque la probabilità ci dovrebbe suggerire che nel caso in cui il giocatore pesca una pallina bianca, allora avrebbe senso dire che l'urna scelta è proprio l'urna bianca, ovvero che l'evento \(\text{UB}\) è vero.

Notiamo però che dire \(\text{UB}\) avrebbe un potenziale impatto nel risultato finale solamente nel caso in cui gli altri due partecipanti votano in modo discorde, e questo succede se e solo se uno dei due ha pescato una pallina verde. Ma se uno dei due ha pescato una pallina verde, allora l'urna scelta è proprio quella verde, in quanto \(P(\text{UG} \,\, | \,\, \text{G}) = 1\). Ma allora mi conviene sempre votare \(\text{UG}\), anche se il mio segnale privato mi suggerirebbe altrimenti.

Nota Bene: Il ragionamento appena svolto è valido se si assume che gli altri due giocatori sono onesti.

1.2 Esperimento della Giuria

Negli Stati Uniti d'America, per condannare una persona è necessario che tutti siano d'accordo, in quanto condannare un innocente (evento \(I\)), è considerato peggio di rilasciare un colpevole (evento \(C\)).

Formalizzando, troviamo un modello simile a quello visto prima

  • \(P(C) = P(I) = \frac12\)

  • \(P(C \,\, | \,\, SC) = P(I \,\, | \,\, SI) = q > \frac12\)

Supponiamo poi di avere \(k\) giurati. Notiamo che anche se ricevo un segnale di innocenza \(SI\), l'unico caso in cui il mio voto influenza il risultato finale è quando tutti votano colpevole. Supponendo di considerare \(!SI\) come l'evento "solo io ho ricevuto un segnale di innocenza", troviamo che

\[\begin{split} P(I \,\, | \,\, !SI) &= \frac{P(!SI \,\, | \,\, I) \cdot P(I)}{P(!SI \,\, | \,\, I) \cdot P(I) + P(!SI \,\, | \,\, C) \cdot P(C)} \\ &= \frac{q \cdot (1-q)^{k-1} \cdot \frac12}{q \cdot (1-q)^{k-1} \cdot \frac12 + (1-q) \cdot q^{k-1} \cdot \frac12} \\ &= \frac{(1-q)^{k-2}}{(1-q)^{k-2} + q^{k-2}} \\ &= \frac{\big(\frac{1-q}{q}\big)^{k-2}}{\big(\frac{1-q}{q}\big)^{k-2} + 1} \\ \end{split}\]

Notando che da \(q > 1/2\) segue che \((1-q)/q < 1\), otteniamo che

\[\lim\limits_{k \to \infty}{P(I \,\, | \,\, !SI)} = 0\]

Questo significa che se il mio è l'unico segnale di innocenza, allora mi conviene votare in modo non sincero.

Nota Bene: Nuovamente, il ragionamento appena fatto assume che gli altri giurati votano in modo sincero.

2 Teorema della Giuria di Condorcet

Consideriamo lo stesso modello analizzato negli ultimi due esperimenti

  • Abbiamo due alternative \(x, y\) tali che

    \[P(x > y) = P(y > x) = \frac12\]

  • Abbiamo due segnali \(sx, sy\) tali che

    \[P(sx \,\, | \,\, x) = P(sy \,\, | \,\, y) = q > \frac12\]

Teorema: Se \(x > y\) e ogni votante \(i \in \{1, ..., k\}\) vota in modo sincero in accordo con il segnale che riceve, allora a.s. (almost surely) vale la seguente cosa

\[\lim\limits_{k \to \infty} \frac{|\{i \in [1, ..., k]: \,\, x >_i y \}|}{k} = q\]

dove con a.s. intendiamo che

\[\lim\limits_{k \to \infty} \,\,\, P\bigg[\,\, \frac{|\{i \in [1, ..., k]: \,\, x >_i y \}|}{k} = q \,\, \bigg] = 1\]

Osservazione: Dire a.s. (almost surely) è meno forte che dire w.h.p. (with high probability). Infatti, nel caso con teorema, avremmo detto w.h.p se avessimo avuto che

\[P\bigg[\,\, \frac{|\{i \in [1, ..., k]: \,\, x >_i y \}|}{k} = q \,\, \bigg] \geq 1 - \frac{1}{k^{\alpha}}\]

con \(\alpha\) costante.