Smith set

In kiessystemen, de Smith set, vernoemd naar John H. Smith, maar ook wel bekend als de top-cyclus, is de kleinste niet-lege verzameling van de kandidaten in een bepaalde verkiezing, zodanig dat elke lid verslaat elke kandidaat buiten de set in een paarsgewijze verkiezing. De Smith-set biedt een optimale keuze voor een verkiezingsuitslag. Stemsystemen die altijd een kandidaat uit de Smith-set kiezen, voldoen aan het Smith-criterium en zouden "Smith-efficiënt" zijn.

Een set kandidaten waarbij elk lid van de set elk lid buiten de set verslaat, staat bekend als een dominerende verzameling .

Eigendommen

• De Smith-set bestaat altijd en is goed gedefinieerd. Er is slechts één kleinste dominerende set, aangezien dominerende sets genest en niet leeg zijn en de set kandidaten eindig is.
• De Smith-set kan meer dan één kandidaat hebben, hetzij vanwege paarsgewijze stakingen of vanwege cycli, zoals in de paradox van Condorcet .
• De Condorcet-winnaar, als die er is, is het enige lid van de Smith-set. Als er zwakke Condorcet-winnaars zijn, zitten ze in de Smith-set.
• De Smith-set is altijd een subset van de door de wederzijdse meerderheid aanbevolen groep kandidaten, als die bestaat.

Algoritmen

De Smith-set kan worden berekend met het Floyd-Warshall-algoritme in de tijd Θ <math>(n^3)</math> . Het kan ook worden berekend met behulp van een versie van Kosaraju's algoritme of Tarjan's algoritme in de tijd Θ <math>(n^2)</math> .

Het kan ook worden gevonden door een paarsgewijze vergelijkingsmatrix te maken met de kandidaten gerangschikt op hun aantal paarsgewijze overwinningen minus paarsgewijze nederlagen (een Copeland-methode rangschikking), en vervolgens te zoeken naar het kleinste celblok linksboven dat zo kan worden bedekt dat alle cellen rechts van deze cellen paarsgewijze overwinningen laten zien. Alle kandidaten links van deze cellen staan in de Smith-set.

Voorbeeld met behulp van de Copeland-ranking:

Verliezen en onderscheiden zijn vetgedrukt

	A	B	C	D	E	F	G
A	---	Winnen	Verliezen	Winnen	Winnen	Winnen	Winnen
B	Verliezen	---	Winnen	Winnen	Winnen	Winnen	Winnen
C	Winnen	Verliezen	---	Verliezen	Winnen	Winnen	Winnen
D	Verliezen	Verliezen	Winnen	---	onderscheiden	Winnen	Winnen
E	Verliezen	Verliezen	Verliezen	onderscheiden	---	Winnen	Winnen
F	Verliezen	Verliezen	Verliezen	Verliezen	Verliezen	---	Winnen
G	Verliezen	Verliezen	Verliezen	Verliezen	Verliezen	Verliezen	---

A verliest van C, dus alle kandidaten van A tot en met C (A, B en C) worden bevestigd in de Smith-set. Er is één matchup waarbij een kandidaat waarvan al is bevestigd dat hij in de Smith-set zit, iemand verliest of vastbindt die nog niet is bevestigd in de Smith-set: C verliest tegen D; dus D is bevestigd in de set van Smith. Nu is er nog een dergelijke matchup: D is onderscheiden met E, dus E wordt toegevoegd aan de Smith-set. Omdat alle A tot en met E alle kandidaten verslaan waarvan nog niet is bevestigd dat ze in de Smith-set zitten, wordt nu bevestigd dat de Smith-set A tot en met E is.

Zie ook

• Condorcet-criterium
• Condorcet-methode
• Landau set
• Voorafgaande bestelling
• Gedeeltelijke bestelling

Referenties

• Ward, Benjamin (1961). Majority Rule and Allocation. Journal of Conflict Resolution 5 (4): 379–389. DOI:10.1177/002200276100500405.
• Smith, J.H. (1973). Aggregation of Preferences with Variable Electorates. Econometrica 41 (6): 1027–1041. DOI:10.2307/1914033. Introduceert een versie van een gegeneraliseerd Condorcet-criterium waaraan wordt voldaan wanneer paarsgewijze verkiezingen zijn gebaseerd op eenvoudige meerderheidskeuze, en voor elke dominante set heeft elke kandidaat in de set collectief de voorkeur boven elke kandidaat die niet in de set zit. Maar Smith bespreekt niet het idee van een kleinste dominante set.
• Fishburn, Peter C. (1977). Condorcet Social Choice Functions. SIAM Journal on Applied Mathematics 33 (3): 469–489. DOI:10.1137/0133030. Versmalt Smiths algemene Condorcet-criterium tot de kleinste dominante set en noemt het Smith's Condorcet-principe.
• Schwartz, Thomas, The Logic of Collective Choice, Columbia University Press, New York , 1986. Bespreekt de Smith-set (genaamd GETCHA) en de Schwartz-set (genaamd GOTCHA) als mogelijke normen voor een optimale collectieve keuze.

Externe links

• Voorbeeldalgoritmen om de Smith-set te berekenen