Smithovo kritérium - Smith criterion

Kritériem Smith (někdy generalizované condorcetovo kritérium , ale může mít i jiné významy) je hlasovací systémy kritériem je definován tak, že je splněn, pokud hlasovací systém vždy volí kandidáta, který je v sadě Smith , což je nejmenší non-prázdná podmnožina kandidáti tak, že každý kandidát v podmnožině je preferován většinou před každým kandidátem, který není v podmnožině. (Říká se, že kandidát X je preferován většinou před jiným kandidátem Y, pokud v soutěži jeden na jednoho mezi X a Y počet voličů, kteří dávají přednost X před Y, převyšuje počet voličů, kteří dávají přednost Y před X. ) Smithova sada je pojmenována pro matematika Johna H Smitha , jehož verze kritéria Condorcet je ve skutečnosti silnější než ta definovaná výše pro funkce sociálního zabezpečení. Benjamin Ward byl pravděpodobně první, kdo psal o této sadě, kterou nazýval „většinová“.

Smithova sada se také nazývá vrcholný cyklus . Termín vrcholný cyklus však může být poněkud zavádějící, protože Smithova sada může obsahovat kandidáty, kteří necyklují. Pokud například existuje vítěz Condorcet, necykluje se s žádnými alternativami, a když se sada Smitha skládá pouze ze dvou alternativ, které se spojují v páru, tyto dvě necyklují s žádnými alternativami.

odhodlání

Smithovu sadu lze vypočítat pomocí Floyd -Warshallova algoritmu v čase Θ ( n ³ ) nebo Kosarajuova algoritmu v čase Θ ( n ² ).

Příklad

Když existuje vítěz Condorcet -kandidát, který dává přednost většině před všemi ostatními kandidáty-Smithova sada se skládá pouze z tohoto kandidáta. Zde je příklad, ve kterém není vítěz Condorcet: Existují čtyři kandidáti: A, B, C a D. 40% voličů řadí D> A> B> C. 35% voličů řadí B> C> A> D. 25% voličů řadí C> A> B> D. Smithova sada je {A, B, C}. Všichni tři kandidáti v sadě Smithů mají přednost před D (protože 60% řadí každého z nich před D). Sada Smith není {A, B, C, D}, protože definice vyžaduje nejmenší podmnožinu, která splňuje ostatní podmínky. Sada Smith není {B, C}, protože B není preferována většinou před A; 65% pořadí A nad B. (atd.)

pro \ con	A	B	C	D
A	-	65	40	60
B	35	-	75	60
C	60	25	-	60
D	40	40	40	-
max. opp	60	65	75	60
minimax	60			60

V tomto případě za minimaxu A a D tie; pod Smithem/Minimaxem vítězí A.

Ve výše uvedeném příkladu jsou tři kandidáti v sadě Smithů ve většinovém cyklu „kámen/papír/nůžky“ : A je zařazeno nad B 65% většinou, B je hodnoceno nad C 75% většinou a C je zařazen nad A 60% většinou.

Další kritéria

Jakákoli volební metoda, která splňuje Smithovo kritérium, také vyhovuje Condorcetovu kritériu , protože pokud existuje Condorcetský vítěz, pak je jediným kandidátem v Smithově sadě. Očividně to znamená, že nesplnění kritéria Condorcet automaticky znamená i nedodržení Smithova kritéria. Tyto sady navíc splňují kritérium poraženého Condorcet . To je pozoruhodné, protože ani některé metody Condorcet ne (Minimax). Z toho také vyplývá kritérium vzájemné většiny , protože Smithova sada je podmnožinou sady MMC.

Smithova sada a Schwartzova sada jsou v literatuře někdy zaměňovány. Miller (1977, s. 775) uvádí GOCHA jako alternativní název pro sadu Smith, ale ve skutečnosti odkazuje na sadu Schwartz. Schwartzova množina je ve skutečnosti podmnožinou Smithovy množiny (a rovná se jí, pokud mezi členy Smithovy množiny neexistují žádné párové vazby).

Vyhovující metody

Smithovo kritérium splňují hodnocené páry , Schulzeho metoda , Nansonova metoda , metoda Robertových pravidel pro hlasování o návrzích a dodatcích a několik dalších metod.

Metody nesplňující kritérium Condorcet také nesplňují kritérium Smith. Některé metody Condorcet, jako například Minimax , také nesplňují Smithovo kritérium.

Metody hlasování, které nesplňují Smithovo kritérium, lze upravit tak, aby splňovalo (obvykle na úkor jiných kritérií). Jedním z přístupů je použít metodu hlasování pouze na sadu Smith. (Jinými slovy, začněte odstraněním kandidátů, kteří nejsou v sadě Smithů, z hlasování.) Například metoda hlasování Smith/Minimax je aplikace Minimaxu na kandidáty ze sady Smithů. Dalším přístupem je zvolit člena Smithovy sady, který je nejvyšší v pořadí dokončení hlasovací metody.

Příklady

Minimax

Kritérium vzájemné většiny#Minimax

Smithovo kritérium implikuje kritérium vzájemné většiny, takže selhání Minimaxu při splnění kritéria vzájemné většiny je také nesplněním Smithova kritéria. Všimněte si, že množina S = {A, B, C} v tomto příkladu je Smithova sada a D je vítěz Minimaxu.

Viz také

• Nezávislost alternativ ovládaných Smithem

Reference

1. ^ JH Smith, „Agregace preferencí s proměnlivým elektorátem“,Econometrica, sv. 41, s. 1027–1041, 1973.
2. ^ Benjamin Ward, „Majoritní pravidlo a alokace“,The Journal of Conflict Resolution, Vol. 5, č. 4. (1961), s. 379–389.