Proporcjonalna metoda głosowania przez aprobaty

Proporcjonalna metoda głosowania przez aprobaty (PGA, Szablon:Ang.) – 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ą Szablon:Link-interwiki, 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 Szablon:Link-interwiki. 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 $W$ sprawdzamy, na ilu kandydatów z $W$ zagłosował każdy z wyborców. Jeżeli dany wyborca zagłosował na $r$ kandydatów z $W,$ to przyjmujemy, że wyborca ten przypisuje $W$ liczbę punktów równą $r$-tej liczbie harmonicznej:

$\mathrm{H}(r)=1+\frac{1}{2}+\frac{1}{3}+\dots +\frac{1}{r}.$

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

Formalna definicja metody PGA jest następująca. Oznaczmy zbiór kandydatów przez $C=\{c_1,c_2,\dots ,c_m\},$ zbiór wyborców przez $N=\{1,2,\dots ,n\},$ a oczekiwany rozmiar komitetu przez $k.$ Niech $A_i$ oznacza zbiór kandydatów, na których zagłosował wyborca $i\in N.$ Wynik punktowy komitetu $W\subseteq C$ o rozmiarze $|W|=k$ jest zdefiniowany jako ${\mathrm{p}\mathrm{k}\mathrm{t}}_{\mathrm{P}\mathrm{A}\mathrm{V}}(W)={\sum }_{i=1}^n\mathrm{H}(|A_i\cap W|).$ PGA wybiera komitet $W,$ 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	$5\cdot (1+\frac{1}{2})=7,5$	$5\cdot 1=5$	$5\cdot 1=5$	$5\cdot 1=5$	$5\cdot 1=5$	$5\cdot 0=0$
Punkty przypisane przez 17 wyborców, głosujących na A i C	$17\cdot 1=17$	$17\cdot (1+\frac{1}{2})=25,5$	$17\cdot 1=17$	$17\cdot 1=17$	$17\cdot 0=0$	$17\cdot 1=17$
Punkty przypisane przez 8 wyborców, głosujących na D	$8\cdot 0=0$	$8\cdot 0=0$	$8\cdot 1=8$	$8\cdot 0=0$	$8\cdot 1=8$	$8\cdot 1=8$
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 $(k=10).$ 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

$60\cdot \mathrm{H}(6)+30\cdot \mathrm{H}(3)+1\cdot \mathrm{H}(1)=60\cdot (1+\frac{1}{2}+\dots +\frac{1}{6})+30\cdot (1+\frac{1}{2}+\frac{1}{3})+10\cdot 1=147+55+10=212.$

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

$60\cdot \mathrm{H}(10)+30\cdot \mathrm{H}(0)+1\cdot \mathrm{H}(0)=60\cdot (1+\frac{1}{2}+\dots +\frac{1}{10})\approx 175,73.$

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 $(k=1),$ PGA wybierze kandydata, który otrzymał najwięcej głosów. W tym przypadku reguła zachowuje się tak jak Szablon:Link-interwiki.

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 Szablon:Link-interwiki.

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 Szablon:Link-interwiki 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 Szablon:Link-interwiki, 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ę Szablon:Link-interwiki. 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 Szablon:Link-interwiki. 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,
• Szablon:Link-interwiki,
• 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),
• Szablon:Link-interwiki.

PGA nie posiada następujących własności:

• Szablon:Link-interwiki. 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. Szablon:Link-interwiki i Szablon:Link-interwiki. Te dwie alternatywne metody są ponadto obliczalne w czasie wielomianowym, jednak nie są efektywne w sensie Pareto, oraz nie spełniają Szablon:Link-interwiki ani Szablon:Link-interwiki.

Obliczanie zwycięskich komitetów

Program liniowy całkowitoliczbowy do obliczania metody PGA. Zmienna $y_c$ przyjmuje wartość 1, gdy kandydat $c$ zostaje wybrany. Zmienna $x_{i,\ell }$ przyjmuje wartość 1, gdy wyborca $i$ zagłosował na co najmniej $\ell$ 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 $m$ i $k$ oznaczają odpowiednio liczbę kandydatów i rozmiar komitetu):

$(\genfrac{}{}{0ex}{}{m}{k})=\frac{m!}{k!(m-k)!}.$

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 abcvoting.

Sekwencyjna metoda PGA (ang. Szablon:Link-interwiki) umożliwia obliczanie w przybliżeniu zwycięskich komitetów względem PGA. Wspólczynnik aproksymacji wynosi wtedy $1-1/e\approx 0,63,$ 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ć ${\mathrm{s}\mathrm{c}}_{\mathrm{P}\mathrm{A}\mathrm{V}}(W)$ chcemy zminimalizować $\sum _{i\in N}\mathrm{H}(k)-{\mathrm{s}\mathrm{c}}_{\mathrm{P}\mathrm{A}\mathrm{V}}(W)$). 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: Szablon:Cytuj
• Rozdział książki opisujący metody wybierania komitetów: Szablon:Cytuj
• Artykuł po polsku opisujący proporcjonalność metody PGA: Szablon:Cytuj

Powiązane pojęcia

• metoda D’Hondta
• metoda równych udziałów