Proporcjonalna metoda głosowania przez aprobaty (PGA, ) – proporcjonalny system wyboru komitetów (czyli grup reprezentantów) w drodze głosowania. PGA jest rozszerzeniem metody D’Hondta, które pozwala wyborcom głosować bezpośrednio na kandydatów, a nie na partie polityczne. Zgodnie z PGA wyborcy głosują za pomocą , czyli wskazują (dowolną liczbę) kandydatów, których akceptują.

Historia Metoda PGA została po raz pierwszy zaproponowana w 1895 roku przez duńskiego matematyka Thorvalda N. Thielego. Wariant tej metody był używany na początku XX wieku w Szwecji, między innymi w lokalnych wyborach, oraz w latach 1909–1921 do wyłaniania reprezentantów w obrębie partii politycznych. Po 1921 roku została zastąpiona . Metoda PGA została na nowo odkryta w 2001 roku przez Foresta Simmonsa, który jako pierwszy zaproponował angielską nazwę „proportional approval voting”.

Definicja PGA wybiera komitet (podzbiór kandydatów o ustalonej liczności) z najwyższym wynikiem punktowym, gdzie wynik punktowy jest obliczany w następujący sposób. Dla ustalonego komitetu sprawdzamy, na ilu kandydatów z zagłosował każdy z wyborców. Jeżeli dany wyborca zagłosował na kandydatów z to przyjmujemy, że wyborca ten przypisuje liczbę punktów równą -tej liczbie harmonicznej:

Wynik punktowy komitetu jest sumą punktów, które wyborcy przypisują komitetowi.

Formalna definicja metody PGA jest następująca. Oznaczmy zbiór kandydatów przez zbiór wyborców przez a oczekiwany rozmiar komitetu przez Niech oznacza zbiór kandydatów, na których zagłosował wyborca Wynik punktowy komitetu o rozmiarze jest zdefiniowany jako PGA wybiera komitet który otrzymał najwięcej punktów.

Przykład 1 Załóżmy, że chcemy wybrać dwóch spośród czterech kandydatów. Kandydaci to: Anna (A), Bartosz (B), Cezary (C) i Dorota (D). Mamy 30 wyborców, którzy oddali następujące głosy: 5 wyborców zagłosowało na A i B, 17 wyborców zagłosowało na A i C, 8 wyborców zagłosowało na D.

Mamy 6 możliwych wyników (dwuosobowych komitetów): AB, AC, AD, BC, BD oraz CD.

AB AC AD BC BD CD Punkty przypisane przez 5 wyborców, głosujących na A i B Punkty przypisane przez 17 wyborców, głosujących na A i C Punkty przypisane przez 8 wyborców, głosujących na D Wynik punktowy komitetu 24,5 30,5 30 22 13 25

Anna i Cezary zostają wybrani zgodnie z metodą PGA.

Przykład 2 Załóżmy, że chcemy wybrać dziesięcioosobowy komitet Kandydatów, którzy wystartowali w wyborach możemy podzielić na trzy grupy: czerwonych, niebieskich i zielonych. Mamy 100 wyborców, którzy oddali następujące głosy: 60 wyborców zagłosowało na wszystkich niebieskich kandydatów, 30 wyborców zagłosowało na wszystkich czerwonych kandydatów, 10 wyborców zagłosowało na wszystkich zielonych kandydatów.

W tym przypadku PGA wybierze 6 niebieskich, 3 czerwonych i 1 zielonego kandydata. Wynik punktowy takiego komitet wynosi

Pozostałe komitety będą miały niższe wyniki punktowe. Przykładowo, wynik punktowy komitetu, który składa się z samych niebieskich kandydatów wynosi

W tym przypadku PGA wybiera komitet, który proporcjonalnie reprezentuje wyborców: dla każdej z trzech grup liczba wybranych kandydatów jest proporcjonalna do liczby wyborców, którzy zagłosowali na kandydatów z tej grupy. Nie jest to przypadek: Jeżeli kandydatów możemy podzielić na grupy (tak jak w powyższym przykładzie; grupy mogą oznaczać partie polityczne) i jeżeli każdy wyborca zagłosuje na kandydatów z jednej wybranej grupy, to metoda PGA zadziała dokładnie tak samo jak metoda D’Hondta.

Własności Ta sekcja opisuje własności proporcjonalnej metody głosowania przez aprobaty (PGA).

Przypadek jednoosobowego komitetu Gdy celem jest wybór jednoosobowego komitetu PGA wybierze kandydata, który otrzymał najwięcej głosów. W tym przypadku reguła zachowuje się tak jak reguła aprobatowa.

Proporcjonalność Większość proporcjonalnych systemów wyborczych wymaga głosowania na partie polityczne. Metoda PGA została zaprojektowana, aby zapewnić proporcjonalność w przypadku, gdy wyborcy głosują na konkretnych kandydatów, a nie na partie. Metoda PGA jest nazywana proporcjonalną, ponieważ gdy głosy wyborców na kandydatów odpowiadają głosom na partie polityczne (tak jak w Przykładzie 2), metoda ta wybiera z każdej partii taką liczbę kandydatów, która jest proporcjonalna do liczby głosów oddanych na partię. Co więcej, przy pewnych naturalnych założeniach (symetria, ciągłość, efektywność w sensie Pareto), PGA jest jedyną metodą, która rozszerza metodę D’Hondta, pozwalając na głosowanie bezpośrednie na kandydatów i która spełnia .

PGA gwarantuje, że wybrany komitet proporcjonalnie reprezentuje wyborców, nawet jeżeli głosy wyborców nie mają „partyjnej” struktury, takiej jak w Przykładzie 2. Przykładowo, PGA spełnia silne własności oraz posiada optymalny współczynnik proporcjonalności. Własności te gwarantują, że każda grupa wyborców o spójnych preferencjach (głosująca na podobnych kandydatów) będzie reprezentowana przez taką liczbę kandydatów, która jest co najmniej proporcjonalna do wielkości tej grupy. PGA jest jedyną regułą wyborczą w klasie metod punktowych, która spełnia wyżej wymienione własności.

Komitety wybrane przez metodę PGA mogą nie należeć do , jednak spośród wszystkich znanych metod wyborczych PGA najlepiej przybliża własność rdzenia. PGA gwarantuje 2-aproksymację rdzenia, co jest najlepszym przybliżeniem, które może zostać osiągnięte przez regułę spełniającą zasadę . Ponadto, PGA spełnia własność rdzenia, jeżeli w wyborach uczestniczy wystarczająco wielu podobnych kandydatów.

Wyniki działania metody PGA nie zawsze mogą być przedstawione jako wyniki procesu, w którym wyborcy otrzymują pewną ustaloną ilość wirtualnych pieniędzy i używają tych pieniędzy, aby kupować kandydatów, na których głosują. PGA nie spełnia również własności laminarnej proporcjonalności. Dwie alternatywne reguły, które spełniają te własności i które mają podobnie dobre własności proporcjonalności to metoda równych udziałów i . Te dwie alternatywne metody są ponadto obliczalne w czasie wielomianowym, jednak nie są efektywne w sensie Pareto.

Pozostałe własności Poza własnościami, które dotyczą proporcjonalności, PGA spełnia następujące aksjomaty: Optymalność w sensie Pareto, , Monotoniczność względem poparcia (jeżeli poparcie jakiegoś zwycięskiego kandydata wzrośnie, czyli jeżeli taki kandydat otrzyma więcej głosów, wtedy kandydat ten musi po takim wzroście poparcia pozostać wybrany), .

PGA nie posiada następujących własności: . Dwie alternatywne metody, które posiadają podobnie dobre własności proporcjonalności co PGA i które są monotoniczne względem rozmiaru komitetu, to Sekwencyjny PGA – ang. i . Te dwie alternatywne metody są ponadto obliczalne w czasie wielomianowym, jednak nie są efektywne w sensie Pareto, oraz nie spełniają ani .

Obliczanie zwycięskich komitetów thumb|upright=1.8|Program liniowy całkowitoliczbowy do obliczania metody PGA. Zmienna przyjmuje wartość 1, gdy kandydat zostaje wybrany. Zmienna przyjmuje wartość 1, gdy wyborca zagłosował na co najmniej wybranych kandydatów. Obliczanie zwycięskich komitetów względem PGA jest NP-trudne. Jeżeli chcielibyśmy obliczyć wynik punktowy każdego komitetu, musielibyśmy rozważyć następującą liczbę kombinacji (niech i oznaczają odpowiednio liczbę kandydatów i rozmiar komitetu)Enric Plaza: „Technologies for political representation and accountability”: p9 .:

Przykładowo, jeżeli mamy 24 kandydatów, spośród których chcemy wyłonić czteroosobowy komitet, to musielibyśmy rozważyć 10.626 komitetów i dla każdego z tych komitetów obliczyć wynik punktowy. Obliczenie zwycięskiego komitetu wymagałoby w takim przypadku użycia komputera. Dla wyborów o średnim rozmiarze do obliczania zwycięskich komitetów możemy użyć narzędzi opartych na programowaniu liniowym całkowitoliczbowym. Taka metoda obliczania zwycięskich komitetów jest zaimplementowana w Pythonie jako część biblioteki abcvotingBiblioteka abcvoting zawiera implementację algorytmów do obliczania zwycięskich komitetów względem metody PGA..

Sekwencyjna metoda PGA (ang. ) umożliwia obliczanie w przybliżeniu zwycięskich komitetów względem PGA. Wspólczynnik aproksymacji wynosi wtedy co oznacza, że wynik punktowy komitetu wybranego przez sekwencyjną metodę PGA jest co najwyżej o 37% gorszy od wyniku punktowego optymalnego komitetu. Sekwencyjna metoda PGA jest obliczalna w czasie wielomianowym i do jej obliczania najczęściej nie potrzebujemy komputera. Metoda sekwencyjna sama w sobie posiada pewne pożądane własności i zapewnia dobre gwarancje proporcjonalności, jednak nie spełnia również wielu aksjomatów, które wyróżniają niesekwencyjny wariant PGA. Bardziej złożone algorytmy aproksymacyjne mogą dawać lepsze współczynniki aproksymacji. Przykładowo, metoda oparta na zaokrąglaniu programu liniowego daje współczynnik aproksymacji równy 0,7965. Przy standardowych założeniach teorii złożoności obliczeniowej jest to najlepszy współczynnik aproksymacji, który może zostać osiągnięty w czasie wielomianowym. Problem obliczania zwycięskich komitetów względem metody PGA możemy również sformułować jako problem minimalizacyjny (zamiast maksymalizować chcemy zminimalizować ). W tym przypadku najlepszy znany współczynnik aproksymacji wynosi 2,36.

Z punktu widzenia parametrycznej złożoności obliczeniowej, znajdowanie zwycięskich komitetów względem PGA jest (z pewnymi nielicznymi wyjątkami) trudne. Problem jest również NP-trudny, gdy preferencje wyborców odzwierciedlają ich pozycje w dwuwymiarowej przestrzeni poglądów ideologicznych. Problem jest obliczalny w czasie wielomianowym, gdy preferencje wyborców pochodzą z jednowymiarowej przestrzeni poglądów ideologicznych.

Pozostałe zastosowania PGA Metodę PGA można stosować również do bezpośredniego głosowania nad kilkoma niezależnymi uchwałami.

Powiązana literatura Książka opisująca metody wybierania komitetów, gdy wyborcy głosują przez aprobaty: Rozdział książki opisujący metody wybierania komitetów: Artykuł po polsku opisujący proporcjonalność metody PGA:

Powiązane pojęcia metoda D’Hondta metoda równych udziałów

Przypisy

Kategoria:Teoria systemów wyborczych