Metoda równych udziałów

Metoda równych udziałów (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, wyborów komitetów i głosowań bezpośrednich nad kilkoma niezależnymi kwestiami. 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

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.

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, oraz do przypadku budżetu partycypacyjnego.

Intuicyjne wyjaśnienie

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

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.

• 
  Mamy 9 zgłoszonych projektów. Przykładowo, trzecia grupa, złożona z 11 wyborców, zagłosowała na projekty D i G. Dostępny budżet $1000 jest dzielony po równo pomiędzy 100 wyborców. Każdy wyborca otrzymuje $10. Kliknięcie strzałki na powyższym obrazku pokaże kolejne kroki metody.
• 
  Projekt D otrzymał najwięcej głosów. Jeżeli podzielimy koszt D po równo pomiędzy wyborców, którzy zagłosowali na D, każdy wyborca zapłaci $3.03. Wybór D minimalizuje największą kwotę, którą wyborca musi zapłacić (w tym przypadku jest to wartość $3.03).
• 
  Projekt A otrzymał 60 głosów. Analogicznie do poprzedniego kroku: jeżeli podzielimy koszt A po równo pomiędzy wyborców, którzy zagłosowali na A, to każdy taki wyborca będzie musiał zapłacić $3.33. Wybór A minimalizuje największą kwotę, którą wyborca musi zapłacić, dlatego ten projekt zostaje wybrany.
• 
  Projekt C otrzymał 56 głosów i został wybrany w trzeciej rundzie. Każdy wyborca, który zagłosował na C musi zapłacić $3.64; jest to minimalna możliwa kwota (w przypadku wyboru każdego innego projektu, ta kwota musiałaby być większa). W tym momencie pierwszych 46 wyborców wydało już wszystkie pieniądze.
• 
  W czwartym kroku projekt G zostaje wybrany. Niektórzy z wyborców, którzy zagłosowali na G nie mają wystarczającej ilości pieniędzy, aby w równym stopniu uczestniczyć w zakupie G, dlatego Ci wyborcy płacą taką kwotę, którą dysponują. Największa płatność, którą któryś wyborca musi zapłącić za G to $6.97.
• 
  W ostatnim kroku projekt H zostaje wybrany. W tym kroku jedynie piąta grupa wyborców dysponuje środkami. Ci wyborcy mają sumarycznie wystarczającą ilość pieniędzy, aby sfinansować zakup projektu H. Największa płatność, którą któryś wyborca musi zapłacić to $10.

Dostępny budżet jest początkowo dzielony po równo pomiędzy wyborców, zatem każdy wyborca otrzymuje $10. Projekt $\mathrm {D}$ otrzymał najwięcej głosów, zatem zostaje wybrany w pierwszej rundzie. Jeżeli podzielimy koszt $\mathrm {D}$ po równo pomiędzy wyborców, którzy zagłosowali na $\mathrm {D} ,$ to każdy z wyborców będzie musiał zapłacić $\$200/66\approx \$3.03.$ Gdybyśmy wybrali inny projekt, np. $\mathrm {E} ,$ to koszt per wyborca wynosiłby $\$200/46\approx \$4.34.$ Metoda w pierwszej kolejności wybiera projekt, który minimalizuje cenę per wyborca.

W ostatnim kroku metoda wybrała projekt $\mathrm {H} ,$ mimo że inne projekty otrzymały więcej głosów (np. projekt $\mathrm {E}$). Dzieje się tak, ponieważ pieniądze przysługujące wyborcom, którzy głosowali na $\mathrm {E}$ zostały wydane na projekty $\mathrm {D} ,$ $\mathrm {A}$ i $\mathrm {C} .$ Z drugiej strony, wyborcy, którzy zagłosowali na $\mathrm {H}$ stanowią 20% wszystkich wyborców, zatem powinni mieć prawo do decydowania o 20% wszystkich dostępnych środków. Wyborcy Ci popierają jedynie projekt $\mathrm {H} ,$ zatem ten projekt zostaje wybrany.

Przykład 2 (poniżej) jest bardziej złożony i ilustruje głosowanie w skali.

Definicja

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 $P=\{p_{1},p_{2},\dots ,p_{m}\},$ oraz zbiór wyborców $N=\{1,2,\dots ,n\}.$ Dla każdego projektu $p\in P$ przez $\mathrm {cost} (p)$ oznaczamy jego koszt; niech $b$ oznacza wielkość dostępnego budżetu. Dla wyborcy $i\in N$ oraz projektu $p\in P$ niech $u_{i}(p)$ oznacza liczbę, którą wyborca $i$-ty przypisał projektowi $p{:}$ wyższa liczba oznacza silniejsze poparcie dla projektu. Innymi słowy, wartość $u_{i}(p)$ mierzy zadowolenie wyborcy $i$ w przypadku, gdy projekt $p$ zostałby wybrany.

Początkowo, każdemu wyborcy jest przypisywana równa część budżetu, $b_{i}=b/n.$ Metoda równych udziałów wybiera projekty w rundach, w każdej rundzie wybierając jeden projekt według następującego schematu:

1. Dla każdego projektu $p\in P,$ który nie został jeszcze wybrany metoda stara się podzielić koszt $\mathrm {cost} (p)$ 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 $p$ jest $\rho$-opłacalny, jeżeli: ${\begin{aligned}\sum _{i\in N}\min \left(b_{i},u_{i}(p)\cdot \rho \right)=\mathrm {cost} (p){\text{.}}\end{aligned}}$ Intuicyjnie, jeżeli projekt $p$ jest $\rho$-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 $\rho$ za jednostkę zadowolenia.
2. Jeżeli nie ma już niewybranych projektów, które byłyby $\rho$-opłacalne, metoda kończy działanie. Może się to zdarzyć wtedy, gdy dla każdego projektu $p,$ wyborcy, którzy oddali pozytywny głos na $p$ nie mają wystarczającej ilości pieniędzy: $\textstyle \sum _{i\in N\colon u_{i}(p)>0}b_{i}<\mathrm {cost} (p){\text{.}}$
3. Jeżeli istnieje $\rho$-opłacalny projekt, który nie został jeszcze wybrany, reguła wybiera ten projekt $p,$ który jest $\rho$-opłacalny dla najniższej wartości parametru $\rho$ (czyli projekt, dla którego cena per jednostka zadowolenia jest minimalna). Budżety wyborców są aktualizowane: dla każdego $i\in N$ ustawiamy $b_{i}:=\max(0,b_{i}-u_{i}(p)\cdot \rho ).$

Przykład 2

Poniższy diagram ilustruje działanie metody.

• 
  Mamy 8 zgłoszonych projektów i 250 wyborców. Przykładowo, pierwszych 65 wyborców przypisuje 30 punktów projektowi B i 10 punktów projektom E i G. Dostępny budżet to $2500. W pierwszym kroku budżet jest dzielony po równo pomiędzy wyborców, czyli każdy wyborca otrzymuje $10. Kliknij w strzałkę nad diagramem aby zobaczyć kolejne kroki metody.
• 
  Metoda w pierwszym kroku wybiera projekt B i dzieli jego koszt proporcjonalnie do wartości punktowych, które wyborcy przypisali do tego projektu. W tym przypadku oznacza to, że koszt jest dzielony po równo pomiędzy wyborców z pierwszej i drugiej grupy. Każdy taki wyborca płaci $2 i za tę kwotę uzyskuje 30 punktów zadowolenia. Zatem maksymalna cena za jednostkę zadowolenia wynosi $2/30\approx 0.066.$ Gdybyśmy wybrali inny projekt, to maksymalna cena za jednostkę zadowolenia byłaby wyższa.
• 
  Rozważmy projekt G i płatności zilustrowane na diagramie. Te płatności nie są równe dla wszystkich wyborców, jednak ciągle są proporcjonalne do wartości punktowych, które wyborcy przypisali projektowi G. Maksymalna cena za jednostkę zadowolenia dla projektu G wynosi $1/10=4/40=10/100=0.1$ i jest to wartość najmniejsza; w przypadku wybrania innego projektu cena za jednostkę zadowolenia musiałaby być wyższa. Projekt G zostaje wybrany. Po tej rundzie, wyborcy z czwartej grupy wydali już wszystkie dostępne środki.
• 
  W trzeciej rundzie metoda wybiera projekt F. Każdy wyborca, który zagłosował na F płaci tę samą cenę – wyjątek stanowią wyborcy z czwartej grupy, która nie mają już dostępnych środków (gdyby mieli, musieliby również zapłacić równą część kosztu projektu). Maksymalna cena za jednostkę zadowolenia dla projektu F jest najmniejsza spośród pozostałych projektów i wynosi 0.2.
• 
  W czwartym kroku projekt E zostaje wybrany. Rozważmy płatności przedstawione na diagramie. Zauważmy, że wyborcy z trzeciej grupy mają zbyt mało pieniędzy aby zapłacić cenę proporcjonalną do wartości punktowych przypisanych do projektu. Każdemu takiemu wyborcy pozostały $4. W tym przypadku, wyborcy Ci płacą taką kwotę, którą dysponują. Maksymalna cena za jednostkę zadowolenia (która jest płacona przez wyborców z pierwszej grupy) wynosi w przybliżeniu 0.54. Jest to wartość najmniejsza spośród tych, które odpowiadają nie wybranym jeszcze projektom, dlatego projekt E zostaje wybrany przez metodę.
• 
  W ostatnim kroku metoda wybiera projekt C. Wyborcy z drugiej i szóstej grupy mają zbyt mało pieniędzy aby zapłacić cenę proporcjonalną do wartości punktowych przypisanych do projektu, zatem płacą tyle na ile pozwalają dostępne środki. Maksymalna cena za jednostkę zadowolenia jest płacona przez wyborców z piątej grupy. Cena ta wynosi 0.7.
• 
  Reguła wybrała projekty o całkowitym koszcie $2380. Ponieważ, dostępny budżet wynosił $2500, mamy jeszcze $120 dostępnych środków. Mimo to, żaden projekt nie może zostać opłacony, ponieważ dla każdego projektu ilość dostępnych środków, które mają wyborcy głosujący na ten projekt jest niewystarczająca. Algorytm kończy działanie. Dostępne $120 możemy wydać na pozostałe projekty, stosując jedną z metod dopełniania. Przykładowo, metoda zachłanna wybrałaby projekt H, ponieważ jego koszt per zadowolenie wynosi $110/(2\cdot 50+1\cdot 10+1\cdot 55)$ i jest to wartość minimalna spośród tych projektów, które kosztują co najwyżej $120.

Dyskusja

Ta sekcja przedstawia dyskusję nad konkretnymi wariantami metody równych udziałów.

Typy głosów

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

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:

1. Możemy przyjąć, że $u_{i}(p)=\mathrm {cost} (p)$ jeżeli wyborca $i$ zagłosował na projekt $p,$ oraz $u_{i}(p)=0$ 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.
2. Możemy założyć, że $u_{i}(p)=1$ jeżeli wyborca $i$ zagłosował na projekt $p,$ oraz $u_{i}(p)=0$ 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

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 $u_{i}(p)$ zależy od pozycji, na której wyborca $i$ uszeregował projekt $p$ oraz, że $u_{i}(p)/u_{i}(p')\to \infty$ gdy wyborca $i$ woli projekt $p$ niż projekt $p'.$

Wybory komitetów

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 $b$ powinien być interpretowany jako liczba zwycięzców, których chcemy wyłonić.

Niewykorzystane środki

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:

1. Metoda zachłanna: wybieramy projekty $p$ w kolejności od największego do najmniejszego stosunku ${\frac {\sum _{i\in N}u_{i}(p)}{\mathrm {cost} (p)}}.$ Kończymy, gdy nie istnieje projekt, który może być sfinansowany w ramach dostępnych środków.
2. 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

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. Różnica pomiędzy tymi dwoma metodami jest następująca:

1. Metoda Równych Udziałów (MRU) jest obliczalna w czasie wielomianowym, natomiast obliczenie komitetu zwycięskiego względem PGA jest NP-trudne. Sekwencyjny wariant reguły PGA (ang. sequential proportional approval voting) jest obliczalny w czasie wielomianowym, jednak wariant ten nie spełnia aksjomatu uzasadnionej reprezentacji.
2. PGA jest optymalne w sensie Pareto, natomiast MRU nie jest.
3. 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.
4. 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.

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. Różnica pomiędzy tymi metodami jest następująca:

1. Obie metody są obliczalne w czasie wielomianowym i obie nie spełniają własności optymalności w sensie Pareto.
2. 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).
3. 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.

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. PGA dodatkowo rozszerza metodę D’Hondta do modelu budżetu partycypacyjnego.

Implementacja

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.

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