title: Set di Smith
text: # 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.
  
  