Metoda Schulze

Metoda Schulze jest system głosowania opracowany w 1997 roku przez Markus Schulze, który wybiera jednego zwycięzcę w głosowaniu kandydat rankingowym. Metodę można również wykorzystać do stworzenia uporządkowanej listy zwycięzców.

Jeśli kandydat wygra wszystkie swoje pojedynki w parach konfrontacji z innymi kandydatami (zwycięzca Condorceta), metoda Schulze gwarantuje, że ten kandydat wygra. Ze względu na tę właściwość metoda Schulzego jest (z definicji) metodą Condorceta . Ta właściwość nie zawsze występuje w głosach rankingowych lub ważonych. Na przykład metody Ware's Borda i Alternative Voting , mogą wyznaczyć zwycięzcę innego niż zwycięzca Condorcet.

Zaproponowano wiele heurystyk metody Schulze, czyli metod pozwalających na efektywne obliczenie zwycięzcy. Najważniejsze heurystyki to heurystyka ścieżki wygranej i heurystyka zestawu Schwartza. Mimo bardzo odmiennego wyglądu wszystkie dają ten sam efekt.

Metoda Schulzego rozwiązuje większość konfliktów generowanych przez paradoks Condorceta , ale nie gwarantuje jednego zwycięzcy. Jest używany m.in. w projekcie Debian lub w projekcie BÉPO .

Kontekst i oceny

Metodę Schulze można wykorzystać do głosowania, w którym wyborcy uszeregują kandydatów w ścisłej kolejności preferencji. Wyborca ​​może wybrać równorzędną rangę dwóch kandydatów. Jeśli pięcioma kandydatami , B , C , D i E są proponowane, Karta do głosowania może zatem wyglądać B > D > E > A > C (wyborca ściśle preferuje kandydata B do kandydata D , sam ściśle wolał kandydata E ,  itd. ) lub przy C = A > B = D = E (wyborca ​​nie wykazuje preferencji między kandydatami C i A z jednej strony ani między kandydatami B , D i E z drugiej strony, ale dwa pierwsze są ściśle preferowane do trzech ostatnich).

Matematycznie relacja preferencji dla wyborcy jest zatem całkowitym preorderem . Jest to postulat wspólny dla wszystkich systemów głosowania typu Condorcet . Intensywność preferencji nie jest brana pod uwagę: wyborca ​​nie może głosować np. A >>> A > B = C = E, aby wyrazić szeroką preferencję dla A .

Zgodnie z konwencją, gdy niektórzy kandydaci nie są sklasyfikowani, karta do głosowania jest standaryzowana  : niesklasyfikowani kandydaci są dodawani równo na dole rankingu. W poprzednim przykładzie nieprawidłowa karta do głosowania A > C jest normalizowana przez A > C > B = D = E .

Metoda Schulzego ma na celu, z arbitralnie dużej liczby takich głosów, wyłonić wybranego kandydata, najlepiej odpowiadającego woli powszechnej . Liczenie takiego głosu rozpoczyna się od ustalenia „tablicy pojedynków” lub „matrycy pojedynków”, czyli przez ustalenie dla każdej pary kandydatów ( X , Y ) liczby wyborców, którzy preferują ściśle X do Y i odwrotnie liczba wyborców preferujących ściśle Y do X .

W całym artykule odnotowujemy liczbę wyborców, którzy zdecydowanie preferują kandydata X od kandydata Y .

Z macierzy pojedynków możemy ustalić powiązany wykres pojedynków. Ten wykres jest grafem skierowanym, którego wierzchołki są kandydatami. Łuk (lub strzała) kieruje kandydata X do kandydata Y, gdy X bije ściśle Y . Jest ważona: jeśli kandydat X w porównaniu z kandydatem Y wygra n konfrontacji ( n wyborców ściśle woli X do Y ) i przegra p ( p wyborców ściśle woli Y do X ) i jeśli n > p , to łuk utworzony od X do Y jest ważone liczbą n - p .

W tej konstrukcji łuki są koniecznie ważone ściśle dodatnią liczbą całkowitą. W szczególności, jeśli istnieje równość między X i Y (jest tyle kandydatów preferujących ściśle X do Y, co kandydatów o przeciwnej preferencji), to nie ma ani strzałki od X do Y , ani strzałki od Y do X .

Przykład

Przyjmuje się, że podczas głosowania między pięcioma kandydatami A , B , C , D i E , głosowało czterdziestu pięciu wyborców. Karty do głosowania są następujące (dla uproszczenia zakładamy, że nie było remisu):

5 - A > C > B > E > D (pięciu głosujących głosowało A > C > B > E > D ) 5 - A > D > E > C > B 8 - B > E > D > A > C 3 - C > A > B > E > D 7 - C > A > E > B > D 2 - C > B > A > D > E 7 - D > C > E > B > A 8 - E > B > A > D > C

Przeprowadzamy konfrontacje w parach ( metoda Condorceta ), aby zbudować macierz pojedynków:

Macierz pojedynków kandydatów
d [*, A] d [*, B] d [*, C] d [*, d] z]
d [A, *] 20 26 30 22
d [B, *] 25 16 33 18
d [C, *] 19 29 17 24
d [D, *] 15 12 28 14
z,*] 23 27 21 31

Wykres pojedynków przedstawia się następująco:

Schulze0.svg

W takim głosowaniu nie ma zwycięzcy Condorcetu . Przechowywania przez zmniejszenie par prowadziłoby do wyboru A , natomiast czarne metoda wyboru E . Pokazana poniżej metoda Schulze doprowadziła również do wyboru E .

Heurystyka zbioru Schwartza

Heurystyka zbioru Schwartza to metoda wyznaczania zwycięzcy Schulza oparta na iteracji dwóch etapów: wyznaczenia zbioru potencjalnych zwycięzców (tzw. zbioru Schwartza), następnie wyeliminowania najbliższego pojedynku (dla którego luka głosowa jest najmniejszy)

Ta stosunkowo prosta heurystyka może reprezentować proces, w którym seria „  rewolucji  ” (sytuacja, w której większość narzuca swój wybór mniejszości) prowadzi do stabilnego lub przynajmniej możliwie najmniej niestabilnego wyboru .

Zestaw Schwartza

Dla danego wykresu pojedynków zbiór Schwartza formalnie definiuje się następująco:

Mniej formalnie, aby ustalić, czy kandydat należy do zbioru Schwartza, interesują nas kandydaci, którzy „pokonali go pośrednio” oraz kandydaci, których „pokonał pośrednio”. Mówimy, że X „pokonuje pośrednio” Y, jeśli spełniony jest jeden z następujących warunków:

Kandydat A należy wówczas do grupy wiodącej, jeżeli:

  1. Albo żaden kandydat nie pobije A  ;
  2. Czy jakikolwiek kandydat „pośrednio nietoperz” A jest również „pośrednio bity” przez A .

Na wykresie pojedynków wiodące grupy pojawiają się jako niepuste podzbiory wykresu, ku którym nie są skierowane żadne strzały. Zwróć uwagę, że grupa składająca się ze wszystkich kandydatów jest zawsze grupą wiodącą. Condorcet paradox odpowiada sytuacji, w której nie ma minimalna grupa głowa zredukowane do Singleton.

Algorytm

Wyborcy wypełniają swoje karty do głosowania, umieszczając różnych kandydatów w kolejności ich preferencji, jak w każdej metodzie Condorcet . Ustala się macierz pojedynków, a następnie graf pojedynków.

Algorytm składa się wtedy z:

  1. usunąć z grafu wierzchołki, które nie należą do jego zbioru Schwartza (łuki mające początek lub koniec usuniętego wierzchołka również są usuwane);
  2. jeśli uzyskany graf nie ma już żadnej krawędzi, to kandydaci odpowiadający wierzchołkom tego grafu są uznawani za równych zwycięzców (jest unikalny zwycięzca, jeśli pozostaje tylko jeden wierzchołek) i metoda zostaje zakończona;
  3. w przeciwnym razie usuń z wykresu krawędź(y), których waga jest minimalna, tj. krawędź(y) odpowiadające najkrótszej porażce, a następnie wróć do kroku 1.

Przykład

Bierzemy poprzedni przykład, w którym wykres pojedynków wygląda następująco:

Schulze1.svg

Jedyną wiodącą grupą jest cały zbiór kandydatów { A , B , C , D , E }. Rzeczywiście nie możemy znaleźć żadnego niepustego podzbioru, na który nie jest skierowana żadna strzała. Zbiór Schwartza to zatem również { A , B , C , D , E }. Algorytm jest kontynuowany.

Najbliższym zwycięstwem jest zwycięstwo E nad A (tylko jeden głos do przodu). Odpowiadający łuk, który ma najniższą wagę (1), jest usuwany. Zmodyfikowany wykres wygląda więc następująco:

Schulze2.svg

Wciąż jest tylko jedna wiodąca grupa, całość. Zbiór Schwartza ponownie składa się z całego zbioru { A , B , C , D , E }. Wyeliminowanie łuku nie wystarczyło do zmiany zestawu Schwartza.

Znowu likwiduje łuk do najniższego ważenia, który zaczyna się od C do E .

Schulze3.svg

Istnieją wtedy dwie grupy głów: ta składająca się ze wszystkich kandydatów { A , B , C , D , E } i singleton { E }. Tylko singleton { E } jest minimalny. Zbiór Schwartza jest wtedy singletonem { E }. Kandydat E jest zatem zwycięzcą wyborów.

Zauważ, że możemy następnie odtworzyć metodę z czterema niewybranymi kandydatami, aby uzyskać ranking wszystkich kandydatów. W tym przykładzie następujące przejście prowadzi do nowego paradoksu Condorceta , który prowadzi do wyeliminowania łuku B ⟶ A i zachowania A jako drugiego kandydata. Z drugiej strony istnieje paradoks Condorceta między kandydatami B , C i D . Eliminacja słabszej krawędzi D ⟶ C czyni C trzecim kandydatem , B czwartym, a D ostatnim. Ogólna klasyfikacja wynikająca z tego przykładu to E > A > C > B > D . W tym przypadku nie ma przypadku równości dwóch kandydatów, ale taka sytuacja może się zdarzyć.

Heurystyka zwycięskiej ścieżki

Heurystyka zwycięskiej ścieżki pozwala w inny sposób określić zwycięzcę Schulzego. Jednak wdrożenie jest bardziej złożone.

Ścieżka siły

Nazywamy ścieżkę siły z od kandydata X do kandydata Y , uporządkowaną listę kandydatów C (1), ..., C (n) spełniającą następujące warunki:

z jest siłą ścieżki.

Siła ścieżki

Siłę na ścieżce nazywamy najmniejszą wartością z różnych d [C (i), C (i + 1)] wzdłuż ścieżki. Siła ścieżki jest zatem równa sile jej najsłabszego ogniwa.

Przez p [A, B] oznaczamy siłę najsilniejszej ścieżki od kandydata A do kandydata B.

p [A, B]: = max {min {d [C (i), C (i + 1)] | i = 1, ..., (n-1)} | C (1), ..., C (n) to ścieżka z A do B}

Jeśli nie ma drogi z A do B, to

p [A, B]: = 0

Jeśli p [A, B]> p [B, A] mówimy, że kandydat A jest lepszy od kandydata B.

W metodzie Schulzego mówimy, że kandydat D jest potencjalnym zwycięzcą wtedy i tylko wtedy, gdy nie ma kandydata E, który byłby od niego lepszy .

Przykład 1

Bierzemy przykład przedstawiony powyżej. Konfrontacje parami ( metoda Condorcet ) prowadzą do następującej matrycy pojedynków:

Macierz pojedynków kandydatów
d [*, A] d [*, B] d [*, C] d [*, d] z]
d [A, *] 20 26 30 22
d [B, *] 25 16 33 18
d [C, *] 19 29 17 24
d [D, *] 15 12 28 14
z,*] 23 27 21 31

Wyznaczamy ścieżki o największej sile. Słabe ogniwo jest podkreślone

Najsilniejsze ścieżki
  ... do A ... być ... do C ... do D ... palec u nogi
od ... A- (30) -D- (28) -C- (29) -B A- (30) -D- (28) -C A- (30) -D A- (30) -D- (28) -C- (24) -E
od B ... B- (25) -A B- (33) -D- (28) -C B- (33) -D B- (33) -D- (28) -C- (24) -E
Gru ... C- (29) -B- (25) -A C- (29) -B C- (29) -B- (33) -D C- (24) -E
Z d ... D- (28) -C- (29) -B- (25) -A D- (28) -C- (29) -B D- (28) -C D- (28) -C- (24) -E
PA ... E- (31) -D- (28) -C- (29) -B- (25) -A E- (31) -D- (28) -C- (29) -B E- (31) -D- (28) -C E- (31) -D

Podsumowaniem wyników jest wtedy:

Największe atuty
  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 [W, *] 25 28 28 31  

Kandydat E jest potencjalnym zwycięzcą, ponieważ p [E, X] ≥ p [X, E] dla każdego innego kandydata X

Przykład 2

Przykład (9 głosujących; 4 kandydatów):

3 - A > B > C > D 2 - D > A > B > C 2 - D > B > C > A 2 - C > B > D > A

Konfrontacje przeprowadzamy w parach

Macierz pojedynków kandydatów
  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  

Wyznaczamy ścieżki o największej sile. Słabe ogniwo jest podkreślone .

Najsilniejsze ścieżki
... do A ... być ... do C ... do D
od ... A- (5) -B A- (5) -C A- (5) -B- (5) -D
od B ... B- (5) -D- (6) -A B- (7) -C B- (5) -D
Gru ... C- (5) -D- (6) -A C- (5) -D- (6) -A- (5) -B C- (5) -D
Z d ... D- (6) -A D- (6) -A- (5) -B D- (6) -A- (5) -C

Podsumowaniem wyników jest wtedy:

Największe atuty
  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  

Kandydaci B i D są potencjalnymi zwycięzcami, ponieważ p [B, X] ≥ p [X, B] dla każdego innego kandydata X oraz p [D, Y] ≥ p [Y, D] dla każdego innego kandydata Y

Kryteria spełnione i niespełnione

Spełnione kryteria

do przetłumaczenia przez specjalistów ds. kryteriów

Kryteria nie zostały spełnione

do przetłumaczenia przez specjalistów ds. kryteriów

Przyjęcia i zastosowania

Metoda Schulzego nie jest jeszcze stosowana w wyborach rządowych. Jednak był już używany w prawyborach w wyborach parlamentarnych przez Partię Piratów (Szwecja) . Ponadto niektóre organizacje od wielu lat przyjmują go na swoje potrzeby wyborcze. Niektóre organizacje stosujące metodę Schulze'a:

Jak również w wielu stowarzyszeniach anglojęzycznych.

Programy liczące

Uwagi i referencje

  1. Zobacz przykład niezgodności z zasadą Condorcet w artykule Natychmiastowe głosowanie w drugiej turze
  2. Rémi Peyre , „  Matematyka demokracji, II. A zwycięzcą drugiej rundy jest…: Kryterium Condorceta  ” , na temat obrazów matematyki , CNRS ,10 maja 2012(dostęp 19 kwietnia 2020 )
  3. Thomas Schwartz jest profesorem nauk politycznych na Uniwersytecie Kalifornijskim
  4. Proces wyborczy do Fundacji Gentoo
  5. Artykuł Gentoo / Condorcet
  6. Artykuł Gentoo / Condorcet / Schwartz
  7. Artykuł Gentoo / Schulze
  8. Patrz rozdział tego dokumentu 40.6 ( cale ) )
  9. Ergodis Association - francuskojęzyczna i ergonomiczna klawiatura bepo

Zobacz również

Powiązane artykuły