Visualizza wikitesto di Set di Smith

Nei [[Sistema elettorale|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 [[Metodo Condorcet|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 di Floyd-Warshall|algoritmo Floyd – Warshall]] in tempo '''[[O-grande|Θ]]''' <math>(n^3)</math> . Può anche essere calcolato usando una versione [[Algoritmo di Kosaraju-Sharir|dell'algoritmo]] di [[Algoritmo di Kosaraju-Sharir|Kosaraju]] o [[Algoritmo di Tarjan per le componenti fortemente connesse|l'algoritmo di Tarjan]] nel tempo '''[[O-grande|Θ]]''' <math>(n^2)</math>. 

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 [[Metodo Copeland|Copeland]]: 
{| class="wikitable"
|+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.

== Bibliografia ==

* {{Cita pubblicazione|autore=Ward, Benjamin|anno=1961|titolo=Majority Rule and Allocation|url=https://archive.org/details/sim_journal-of-conflict-resolution_1961-12_5_4/page/379|rivista=Journal of Conflict Resolution|volume=5|numero=4|pp=379-389|doi=10.1177/002200276100500405}} 
* {{Cita pubblicazione|autore=Smith, J.H.|linkautore=John H. Smith (mathematician)|anno=1973|titolo=Aggregation of Preferences with Variable Electorates|url=https://archive.org/details/sim_econometrica_1973-11_41_6/page/1027|rivista=Econometrica|editore=The Econometric Society|volume=41|numero=6|pp=1027-1041|doi=10.2307/1914033}}  Introduce una versione di un criterio generalizzato Condorcet che è soddisfatto quando le elezioni a coppie si basano sulla scelta della maggioranza semplice e, per qualsiasi set dominante, qualsiasi candidato nel set è collettivamente preferito a qualsiasi candidato non nel set. Ma Smith non discute l'idea di un insieme dominante più piccolo. 
* {{Cita pubblicazione|autore=Fishburn, Peter C.|anno=1977|titolo=Condorcet Social Choice Functions|rivista=SIAM Journal on Applied Mathematics|volume=33|numero=3|pp=469-489|doi=10.1137/0133030}}  Il Criterio di Condorcet generalizzato di Narrows Smith al più piccolo set dominante e lo chiama Principio di Condorcet di Smith. 
* {{Cita libro|autore=Schwartz|nome=Thomas|titolo=The Logic of Collective Choice|url=https://archive.org/details/logicofcollectiv0000schw|anno=1986|editore=Columbia University Press|città=New York}}  Discute il set di Smith (chiamato GETCHA) e il set di Schwartz (chiamato GOTCHA) come possibili standard per una scelta collettiva ottimale. 

== Voci correlate ==
* [[Metodo Condorcet]] 
* [[Preordine]] 

== Collegamenti esterni ==
* [http://wiki.electorama.com/wiki/Maximal_elements_algorithms Algoritmi di esempio per calcolare il set di Smith] {{Webarchive|url=https://web.archive.org/web/20170617014652/http://wiki.electorama.com/wiki/Maximal_elements_algorithms |date=17 giugno 2017 }}

[[Categoria:Sistemi elettorali]]