Set di Smith
# Set di Smith

Nei sistemi di voto, il set di Smith, che prende il nome da John H. Smith, è il più piccolo gruppo non vuoto di candidati in una particolare elezione tale che ciascuno dei membri di set sconfigge tutti i candidati al di fuori del set in elezioni a coppie (cuando solo i due candidati sono nella elezione). Il set Smith offre uno standard di scelta ottimale per un risultato elettorale. I sistemi di voto che eleggono sempre un candidato dal set di Smith superano il criterio di Smith e si dice che siano "Smith-efficienti".

Un set di candidati in cui ogni membro del set sconfigge a coppie ogni membro al di fuori del set è noto come set dominante.

## Proprietà

* Il set Smith esiste sempre ed è ben definito. C'è solo un set dominante più piccolo poiché i set dominanti sono nidificati e non vuoti e il set di candidati è finito.
* Il set di Smith può avere più di un candidato, sia per pareggio di coppia o per cicli, come nel paradosso di Condorcet.
* Il vincitore di Condorcet, se presente, è l'unico membro del set Smith. Se esistono vincitori deboli di Condorcet, allora sono nel set di Smith.
* Il set di Smith è sempre un sottoinsieme del set di candidati preferito dalla maggioranza reciproca, se ne esiste uno.

## Confronto con il set di Schwartz

Il set di Schwartz è strettamente correlato ed è sempre un sottoinsieme del set Smith. Il set Smith è più grande se e solo se un candidato nel set Schwartz ha un pareggio in coppia con un candidato che non è nel set Schwartz.

## Algoritmi

Il set di Smith può essere calcolato con l'algoritmo Floyd – Warshall in tempo Θ $(n^{3})$ . Può anche essere calcolato usando una versione dell'algoritmo di Kosaraju o l'algoritmo di Tarjan nel tempo Θ $(n^{2})$.

Può anche essere trovato creando una matrice di confronto a coppie con i candidati classificati in base al loro numero di vittorie a coppie meno sconfitte a coppie (una classifica del metodo Copeland) e quindi cercando il più piccolo quadrato di celle in alto a sinistra che può essere coperto in modo tale che tutte le celle a destra di queste celle mostrano vittorie a coppie. Tutti i candidati nominati a sinistra di queste celle si trovano nel set di Smith.

Esempio: supponiamo che i candidati A, B e C siano nel set di Smith, ciascuno battendo in coppia uno degli altri, ma tutti e 3 i battiti in coppia D ed E. A, B e C verrebbero posizionati nelle prime 3 file (supponiamo che vengono inseriti in questo ordine per questo esempio) della tabella di confronto a coppie, e quindi si vedrebbe che coprendo tutte le celle da "A battiti A" (la cella che confronta A con se stesse) a "C battiti C", tutto le celle a destra (le celle che confrontano A, B e C con D ed E) mostrerebbero vittorie a coppie, mentre nessun gruppo di celle più piccolo potrebbe farlo, quindi A, B e C sarebbero nel set di Smith.

Esempio con la classificazione di Copeland:

Perdite e pareggio in grassetto :

| | A | B | C | D | E | F | G |
| - | - | - | - | - | - | - | - |
| A | --- | Gana | Perde | Gana | Gana | Gana | Gana |
| B | Perde | --- | Gana | Gana | Gana | Gana | Gana |
| C | Gana | Perde | --- | Perde | Gana | Gana | Gana |
| D | Perde | Perde | Gana | --- | Pareggio | Gana | Gana |
| E | Perde | Perde | Perde | Pareggio | --- | Gana | Gana |
| F | Perde | Perde | Perde | Perde | Perde | --- | Gana |
| G | Perde | Perde | Perde | Perde | Perde | Perde | --- |

A perde a C, in questo modo tutti i candidati dal A a C (A, B, e C) sono nel set di Smith. È una coppia in che uno di questi candidati perde o pareggia con alcuno che non è uno di questi candidati: C perde a D, così anche D è nel set. Un'altra coppia come le ultime esiste ora: D pareggia con E, così E è nel set di Smith. Ora tutti i candidati che sono confermati nel set sconfitte tutti i candidati che già non stanno nel set, in questo modo tutti candidati dal A a E stanno nel set di Smith.

