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.

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

Collegamenti esterni

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