Metoda Schulzego

right|thumb|Metoda Schulzego obrazowo: 1. Pierwsze opuszczenie (strategia heurystyczna ustala zbiór Schwartza, po czym kolejno opuszcza najsłabszą przegraną, aż do skutku) right|thumb|2. Kolejne opuszczenie right|thumb|3. E wygrywa, ponieważ wygrało wszystkie zestawienia parami Metoda Schulzego (ang.: Schulze method, Schwartz Sequential Dropping (SSD), Cloneproof Schwartz Sequential Dropping (CSSD), Beatpath Method, Beatpath Winner, Path Voting, Path Winner) – metoda wyborcza, czyli oddawania i liczenia głosów, stworzona w 1997 przez Markusa Schulzego w celu wybierania jednego zwycięzcy w głosowaniu preferencyjnym.

Głosowanie odbywa się przez wpisanie liczby przy każdym kandydacie. Wyborca oddaje głos, oznaczając wybranych kandydatów numerami: zaznaczając '1' obok najbardziej preferowanego kandydata, '2' obok następnego w kolejności preferencji itd.

Metoda ta może zostać użyta także w celu wyłonienia listy zwycięzców.

Jeżeli w zestawieniach kandydatów parami, w wyniku tych zestawień jeden z nich jest preferowany, metoda Schulzego gwarantuje, że ten kandydat wygra wybory. Dzięki tej właściwości metoda Schulzego z racji definicji jest metodą CondorcetaJean Condorcet (17 wrze 1743 – 28 mar 1794): ang. Condorcet method.

Jako pierwszy metody wyłaniania zwycięzcy wyborczego na zasadzie oddawania głosu jako uszeregowanych preferencji opracował już w XVIII wieku francuski matematyk Jean Condorcet. Rajmund Lullus, średniowieczny filozof z Majorki, zaproponował podobne metody już w XIII wieku, przy czym swoje obliczenia wykonywał iteratywnie (parami, po kolei), budując przy tym maszyny logiczne. Z kolei ok. r. 1670 niemiecki matematyk Gottfried Leibniz zastosował metody Lullusa do liczenia, nadając im nazwę ars combinatorica, tworząc przy okazji rodzaj kodu binarnego. Z tego powodu Lull jest dziś uważany za ojca informatyki, a w jego metodach ustalono zapożyczenia z matematyki afrykańskiej.

Metoda Schulzego stała się najbardziej rozpowszechnioną metodą Condorceta. Obecnie jest ona używana przez szereg organizacji, w tym: Wikimedia, Debian, Gentoo i Software in the Public Interest.

Szereg rozmaitych strategii heurystycznych zostało zaproponowanych przez informatyków w celu sprawnego obliczenia wyniku wyborów zgodnie z metodą Schulzego. Najważniejsze z nich to tzw. ścieżkowa (ang. path heuristic) i zbioru Schwartza (ang. Schwartz set heuristic), opisane poniżej. Wszystkie strategie stosujące heurystykę obliczają tego samego zwycięzcę i różnią się od siebie tylko detalami algorytmu.

Strategia ścieżkowa (path heuristic) right|thumb|Przykładowy formularz do głosowania metodą Schulzego: Wyborca głosuje preferencyjnie, oznaczając wybranych kandydatów numerami: '1' obok najbardziej preferowanego kandydata, '2' obok następnego w kolejności preferencji, itd. Nieoznaczeni kandydaci stają się domyślnie uszeregowani według jednakowej, niższej preferencji od kogokolwiek oznaczonego

W zastosowaniu metody Schulzego (jak i innych ordynacjach preferencyjnych wyłaniającego jednego wygrywającego (ang. single-winner election methods), każdy formularz do oddawania głosu zawiera kompletny spis wszystkich biorących udział w wyborach kandydatów. Wyborca ustawia ich według preferencji, oznaczając wybranych kandydatów numerami (zaznaczając '1' obok najbardziej preferowanego kandydata, '2' obok następnego w kolejności preferencji itd.).

Wyborca może przypisać tę samą preferencję wielu kandydatom, jak i nie oznaczyć kandydata. Jeżeli wyborca nie oznaczy kandydata, znaczy to, że ściśle preferuje oznaczonych nad nieoznaczonym i że nie preferuje nikogo wśród nieoznaczonych.

Rys matematyczny Niech d[V,W] stanowi liczbę wyborców, którzy ściśle preferują kandydata V nad kandydata W.

Ścieżka prowadząca od kandydata X do kandydata Y o mocy p to ciąg kandydatów C(1),...,C(n) o następujących właściwościach:

C(1) = X i C(n) = Y. Dla wszystkich i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)]. Dla wszystkich i = 1,...,(n-1): d[C(i),C(i+1)] ≥ p. Istnieje i, 1 ≤ i ≤ n-1 takie że: d[C(i),C(i+1)] = p.

p[A,B], moc najsilniejszej ścieżki od kandydata A do kandydata B, to wartość maksymalna wśród ścieżek od kandydata A do kandydata B. Jeżeli w ogóle nie istnieje ścieżka od kandydata A do kandydata B, wtedy p[A,B] : = 0.

Kandydat D jest lepszym od kandydata E, wtedy i tylko wtedy, gdy p[D,E] > p[E,D].

Kandydat D jest potencjalnie zwycięzcą (wygrywającym) wtedy i tylko wtedy, gdy p[D,E] ≥ p[E,D] dla każdego innego kandydata E.

Pseudokod Zakładając C jako liczbę kandydatów biorących udział w wyborach, moce najsilniejszych ścieżek można obliczyć algorytmem Floyda-Warshalla. Poniższy pseudokod realizuje ten algorytm iteratywnie, od 1 do C. Jest to dokładne obliczenie, bez przybliżeń. Zdefiniowane ścieżki zaistniały jeszcze przed przeprowadzeniem tych obliczeń.

Wejście: d[i,j] stanowi liczbę wyborców, którzy ściśle preferują kandydata i nad kandydata j. Wyjście: Kandydat i stanowi potencjalnego zwycięzcę wtedy i tylko wtedy, gdy „zwycięzca[i] = prawda”.

1 od i : = 1 do C 2 od j : = 1 do C 3 jeżeli i ≠ j wtedy 4 jeżeli d[i,j] > d[j,i] wtedy 5 p[i,j] := d[i,j] 6 w przeciwnym wypadku 7 p[i,j] := 0 8 9 od i : = 1 do C 10 od j : = 1 do C 11 jeżeli i ≠ j wtedy 12 od k : = 1 do C 13 jeżeli i ≠ k oraz j ≠ k wtedy 14 p[j,k] : = max { p[j,k]; min { p[j,i]; p[i,k] } } 15 16 od i : = 1 do C 17 zwycięzca[i] := prawda 18 od j : = 1 do C 19 jeżeli i ≠ j oraz p[j,i] > p[i,j] wtedy 20 zwycięzca[i] := fałsz

Przykłady Przykład 1 45 wyborców wybiera spośród 5 kandydatów:

5 ACBED (oznacza: pięciu wyborców wybrało preferencyjnie: A > C > B > E > D) 5 ADECB 8 BEDAC 3 CABED 7 CAEBD 2 CBADE 7 DCEBA 8 EBADC

d[*,A] d[*,B] d[*,C] d[*,D] d[*,E] d[A,*] 20 26 30 22 d[B,*] 25 16 33 18 d[C,*] 19 29 17 24 d[D,*] 15 12 28 14 d[E,*] 23 27 21 31 +Macierz zestawiająca pary kandydatów i przez to, przegranych w indywidualnie zestawionych parach, wygląda następująco:

border|none|300px

Krytyczne przegrane wśród najsilniejszych ścieżek (ang. strongest paths) są tu pogrubione.

p[*,A] p[*,B] p[*,C] p[*,D] p[*,E] p[A,*] 28 28 30 24 p[B,*] 25 28 33 24 p[C,*] 25 29 29 24 p[D,*] 25 28 28 24 p[E,*] 25 28 28 31 +Moc najsilniejszych ścieżek:

Kandydat E jest potencjalnym wygrywającym, ponieważ p[E,X] ≥ p[X,E] dla każdego innego kandydata X.

Przykład 2 30 wyborców wybiera spośród 4 kandydatów:

5 ACBD 2 ACDB 3 ADCB 4 BACD 3 CBDA 3 CDBA 1 DACB 5 DBAC 4 DCBA

d[*,A] d[*,B] d[*,C] d[*,D] d[A,*] 11 20 14 d[B,*] 19 9 12 d[C,*] 10 21 17 d[D,*] 16 18 13 +Macierz zestawiająca pary kandydatów i przez to, przegranych w indywidualnie zestawionych parach, wygląda następująco:

border|none|210px

Krytyczne przegrane wśród najsilniejszych ścieżek (ang. strongest paths) są tu pogrubione.

p[*,A] p[*,B] p[*,C] p[*,D] p[A,*] 20 20 17 p[B,*] 19 19 17 p[C,*] 19 21 17 p[D,*] 18 18 18 +Moc najsilniejszych ścieżek:

Kandydat D jest potencjalnym wygrywającym, ponieważ p[D,X] ≥ p[X,D] dla każdego innego kandydata X.

Przykład 3 30 wyborców wybiera spośród 5 kandydatów:

3 ABDEC 5 ADEBC 1 ADECB 2 BADEC 2 BDECA 4 CABDE 6 CBADE 2 DBECA 5 DECAB

d[*,A] d[*,B] d[*,C] d[*,D] d[*,E] d[A,*] 18 11 21 21 d[B,*] 12 14 17 19 d[C,*] 19 16 10 10 d[D,*] 9 13 20 30 d[E,*] 9 11 20 0 +Macierz zestawiająca pary kandydatów i przez to, przegranych w indywidualnie zestawionych parach, wygląda następująco:

border|none|300px

Krytyczne przegrane wśród najsilniejszych ścieżek (ang. strongest paths) są tu pogrubione.

p[*,A] p[*,B] p[*,C] p[*,D] p[*,E] p[A,*] 18 20 21 21 p[B,*] 19 19 19 19 p[C,*] 19 18 19 19 p[D,*] 19 18 20 30 p[E,*] 19 18 20 19 +Moc najsilniejszych ścieżek:

Kandydat B jest potencjalnym wygrywającym, ponieważ p[B,X] ≥ p[X,B] dla każdego innego kandydata X.

Przykład 4 9 wyborców wybiera spośród 4 kandydatów:

3 ABCD 2 DABC 2 DBCA 2 CBDA

d[*,A] d[*,B] d[*,C] d[*,D] d[A,*] 5 5 3 d[B,*] 4 7 5 d[C,*] 4 2 5 d[D,*] 6 4 4 +Macierz zestawiająca pary kandydatów i przez to, przegranych w indywidualnie zestawionych parach, wygląda następująco:

border|none|210px

Krytyczne przegrane wśród najsilniejszych ścieżek (ang. strongest paths) są tu pogrubione.

p[*,A] p[*,B] p[*,C] p[*,D] p[A,*] 5 5 5 p[B,*] 5 7 5 p[C,*] 5 5 5 p[D,*] 6 5 5 +Moc najsilniejszych ścieżek:

Kandydat B i kandydat D są potencjalnymi wygrywającymi, ponieważ p[B,X] ≥ p[X,B] dla każdego innego kandydata X, jak i p[D,Y] ≥ p[Y,D] dla każdego innego kandydata Y.

Strategia zbioru Schwartza (Schwartz set heuristic) Zbiór Schwartza Definicja zbioru Schwartza, według zastosowania w metodzie Schulzego to:

Zbiór niepokonanych jest zbiorem kandydatów, z których żaden nie przegrał z nikim poza zbiorem. Skrajnie wewnętrzny zbiór niepokonanych to zbiór niepokonanych, który nie zawiera w sobie podzbioru stanowiącego zbiór niepokonanych. Zbiór Schwartza jest zbiorem kandydatów, którzy należą do skrajnie wewnętrznych zbiorów niepokonanych.

Rys matematyczny Wyborcy głosują przez wykonanie preferencyjnego rankingu kandydatów, jak w każdym innym głosowaniu metodą Condorceta.

Metoda Schulzego stosuje zestawianie kandydatów parami według Condorceta, w następstwie czego wybierany jest zwycięzca każdego takiego zestawienia.

Następnie, metoda Schulzego postępuje algorytmicznie w następujący sposób: w celu wybrania jednego zwycięzcy (lub w celu otrzymania rankingu):

Oblicz zbiór Schwartza przez spisanie wszystkich (bez opuszczania) przegranych.

Metoda Schulzego

Czytaj w krótszych częściach

Źródło i licencja