Wikisage is op 1 na de grootste internet-encyclopedie in het Nederlands. Iedereen kan de hier verzamelde kennis gratis gebruiken, zonder storende advertenties. De Koninklijke Bibliotheek van Nederland heeft Wikisage in 2018 aangemerkt als digitaal erfgoed.
- Wilt u meehelpen om Wikisage te laten groeien? Maak dan een account aan. U bent van harte welkom. Zie: Portaal:Gebruikers.
- Bent u blij met Wikisage, of wilt u juist meer? Dan stellen we een bescheiden donatie om de kosten te bestrijden zeer op prijs. Zie: Portaal:Donaties.
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 Θ (n3). Het kan ook worden berekend met behulp van een versie van Kosaraju's algoritme of Tarjan's algoritme in de tijd Θ (n2).
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:
| 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
Externe links
Referenties
- Ward, Benjamin(1961). Majority Rule and Allocation. Journal of Conflict Resolution 5 (4): 379–389 DOI: 10.1177/002200276100500405
- John H. Smith (mathematician) (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.
