Proporcjonalna metoda głosowania przez aprobaty

Proporcjonalna metoda głosowania przez aprobaty (PGA, ang. Proportional approval voting) – 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^[1][2]. Zgodnie z PGA wyborcy głosują za pomocą aprobat(inne języki), 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^[3][4][5]. 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(inne języki). Metoda PGA została na nowo odkryta w 2001 roku przez Foresta Simmonsa^[6], 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 ${\displaystyle W}$ sprawdzamy, na ilu kandydatów z ${\displaystyle W}$ zagłosował każdy z wyborców. Jeżeli dany wyborca zagłosował na ${\displaystyle r}$ kandydatów z ${\displaystyle W,}$ to przyjmujemy, że wyborca ten przypisuje ${\displaystyle W}$ liczbę punktów równą ${\displaystyle r}$-tej liczbie harmonicznej^[6][7]:

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

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

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

${\displaystyle 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

${\displaystyle 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^[1].

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 ${\displaystyle (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(inne języki).

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ę^[1]. 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(inne języki)^[2].

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(inne języki)^[7][8] oraz posiada optymalny współczynnik proporcjonalności^[9][10]. 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(inne języki)^[7][11], 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(inne języki)^[11]. Ponadto, PGA spełnia własność rdzenia, jeżeli w wyborach uczestniczy wystarczająco wielu podobnych kandydatów^[12].

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^[11]. 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(inne języki)^[13]. 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(inne języki),
• 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)^[14],
• Kryterium Pigou–Daltona(inne języki)^[11].

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

• Monotoniczność względem rozmiaru komitetu(inne języki)^[13]. 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(inne języki) i sekwencyjna metoda Phragmena(inne języki)^[13]. 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(inne języki) ani kryterium Pigou-Daltona(inne języki)^[13].

Obliczanie zwycięskich komitetów

Program liniowy całkowitoliczbowy do obliczania metody PGA. Zmienna ${\displaystyle y_{c}}$ przyjmuje wartość 1, gdy kandydat ${\displaystyle c}$ zostaje wybrany. Zmienna ${\displaystyle x_{i,\ell }}$ przyjmuje wartość 1, gdy wyborca ${\displaystyle i}$ zagłosował na co najmniej ${\displaystyle \ell }$ wybranych kandydatów^[13][15].

Obliczanie zwycięskich komitetów względem PGA jest NP-trudne^[16][17]. Jeżeli chcielibyśmy obliczyć wynik punktowy każdego komitetu, musielibyśmy rozważyć następującą liczbę kombinacji (niech ${\displaystyle m}$ i ${\displaystyle k}$ oznaczają odpowiednio liczbę kandydatów i rozmiar komitetu)^[18]:

${\displaystyle {\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^[19].

Sekwencyjna metoda PGA (ang. Sequential proportional approval voting(inne języki)) umożliwia obliczanie w przybliżeniu zwycięskich komitetów względem PGA. Wspólczynnik aproksymacji wynosi wtedy ${\displaystyle 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^[17]. 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^[20]. 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^[20]. Problem obliczania zwycięskich komitetów względem metody PGA możemy również sformułować jako problem minimalizacyjny (zamiast maksymalizować ${\displaystyle \textstyle \mathrm {sc} _{\mathrm {PAV} }(W)}$ chcemy zminimalizować ${\displaystyle \textstyle \sum _{i\in N}\mathrm {H} (k)-\mathrm {sc} _{\mathrm {PAV} }(W)}$). W tym przypadku najlepszy znany współczynnik aproksymacji wynosi 2,36^[21].

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

Pozostałe zastosowania PGA

Metodę PGA można stosować również do bezpośredniego głosowania nad kilkoma niezależnymi uchwałami^[24][25].

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 numerów stron w książce
• 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

Przypisy

1. MarkusM. Brill MarkusM., Jean-FrançoisJ.F. Laslier Jean-FrançoisJ.F., PiotrP. Skowron PiotrP., Multiwinner Approval Rules as Apportionment Methods, „Journal of Theoretical Politics”, 2018, DOI: 10.1177/0951629818775518, arXiv:1611.08691 .
2. MartinM. Lackner MartinM., PiotrP. Skowron PiotrP., Consistent approval-based multi-winner rules, „Journal of Economic Theory”, 192, 2021, DOI: 10.1016/j.jet.2020.105173, arXiv:1704.02453 .
3. Thorvald N.T.N. Thiele Thorvald N.T.N., Om Flerfoldsvalg, „Oversigt over Det Kongelige Danske Videnskabernes Selskabs Forhandlinger”, 1895, s. 415–441 .
4. SvanteS. Janson SvanteS., Phragmén’s and Thiele’s election methods, „ArXiv”, 2016, arXiv:1611.08826 .
5. RangeVoting.org - Optimal proportional representation [online], org/QualityMulti.html#acknow [dostęp 2024-04-25] .
6. Marc D.M.D. Kilgour Marc D.M.D., Approval Balloting for Multi-winner Elections, [w:] Jean-FrançoisJ.F. Laslier, M. RemziM.R. Sanver (red.), Handbook on Approval Voting, Springer, 2010, s. 105–124, ISBN 978-3-642-02839-7 .
7. HarisH. Aziz HarisH. i inni, Justified representation in approval-based committee voting, „Social Choice and Welfare”, 48 (2), 2017, s. 461–485, DOI: 10.1007/s00355-016-1019-3, arXiv:1407.8269 .
8. LuisL. Sánchez-Fernández LuisL. i inni, Proportional Justified Representation, „Proceedings of the AAAI Conference on Artificial Intelligence”, 2017, s. 670–676 .
9. HarisH. Aziz HarisH. i inni, On the Complexity of Extended and Proportional Justified Representation, „Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence”, 2018 (AAAI-18), s. 902–909 .???
10. PiotrP. Skowron PiotrP., Proportionality Degree of Multiwinner Rules, „Proceedings of the 22nd ACM Conference on Economics and Computation”, 2021 (EC-21), s. 820–840, DOI: 10.1145/3465456.3467641, arXiv:1810.08799 .???
11. DominikD. Peters DominikD., PiotrP. Skowron PiotrP., Proportionality and the Limits of Welfarism, „Proceedings of the 21st ACM Conference on Economics and Computation”, 2020 (EC'20), s. 793–794, DOI: 10.1145/3391403.3399465, arXiv:1911.11747 .???
12. MarkusM. Brill MarkusM. i inni, Approval-Based Apportionment, „Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence”, 2020 (AAAI-20), s. 1854–1861, DOI: 10.1609/aaai.v34i02.5553, arXiv:1911.08365 .???
13. MartinM. Lackner MartinM., PiotrP. Skowron PiotrP., Multi-Winner Voting with Approval Preferences, „ArXiv”, 2020, arXiv:2007.01795 .
14. Luis SánchezL.S. Fernández Luis SánchezL.S., JesúsJ. Fisteus JesúsJ., Monotonicity Axioms in Approval-based Multi-winner Voting Rules, „Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems”, 2019 (AAMAS-19), s. 485–493, arXiv:1710.04246 .???
15. DominikD. Peters DominikD., Single-Peakedness and Total Unimodularity: New Polynomial-Time Algorithms for Multi-Winner Elections, „Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence”, 2018 (AAAI-18), s. 1169–1176, arXiv:1609.03537 .???
16. HarisH. Aziz HarisH. i inni, Computational Aspects of Multi-Winner Approval Voting, „Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems”, 2015 (AAMAS-15), s. 107–115, ISBN 978-1-4503-3413-6, arXiv:1407.3247 .???
17. PiotrP. Skowron PiotrP., PiotrP. Faliszewski PiotrP., JérômeJ. Lang JérômeJ., Finding a collective set of items: From proportional multirepresentation to group recommendation, „Artificial Intelligence”, 241, 2016, s. 191–216, DOI: 10.1016/j.artint.2016.09.003, arXiv:1402.3044 .
18. Enric Plaza: „Technologies for political representation and accountability”: p9 [1].
19. Biblioteka abcvoting zawiera implementację algorytmów do obliczania zwycięskich komitetów względem metody PGA.
20. SzymonS. Dudycz SzymonS. i inni, Tight Approximation for Proportional Approval Voting, „Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence”, 2020 (IJCAI-20), s. 276–282, DOI: 10.24963/ijcai.2020/39 .???
21. JaroslawJ. Byrka JaroslawJ., PiotrP. Skowron PiotrP., KrzysztofK. Sornat KrzysztofK., Proportional Approval Voting, Harmonic k-median, and Negative Association, „Proceedings of the 45th International Colloquium on Automata, Languages, and Programming”, 2018 (ICALP-18), 26:1–26:14, DOI: 10.4230/LIPIcs.ICALP.2018.26, arXiv:1704.02183 .???
22. RobertR. Bredereck RobertR. i inni, Parameterized Algorithms for Finding a Collective Set of Items, „Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence”, 2020 (AAAI-20), s. 1838–1845, DOI: 10.1609/aaai.v34i02.5551 .???
23. MichalM. Godziszewski MichalM. i inni, An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections, „Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence”, 2021 (AAAI-21), s. 5448–5455 .???
24. VincentV. Conitzer VincentV., RupertR. Freeman RupertR., NisargN. Shah NisargN., Fair Public Decision Making, „Proceedings of the 18th ACM Conference on Economics and Computation”, 2017 (EC'17), s. 629–646, DOI: 10.1145/3033274.3085125, arXiv:1611.04034 .???
25. RupertR. Freeman RupertR., AnsonA. Kahng AnsonA., DavidD. Pennock DavidD., Proportionality in Approval-Based Elections With a Variable Number of Winners, „Proceedings of the 29th International Joint Conference on Artificial Intelligence”, 2020 (IJCAI'20), s. 132–138, DOI: 10.24963/ijcai.2020/19 .???