Proporcjonalna metoda głosowania przez aprobaty

Proporcjonalna metoda głosowania przez aprobaty (PGA) (ang. Proportional Approval Voting (PAV)) – 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ą aprobat, 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 metodą Phragména. 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}}+\ldots +{\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 $\textstyle \mathrm {pkt} _{\mathrm {PAV} }(W)=\sum _{i=1}^{n}\mathrm {H} {\big (}|A_{i}\cap W|{\big )}.$ 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 \left(1+{\tfrac {1}{2}}\right)=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 \left(1+{\tfrac {1}{2}}\right)=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 \left(1+{\tfrac {1}{2}}+\ldots +{\tfrac {1}{6}}\right)+30\cdot \left(1+{\tfrac {1}{2}}+{\tfrac {1}{3}}\right)+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 \left(1+{\tfrac {1}{2}}+\ldots +{\tfrac {1}{10}}\right)\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 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 kryterium spójności.

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 uzasadnionej reprezentacji 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 rdzenia, 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ę Pigou–Daltona. 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 sekwencyjna metoda Phragmena. 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,
• Kryterium spójności,
• 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),
• Kryterium Pigou–Daltona.

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

• Monotoniczność względem rozmiaru komitetu. 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. Sequential proportional Approval Voting i sekwencyjna metoda Phragmena. Te dwie alternatywne metody są ponadto obliczalne w czasie wielomianowym, jednak nie są efektywne w sensie Pareto, oraz nie spełniają kryterium spójności ani kryterium Pigou-Daltona.

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):

${\binom {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. Sequential proportional approval voting) 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ć $\textstyle \mathrm {sc} _{\mathrm {PAV} }(W)$ chcemy zminimalizować $\textstyle \sum _{i\in N}\mathrm {H} (k)-\mathrm {sc} _{\mathrm {PAV} }(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: MartinM. Lackner MartinM., PiotrP. Skowron PiotrP., Multi-Winner Voting with Approval Preferences, „ArXiv”, 2020, arXiv:2007.01795 .
• Rozdział książki opisujący metody wybierania komitetów: PiotrP. Faliszewski PiotrP. i inni, Multiwinner Voting: A New Challenge for Social Choice Theory, [w:] UlleU. Endriss (red.), Trends in Computational Social Choice, AI Access, 26 października 2017, ISBN 978-1-326-91209-3 .brak strony (książka)
• Artykuł po polsku opisujący proporcjonalność metody PGA: PiotrP. Skowron PiotrP., Proporcjonalność bez partii politycznych, „Delta”, 2020 .

Powiązane pojęcia

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