Zestaw Smitha - Smith set

W systemach głosowania The Zbiór Smitha , nazwany na cześć Johna H. Smith , ale również znany jako cykl górę lub jako ogólnego Top wyboru NMP (skupić), to najmniejsza niepusty zbiór kandydatów w danym wyborów tak, że każda członek pokonuje każdego kandydata spoza zestawu w wyborach parami. Zestaw Smitha zapewnia jeden standard optymalnego wyboru dla wyniku wyborów. Systemy głosowania, które zawsze wybierają kandydata z zestawu Smitha, spełniają kryterium Smitha i są określane jako „skuteczne w stosunku do Smitha ” lub spełniające kryterium Smitha .

Zbiór kandydatów, z których każdy w parach pokonuje każdego kandydata spoza zbioru, jest znany jako zbiór dominujący .

Zestaw Smith może być postrzegane jako definiowanie sposobu głosowania ( metoda Smith ), który jest najczęściej napotykanych podczas przedłużony o IRV tie-breaku jak Smith / IRV lub jako Tideman Alternatywna lub przez Minimax jako Smith / Minimax .

Właściwości zbiorów Smitha

• Zbiór Smitha zawsze istnieje i jest dobrze zdefiniowany (patrz następna sekcja).
• Zbiór Smitha może mieć więcej niż jednego kandydata, albo z powodu powiązań parami, albo z powodu cykli, tak jak w paradoksie Condorceta .
• Zwycięzca Condorcet , jeżeli taki istnieje, jest jedynym członkiem zestawu Smith. Jeśli istnieją słabi zwycięzcy Condorceta , to są w zestawie Smitha.
• Zbiór Smitha jest zawsze podzbiorem zbioru kandydatów z obopólną większością - preferowanych, jeśli taki istnieje.

Własności zbiorów dominujących

Twierdzenie: Zbiory dominujące są zagnieżdżone ; to znaczy, z dowolnych dwóch dominujących zestawów w wyborach, jeden jest podzbiorem drugiego.

Dowód: Przypuśćmy, że istnieją dwa dominujące zbiory, D i E , z których żaden nie jest podzbiorem drugiego. Następnie musi istnieć kandydatów d ∈ D , E ∈ E tak, że d ∉ E i e ∉ D . Ale według hipotezy d pokonuje każdego kandydata nie w D (włącznie z e ), podczas gdy e pokonuje każdego kandydata nie w E (włącznie z d ), co jest sprzecznością. ∎

Wniosek: Z tego wynika, że ​​zbiór Smitha jest najmniejszym niepustym zbiorem dominującym i jest dobrze zdefiniowany.

Twierdzenie: Jeśli D jest zbiorem wyróżniającym się, to nie jest jakiś próg θ _D takie, że elementy D są właśnie kandydaci, których Copeland wyniki są co najmniej θ _D . (Wynik Copelanda kandydata to liczba innych kandydatów, których pokonuje, plus połowa liczby innych kandydatów, z którymi jest związany.)

Dowód: Wybierz d jako element D z minimalnym wynikiem Copelanda i zidentyfikuj ten wynik za pomocą θ _D . Teraz załóżmy, że jakiś kandydat e ∉ D ma Copeland nie mniej niż zdobyć θ _D . Następnie, ponieważ d należy do D, a e nie, wynika z tego, że d pokonuje e ; oraz w celu e „ s Copeland zdobyć być przynajmniej równa d ” s, musi być jakiś trzeci kandydat f przeciwko któremu e dostaje lepszy wynik niż robi d . Jeśli f ∈ D , to mamy element D , który nie pokona e , i jeśli f ∉ D wtedy mamy poza kandydat D kogo d nie pokona, co prowadzi do sprzeczności w obu kierunkach. ∎

Porównanie zestawu Schwartza

Zestaw Schwartz , znany jako ogólnego optymalnego wyboru aksjomatu lub Gocha, jest ściśle związane i zawsze jest podzbiorem zbioru Smitha. Zestaw Smitha jest większy wtedy i tylko wtedy, gdy kandydat w zestawie Schwartza ma remis w parach z kandydatem, który nie znajduje się w zestawie Schwartza.

Zbiór Smitha można skonstruować ze zbioru Schwartza przez wielokrotne dodawanie dwóch typów kandydatów, aż nie będzie już takich kandydatów poza zbiorem:

• kandydaci, którzy mają powiązania parami z kandydatami w zbiorze,
• kandydaci, którzy pokonali kandydata w zestawie.

Należy zauważyć, że kandydaci drugiego typu mogą istnieć dopiero po dodaniu kandydatów pierwszego typu.

Kryterium Smitha

Kryterium Smitha spełnia każda metoda głosowania, której zwycięzca zawsze należy do zestawu Smitha. Każda metoda, która spełnia kryterium Smitha, musi również spełniać kryterium Condorceta ; stąd każda metoda (taka jak IRV ), która nie jest spójna z Condorcetem, musi również nie spełniać kryterium Smitha. Minimax jest najbardziej znaną metodą Condorceta, która nie spełnia kryterium Smitha.

Obliczanie zbioru Smitha

Podane powyżej własności logiczne zbiorów dominujących mogą posłużyć do skonstruowania efektywnego algorytmu obliczania zbioru Smitha. Widzieliśmy, że dominujące zbiory są zagnieżdżone w partyturze Copelanda. Wynika z tego, że dostosowując próg Copelanda, można pracować nad zbiorami zagnieżdżonymi w kolejności rosnącej wielkości, aż do osiągnięcia zbioru dominującego; a ten zbiór jest koniecznie zbiorem Smitha. Darlingon szkicuje tę metodę.

Testowanie, czy zbiór jest dominującym zbiorem na każdym etapie, może powtórzyć niektóre obliczenia, ale można tego dość łatwo uniknąć, prowadząc do algorytmu, którego czynnik pracy jest kwadratowy w liczbie kandydatów.

Szczegółowy algorytm

Algorytm można szczegółowo przedstawić na przykładzie. Załóżmy, że macierz wyników wygląda następująco:

Tutaj wpis w głównej tabeli wynosi 1, jeśli pierwszy kandydat był preferowany względem drugiego przez większą liczbę wyborców niż preferował drugiego kandydata względem pierwszego; 0 jeśli zachodzi przeciwna relacja; oraz1/2jeśli jest remis. Ostatnia kolumna podaje wynik Copelanda pierwszego kandydata.

Algorytm obliczania zbioru Smitha jest aglomeracyjny: zaczyna się od zbioru Copelanda, który na pewno jest jego podzbiorem, ale często będzie mniejszy, i dodaje elementy, dopóki nie będą już potrzebne. Pierwszym krokiem jest posortowanie kandydatów według punktów:

Patrzymy na najwyższy wynik – 5 – i bierzemy pod uwagę kandydatów (zwycięzców Copelanda), których wynik jest przynajmniej tak wysoki, tj. {A,D}. Te z pewnością należą do zestawu Smitha, a kandydaci, których nie pokonają, będą musieli zostać dodani. Aby znaleźć niepokonanych kandydatów, przyglądamy się komórkom w tabeli poniżej kwadratu 2×2 w lewym górnym rogu zawierającego {A,D} (kwadrat ten jest oznaczony złamaną ramką): w tabeli dane komórki są zacieniowane na żółto. Musimy znaleźć najniższy (pozycyjny) niezerowy wpis wśród tych komórek, czyli komórkę w wierszu G. Wszyscy kandydaci aż do tego rzędu i wszystkie niższe rzędy z tym samym wynikiem muszą zostać dodane do zbioru, który rozszerza się do {A,D,G}.

Teraz przyjrzymy się nowym komórkom, które należy wziąć pod uwagę, czyli znajdującym się poniżej lewego górnego kwadratu zawierającego {A,D,G}, ale z wyłączeniem tych z dwóch pierwszych kolumn, które już uwzględniliśmy. Komórki, które wymagają uwagi, są zacieniowane na jasnoniebiesko. Tak jak poprzednio, lokalizujemy pozycyjnie najniższy niezerowy wpis wśród nowych komórek, dodając do niego wszystkie wiersze i wszystkie wiersze z tym samym wynikiem do rozszerzonego zbioru, który teraz zawiera {A,D,G,C} .

Powtarzamy operację dla nowych komórek poniżej czterech członków, o których wiadomo, że należą do zbioru Smitha. Są one zacieniowane na różowo i pozwalają nam znaleźć kandydatów, których nie pokona żaden z {A,D,G,C}. Znowu jest tylko jeden, F, którego dodajemy do zestawu.

Komórki, które są brane pod uwagę, są zacieniowane na bladozielony kolor, a ponieważ wszystkie ich wpisy mają wartość zero, nie musimy dodawać żadnych nowych kandydatów do zbioru, co jest zatem ustalone jako {A,D,G,C,F}. A zauważając, że wszystkie wpisy w czarnej skrzynce są zerowe, mamy potwierdzenie, że wszyscy kandydaci nad nią pokonują wszystkich kandydatów w niej.

Poniższa funkcja C ilustruje algorytm przez zwrócenie liczności zbioru Smitha dla danej macierzy podwojonych wyników r i tablicy s podwojonych wyników Copelanda. Jest n kandydatów; r _{i j} wynosi 2, jeśli więcej wyborców woli i do j niż j do i , 1, jeśli liczby są równe, i 0, jeśli więcej wyborców woli j do i niż woli i do j  ; s _i jest sumą nad j z r _{i j} . Zakłada się, że kandydaci są sortowani w porządku malejącym wyniku Copelanda.

 int smithset(int **r,int *s,int n)
 { int row,col,lhs,rhs ;
   for(rhs=1,lhs=0;lhs<rhs;lhs=rhs,rhs=row+1)
   { for(;rhs<n&&s[rhs]==s[rhs-1];rhs++) ; /* this line optional */
     for(col=rhs,row=n;col==rhs&&row>=rhs;row--) for(col=lhs;col<rhs&&r[row-1][col]==0;col++) ; 
   }
   return lhs ; 
 }

Metoda Smitha

Zestaw Smitha może być postrzegany jako definiujący metodę rankingowego głosowania , w której...

Wszyscy członkowie zestawu Smitha są zwycięzcami. Zwykle w połączeniu z inną metodą.

Godnym uwagi przykładem kombinacji metody Smitha jest Smith/IRV , która redukuje pole kandydatów do zbioru Smitha, a następnie wykorzystuje natychmiastowe głosowanie w celu rozstrzygnięcia remisu, jeśli ten zbiór ma więcej niż jeden element. Bardziej skomplikowaną metodą (również przywołującą IRV) jest Alternatywa Tidemana , której artykuł zawiera tabelę wymieniającą ważne właściwości tych dwóch metod. Smith/ minimax używa znacząco odmiennej procedury zrywania więzi.

Eliminacja więzi

Komponent IRV zarówno Smitha/IRV, jak i Alternatywy Tidemana od czasu do czasu napotka remis na najniższym miejscu wśród pierwszych preferencji (prawdopodobieństwo tego staje się arbitralnie małe wraz ze wzrostem liczby głosujących). Kiedy powstaje taki remis, można go zerwać na różne sposoby. W przypadku Smith/IRV zestaw wszystkich kandydatów z najmniejszą liczbą głosów pierwszego rzędu, których łączna liczba głosów jest mniejsza niż wszystkich innych kandydatów, może zostać wyeliminowany bez zmiany wyniku; Alternatywa Tidemana ponownie oblicza Zestaw Smitha po każdej pojedynczej eliminacji i nie może być zoptymalizowana w ten sposób.

W natychmiastowej turze głosowania nie można zaakceptować kart do głosowania z dwoma kandydatami o tej samej randze, ale ograniczenie pola do zestawu Smitha jest możliwe, nawet jeśli wyborcy wykazali powiązania między kandydatami. Karty do głosowania z równym rankingiem pierwszego wyboru po wyeliminowaniu kandydatów innych niż Smith muszą zostać odrzucone.

Zobacz też

• Kryterium kondorcetu
• Metoda kondorceta
• Zestaw Landau
• Przed Sprzedaż
• Częściowe zamówienie

Bibliografia

Dalsza lektura

• Ward, Benjamin (1961). „Zasada większości i alokacja”. Dziennik Rozwiązywania Konfliktów . 5 (4): 379–389. doi : 10.1177/002200276100500405 . W analizie szeregowego podejmowania decyzji w oparciu o regułę większości opisuje zbiór Smitha i zbiór Schwartza.
• Smith, JH (1973). „Agregacja preferencji ze zmiennymi elektoratami”. Ekonometria . Towarzystwo Ekonometryczne. 41 (6): 1027–1041. doi : 10.2307/1914033 . JSTOR  1914033 . Wprowadza wersję uogólnionego Kryterium Condorcet, które jest spełnione, gdy wybory parami opierają się na prostym wyborze większości, a dla dowolnego zestawu dominującego każdy kandydat w zestawie jest preferowany w stosunku do kandydata spoza zestawu. Ale Smith nie omawia idei najmniejszego zbioru dominującego.
• Fishburn, Peter C. (1977). „Condorcet Social Choice Funkcje”. SIAM Journal o Matematyce Stosowanej . 33 (3): 469–489. doi : 10.1137/0133030 . Zawęża uogólnione kryterium Condorceta Smitha do najmniejszego zestawu dominującego i nazywa je Zasadą Condorceta Smitha.
• Schwartz, Thomas (1986). Logika zbiorowego wyboru . Nowy Jork: Wydawnictwo Uniwersytetu Columbia. Omówiono zestaw Smitha (o nazwie GETCHA) i zestaw Schwartza (o nazwie GOTCHA) jako możliwe standardy optymalnego wyboru zbiorowego.
• Somdeb Lahiri (nd), „Podejmowanie decyzji grupowych i wielokryterialnych”. Przedstawia niektóre właściwości zbiorów wyboru.

Zewnętrzne linki

• Przykładowe algorytmy obliczania zbioru Smitha