Metoda równych udziałów
Metoda równych udziałów[1][2][3][4] (w pierwszych artykułach metoda była również nazywana regułą X) – proporcjonalna metoda liczenia głosów i wyłaniania zwycięzców, która może być używana w przypadku budżetu partycypacyjnego[2], wyborów komitetów[1][4] i głosowań bezpośrednich nad kilkoma niezależnymi kwestiami[5][3]. Może być używana, gdy wyborcy głosują za pomocą aprobat (wskazując tych kandydatów, których akceptują), ustawiając kandydatów w ranking od najbardziej do najmniej lubianego, lub gdy głosują w skali przypisując kandydatom konkretne liczby punktów.
Motywacja
[edytuj | edytuj kod]Metoda równych udziałów jest alternatywą dla standardowej zachłannej metody używanej w głosowaniach nad budżetem partycypacyjnym. Zachłanna metoda, wybiera te projekty, które uzyskały największą liczbę głosów, dopóki dostępny budżet na to pozwala. Metoda zachłanna nie jest proporcjonalna, co pokazuje następujący przykład. Mamy 20 projektów, 10 niebieskich i 10 czerwonych. Możemy wybrać tylko 10 z nich; 51% wyborców głosuje na projekty niebieskie, a 49% na czerwone. W tym przypadku, reguła zachłanna wybrałaby 10 projektów niebieskich, a metoda równych udziałów wybrałaby 6 niebieskich i 4 czerwone, lub (w zależności od wariantu) 5 niebieskich i 5 czerwonych[6].
Metoda równych udziałów spełnia zasadę proporcjonalności: między innymi spełnia najsilniejszy znany wariant uzasadnionej reprezentacji , oraz jest rozszerzeniem metody D’Hondta do przypadku, gdy wyborcy głosują bezpośrednio na kandydatów, a nie na partie polityczne[1][7], oraz do przypadku budżetu partycypacyjnego[2].
Intuicyjne wyjaśnienie
[edytuj | edytuj kod]W przypadku budżetu partycypacyjnego metoda równych udziałów zakłada, że początkowo pieniądze z budżetu są rozdzielone równo pomiędzy wszystkich wyborców. Za każdym razem, gdy zostanie wybrany jakiś projekt, jego koszt jest dzielony po równo między wyborców, którzy na niego zagłosowali, a ich oszczędności są odpowiednio zmniejszane. Jeżeli wyborcy głosują za pomocą aprobat, to koszt projektu jest dzielony możliwie równo pomiędzy wyborców głosujących na projekt; jeżeli wyborcy głosują w skali, to koszt jest dzielony proporcjonalnie do punktów, które wyborcy przypisują danemu projektowi. Reguła wybiera po kolei projekty, które mogą być w ten sposób opłacone i u których stosunek liczby oddanych na nie głosów do ich kosztu jest jak największy.
Przykład 1
[edytuj | edytuj kod]Poniższy przykład ilustruje działanie reguły w przypadku, gdy wyborcy głosują przez aprobaty. W tym przykładzie mamy 100 wyborców i 9 zgłoszonych projektów, a dostępny budżet to $1000. Koszt każdego projektu to $200, zatem należy wybrać pięć spośród dziewięciu dostępnych projektów. Poniższy animowany diagram ilustruje kolejne kroki działania metody równych udziałów.
Dostępny budżet jest początkowo dzielony po równo pomiędzy wyborców, zatem każdy wyborca otrzymuje $10. Projekt otrzymał najwięcej głosów, zatem zostaje wybrany w pierwszej rundzie. Jeżeli podzielimy koszt po równo pomiędzy wyborców, którzy zagłosowali na to każdy z wyborców będzie musiał zapłacić Gdybyśmy wybrali inny projekt, np. to koszt per wyborca wynosiłby Metoda w pierwszej kolejności wybiera projekt, który minimalizuje cenę per wyborca.
W ostatnim kroku metoda wybrała projekt mimo że inne projekty otrzymały więcej głosów (np. projekt ). Dzieje się tak, ponieważ pieniądze przysługujące wyborcom, którzy głosowali na zostały wydane na projekty i Z drugiej strony, wyborcy, którzy zagłosowali na stanowią 20% wszystkich wyborców, zatem powinni mieć prawo do decydowania o 20% wszystkich dostępnych środków. Wyborcy Ci popierają jedynie projekt zatem ten projekt zostaje wybrany.
Przykład 2 (poniżej) jest bardziej złożony i ilustruje głosowanie w skali .
Definicja
[edytuj | edytuj kod]Ta sekcja opsuje definicję metody równych udziałów w przypadku gdy wyborcy głosują w skali przypisując kandydatom konkretne liczby punktów.
Rozważmy instancję, w której dostępny jest zbiór projektów oraz zbiór wyborców Dla każdego projektu przez oznaczamy jego koszt; niech oznacza wielkość dostępnego budżetu. Dla wyborcy oraz projektu niech oznacza liczbę, którą wyborca -ty przypisał projektowi wyższa liczba oznacza silniejsze poparcie dla projektu. Innymi słowy, wartość mierzy zadowolenie wyborcy w przypadku, gdy projekt zostałby wybrany.
Początkowo, każdemu wyborcy jest przypisywana równa część budżetu, Metoda równych udziałów wybiera projekty w rundach, w każdej rundzie wybierając jeden projekt według następującego schematu:
- Dla każdego projektu który nie został jeszcze wybrany metoda stara się podzielić koszt proporcjonalnie do wartości przypisanych przez wyborców. Bierzemy przy tym pod uwagę to, że niektórzy wyborcy nie mają wystarczającej ilości pieniędzy. Formalnie, powiemy, że projekt jest -opłacalny, jeżeli: Intuicyjnie, jeżeli projekt jest -opłacalny, to jego koszt może zostać podzielony pomiędzy wyborców w taki sposób, aby każdy wyborca zapłacił co najwyżej za jednostkę zadowolenia.
- Jeżeli nie ma już niewybranych projektów, które byłyby -opłacalne, metoda kończy działanie. Może się to zdarzyć wtedy, gdy dla każdego projektu wyborcy, którzy oddali pozytywny głos na nie mają wystarczającej ilości pieniędzy:
- Jeżeli istnieje -opłacalny projekt, który nie został jeszcze wybrany, reguła wybiera ten projekt który jest -opłacalny dla najniższej wartości parametru (czyli projekt, dla którego cena per jednostka zadowolenia jest minimalna). Budżety wyborców są aktualizowane: dla każdego ustawiamy
Przykład 2
[edytuj | edytuj kod]Poniższy diagram ilustruje działanie metody.
Dyskusja
[edytuj | edytuj kod]Ta sekcja przedstawia dyskusję nad konkretnymi wariantami metody równych udziałów.
Typy głosów
[edytuj | edytuj kod]Definicja metody zakłada, że wyborcy głosują w skali. Metoda ta może jednak być używana również gdy wyborcy głosują w inny sposób.
Głosowanie przez aprobaty
[edytuj | edytuj kod]Głosowanie przez aprobaty polega na tym, że każdy wyborca zaznacza te projekty, które uważa, że powinny zostać wybrane (często mówimy, że wyborca aprobuje te projekty lub, że na nie głosuje; przykład 1) ilustruje głosowanie przez aprobaty. Przy głosowaniu przez aprobaty możemy użyć metody równych udziałów w jeden z następujących sposobów:
- Możemy przyjąć, że jeżeli wyborca zagłosował na projekt oraz w przeciwnym przypadku. W ten sposób definiujemy zadowolenie wyborcy jako ilość pieniędzy przeznaczona na projekty, na które wyborca zagłosował. Założenie to jest powszechne w przypadku budżetu partycypacyjnego (m.in. zachłanna metoda używana przez większość miast działa w oparciu o to założenie) i zazwyczaj powoduje, że reguła wybiera projekty droższe, które mają duże Poparcie społeczne.
- Możemy założyć, że jeżeli wyborca zagłosował na projekt oraz w przeciwnym przypadku. Takie użycie metody zakłada, że definiujemy zadowolenie wyborcy jako liczbę wybranych projektów, na które wyborca zagłosował. To założenie powoduje, że reguła będzie wybierać więcej tanich projektów.
Głosowanie przez rankingi
[edytuj | edytuj kod]W przypadku głosowania przez rankingi wyborcy szeregują projekty od najbardziej do najmniej lubianego (czyli przedstawiając ich ranking). Zakładając preferencje leksykograficzne przyjmujemy, że zależy od pozycji, na której wyborca uszeregował projekt oraz, że gdy wyborca woli projekt niż projekt
Wybory komitetów
[edytuj | edytuj kod]W przypadku wyborów komitetów naszym celem jest wyłonienie ustalonej liczby zwycięzców spośród dostępnych kandydatów. W tym przypadku możemy użyć metody równych udziałów, zakładając, że koszt każdego kandydata wynosi 1. Wtedy budżet powinien być interpretowany jako liczba zwycięzców, których chcemy wyłonić.
Niewykorzystane środki
[edytuj | edytuj kod]Metoda równych udziałów może wybrać projekty, których sumaryczny koszt nie wykorzystuje całego dostępnego budżetu. Istnieje kilka możliwości aby zagospodarować niewykorzystaną część budżetu:
- Metoda zachłanna: wybieramy projekty w kolejności od największego do najmniejszego stosunku Kończymy, gdy nie istnieje projekt, który może być sfinansowany w ramach dostępnych środków.
- Skalowanie początkowego budżetu: początkowy budżet może zostać przeskalowany do największej takiej wartości, dla której całkowity koszt wybranych projektów nie przekroczy wartości budżetu przed przeskalowaniem (czyli rzeczywistej wielkości środków, które są dostępne).
Własności
[edytuj | edytuj kod]W kontekście wyborów komitetów Metoda Równych Udziałów (MRU) jest często porównywana do proporcjonalnego głosowania przez aprobaty (PGA) (ang. proportional approval voting, PAV). Obie metody spełniają aksjomat rozszerzonej uzasadnionej reprezentacji[8][2]. Różnica pomiędzy tymi dwoma metodami jest następująca:
- Metoda Równych Udziałów (MRU) jest obliczalna w czasie wielomianowym[1], natomiast obliczenie komitetu zwycięskiego względem PGA jest NP-trudne[9]. Sekwencyjny wariant reguły PGA (ang. sequential proportional approval voting ) jest obliczalny w czasie wielomianowym, jednak wariant ten nie spełnia aksjomatu uzasadnionej reprezentacji[8].
- PGA jest optymalne w sensie Pareto, natomiast MRU nie jest.
- MRU zwraca wyniki, które są w równowadze rynkowej. Wyniki zwracane przez MRU mogą być interpretowane jako równowaga Lindahla w modelu dyskretnym, przy założeniu, że konsumenci nabywający dobro publiczne muszą płacić tę samą kwotę za to dobro[2][10].
- MRU może być stosowane do wyboru projektów w ramach budżetu partycypacyjnego oraz w przypadku głosowania w skali. PGA nie spełnia własności uzasadnionej reprezentacji w modelu budżetu partycypacyjnego ani w przypadku głosowania w skali[1].
Metoda równych udziałów jest również podobna do sekwencyjnej metody Phragmena (ang. Phragmen’s sequential rule ). Różnica polega na tym, że w przypadku MRU wyborcy otrzymują pieniądze w pierwszym kroku reguły, podczas gdy w przypadku sekwencyjnej metody Phragmena zakładamy, że wyborcy zarabiają pieniądze sukcesywnie[11][12]. Różnica pomiędzy tymi metodami jest następująca:
- Obie metody są obliczalne w czasie wielomianowym i obie nie spełniają własności optymalności w sensie Pareto[4].
- MRU spełnia aksjomat Rozszerzonej Uzasadnionej Reprezentacji (ang. extended justified representation) natomiast sekwencyjna metoda Phragmena spełnia jedynie słabszy wariant tej własności, Proporcjonalną Uzasadnioną Reprezentację (ang. proportional justified representation)[1][11].
- Metoda Phragmena spełnia własności monotoniczności względem rozmiaru komitetu, natomiast MRU nie spełnia tej własności[4].
- MRU może być stosowana w przypadku budżetu partycypacyjnego oraz w przypadku głosowania w skali. Metoda Phragmena nie rozszerza się do tych modeli[1].
Wszystkie trzy metody, MRU, PGA i sekwencyjna metoda Phragmena, są rozszerzeniami metody D’Hondta, które pozwalają wyborcom głosować na konkretnych kandydatów bez afiliacji partyjnej[2][7]. PGA dodatkowo rozszerza metodę D’Hondta do modelu budżetu partycypacyjnego.
Implementacja
[edytuj | edytuj kod]Poniższy przykład zawiera implementację metody w języku Python dla przypadku gdy wyborcy głosują w skali. W przypadku wyborów komitetów metoda jest zaimplementowana w języku Python jako część pakietu abcvoting[13].
import math
def leq(a, b):
return a < b or math.isclose(a, b)
# N: lista wyborców.
# C: lista projektów (kandydatów).
# cost: słownik, który przypisuje każdemu projektowi jego koszt.
# b: dostępny budżet.
# u: słownik; u[c][i] jest wartością punktową, którą wyborca i przypisuje do projektu c.
# pusta wartość u[c][i] oznacza wartość punktową, równą 0.
def complete_utilitarian(N, C, cost, u, b, W):
util = {c: sum([u[c][i] for i in N]) for c in C}
committee_cost = sum([cost[c] for c in W])
while True:
next_candidate = None
highest_util = float("-inf")
for c in C.difference(W):
if leq(committee_cost + cost[c], b):
if util[c] / cost[c] > highest_util:
next_candidate = c
highest_util = util[c] / cost[c]
if next_candidate is None:
break
W.add(next_candidate)
committee_cost += cost[next_candidate]
return W
def method_of_equal_shares(N, C, cost, u, b):
W = set()
total_utility = {c: sum(u[c].values()) for c in C}
supporters = {c: set([i for i in N if u[c][i] > 0]) for c in C}
budget = {i: b / len(N) for i in N}
while True:
next_candidate = None
lowest_rho = float("inf")
for c in C.difference(W):
if leq(cost[c], sum([budget[i] for i in supporters[c]])):
supporters_sorted = sorted(supporters[c], key=lambda i: budget[i] / u[c][i])
price = cost[c]
util = total_utility[c]
for i in supporters_sorted:
if leq(price * u[c][i], budget[i] * util):
break
price -= budget[i]
util -= u[c][i]
rho = price / util \
if not math.isclose(util, 0) and not math.isclose(price, 0) \
else budget[supporters_sorted[-1]] / u[c][supporters_sorted[-1]]
if rho < lowest_rho:
next_candidate = c
lowest_rho = rho
if next_candidate is None:
break
W.add(next_candidate)
for i in N:
budget[i] -= min(budget[i], lowest_rho * u[next_candidate][i])
return complete_utilitarian(N, C, cost, u, b, W) # jedno z możliwych dopełnień.
Przypisy
[edytuj | edytuj kod]- ↑ a b c d e f g Dominik Peters , Piotr Skowron , Proportionality and the Limits of Welfarism, „Proceedings of the 21st ACM Conference on Economics and Computation”, 2020, s. 793–794, DOI: 10.1145/3391403.3399465, arXiv:1911.11747 (ang.).
- ↑ a b c d e f Dominik Peters , Grzegorz Pierczyński , Piotr Skowron , Proportional Participatory Budgeting with Additive Utilities, „Proceedings of the 2021 Conference on Neural Information Processing Systems”, 2020, arXiv:2008.13276 (ang.).
- ↑ a b Rupert Freeman , Anson Kahng , David Pennock , Proportionality in Approval-Based Elections With a Variable Number of Winners, „Proceedings of the 29th International Joint Conference on Artificial Intelligence”, 2020, s. 132–138, DOI: 10.24963/ijcai.2020/19 (ang.).
- ↑ a b c d Martin Lackner , Piotr Skowron , Multi-Winner Voting with Approval Preferences, „ArXiv”, 2020, arXiv:2007.01795 (ang.).
- ↑ Vincent Conitzer , Rupert Freeman , Nisarg Shah , Fair Public Decision Making, „Proceedings of the 18th ACM Conference on Economics and Computation”, 2017, s. 629–646, DOI: 10.1145/3033274.3085125, arXiv:1611.04034 (ang.).
- ↑ Till Fluschnik i inni, Fair Knapsack, „Proceedings of the AAAI Conference on Artificial Intelligence”, 2019, s. 1941–1948, DOI: 10.1609/aaai.v33i01.33011941 (ang.).
- ↑ a b Markus Brill , Jean-François Laslier , Piotr Skowron , Multiwinner Approval Rules as Apportionment Methods, „Journal of Theoretical Politics”, 2018, DOI: 10.1177/0951629818775518, arXiv:1611.08691 (ang.).
- ↑ a b Haris Aziz 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 (ang.).
- ↑ Haris Aziz i inni, Computational Aspects of Multi-Winner Approval Voting, „Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems”, 2015, s. 107–115, arXiv:1407.3247 (ang.).
- ↑ Dominik Peters i inni, Market-Based Explanations of Collective Decisions, „Proceedings of the 35th AAAI Conference on Artificial Intelligence”, s. 5656–5663, DOI: 10.1609/aaai.v35i6.16710 (ang.).
- ↑ a b Svante Janson , Phragmen’s and Thiele’s election methods, „ArXiv”, 2018, arXiv:1611.08826 (ang.).
- ↑ Markus Brill i inni, Phragmén’s Voting Methods and Justified Representation, „Proceedings of the AAAI Conference on Artificial Intelligence”, 2017, s. 2374–3468, DOI: 10.1609/aaai.v31i1.10598 (ang.).
- ↑ Martin Lackner , abcvoting, [w:] GitHub [online] (ang.).