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 Θ ${\displaystyle (n^{3})}$ . Può anche essere calcolato usando una versione dell'algoritmo di Kosaraju o l'algoritmo di Tarjan nel tempo Θ ${\displaystyle (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:

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

• Ward, Benjamin, Majority Rule and Allocation, in Journal of Conflict Resolution, vol. 5, n. 4, 1961, pp. 379-389, DOI:10.1177/002200276100500405.
• Smith, J.H., Aggregation of Preferences with Variable Electorates, in Econometrica, vol. 41, n. 6, The Econometric Society, 1973, 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.
• Fishburn, Peter C., Condorcet Social Choice Functions, in SIAM Journal on Applied Mathematics, vol. 33, n. 3, 1977, 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.
• Thomas Schwartz, The Logic of Collective Choice, New York, Columbia University Press, 1986. 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

• Algoritmi di esempio per calcolare il set di Smith Archiviato il 17 giugno 2017 in Internet Archive.