Matematyczne gwarancje sprawiedliwości

W skrócie: W literaturze naukowej wykazano, że przy użyciu metody równych udziałów każda grupa wyborców o spójnych preferencjach ma proporcjonalny wpływ na wynik wyborów.

Metoda równych udziałów została zaprojektowana przez naukowców. Okazuje się, że można precyzyjnie wykazać, że metoda ta jest proporcjonalna i że sprawiedliwie traktuje wszystkie grupy wyborców. Poniżej opisujemy niektóre z tych teoretycznych wyników. Opisujemy je zarówno na poziomie intuicyjnym, jak i w bardziej precyzyjny matematyczny sposób.

Więcej informacji można znaleźć również w następujących źródłach:

• Książka "Multi-Winner Voting with Approval Preferences", 2023, Martin Lackner i Piotr Skowron, opublikowana w otwartym dostępie przez Springera (darmowy PDF). Książka ta koncentruje się głównie na „wyborach komitetów”, czyli na szczególnym przypadku budżetu obywatelskiego, gdzie wszystkie projekty mają ten sam koszt.
• Artykuł "Proportional Participatory Budgeting with Additive Utilities", 2021, opublikowany na konferencji Annual Conference on Neural Information Processing Systems 2021 (NeurIPS 2021), Dominik Peters, Grzegorz Pierczyński, Piotr Skowron. Pełna wersja artykułu dostępna w serwisie arXiv.

Projekt na pewno zostanie sfinansowany, jeśli liczba pojedynczych głosów oddanych na ten projekt będzie proporcjonalna do jego kosztu

Pierwszy wynik, który omówimy dotyczy gwarancji, że projekt zostanie sfinsnsowany, jeśli uzyska co najmniej pewną minimalną liczbę unikalnych głosów.

Przykładowo, rozważmy projekt o koszcie wynoszącym 5% dostępnych środków. Jeśli co najmniej 5% wyborców zagłosuje na ten projekt i na żaden inny projekt, wówczas projekt ten na pewno zostanie wybrany przez metodę równych udziałów.

Oto formalny opis tej własności:

Twierdzenie. Rozważmy projekt $P$ o koszcie $\text{koszt}(P)$. Przez $B$ oznaczmy całkowitą kwotę dostępną w ramach budżetu obywatelskiego. Niech $n$ oznacza liczbę głosujących. Jeśli co najmniej $n \cdot \text{koszt}(P)/B$ wyborców zagłosowało na $P$ i jeżeli żaden z tych wyborców nie zagłosował na żaden inny projekt, to $P$ zostanie wybrany przez metodę równych udziałów.

Dowód

Każdy z wyborców, który zagłosował jedynie na $P$, dostaje na początku kwotę równą co najmniej $B/n$. (Może to być więcej niż $B/n$, ponieważ uzupełniamy wynik jeśli nie wykorzystuje on w pełni dostępnego budżetu).

Zatem łączna kwota przypisana wyborcom głosującym tylko na $P$ wynosi co najmniej

$$\underbrace{n \cdot \frac{\text{koszt}(P)}{B}}_{\text{liczba wyborców}} \cdot \underbrace{\frac{B}{n}}_{\text{początkowy budżet każdego z nich}} = \text{koszt}(P).$$

Metoda równych udziałów kończy działanie dopiero wtedy, gdy zwolennicy każdego niewybranego jeszcze projektu nie mają już wystarczających środków, aby pokryć koszt tego projektu. To oznacza, że $P$ musi zostać wybrany, ponieważ wyborcy, którzy głosują tylko na $P$, zachowują wszystkie swoje początkowe środki i mogą je wydać jedynie na $P$, czyli Ci wyborcy będą zawsze w stanie pokryć koszt $P$.

Przy zastosowaniu standardowej metody głosowania w budżecie obywatelskim (która wybiera najpopularniejsze projekty do wyczerpania budżetu), nie mamy takich gwarancji. Nawet bardzo opłacalny projekt (na przykład taki, który kosztuje jedynie 1% budżetu i otrzymał aż 30% unikalnych głosów) może zostać pominięty.

Grupa wyborców, którzy głosują podobnie, będzie miała proporcjonalny udział w rozdysponowanym budżecie

Każda grupa wyborców, która głosuje na podobne projekty będzie miała udział w budżecie, który jest proporcjonalny do wielkości tej grupy. Przykładowo, grupa 20% głosujących będzie decydować o 20% środków.

Takie grupy mogą stanowić na przykład rodzice dzieci uczęszczających do konkretnej szkoły, mieszkańcy konkretnej dzielnicy, lub osoby dojeżdżające do pracy na rowerze. Jeżeli tacy wyborcy będą głosować podobnie (np. na projekty dotyczące szkoły, na projekty z konkretnej dzielnicy, lub na projekty rowerowe), to będą oni w stanie zagwarantować wybór projektów o koszcie odpowidajacym liczbie takich wyborców.

Grupy wyborców, którzy głosują identycznie

Rozważmy wybory, w których każdy wyborca wskazuje dowolny zbiór projektów, które popiera. Załóżmy, że $t$ z $n$ wyborców zagłosowało na ten sam zestaw projektów. Powiedzmy, że tych $t$ wyborców zagłosowało na projekty $P_1$, $P_2$ i $P_3$. Intuicyjnie, ponieważ ta grupa stanowi $t/n$ wyborców, powinna być w stanie zdecydować o $t/n$ budżetu. Załóżmy, że:

$$\text{koszt}(P_1) + \text{koszt}(P_2) + \text{koszt}(P_3) \leqslant \frac{t}{n} \cdot B,$$

gdzie $B$ oznacza wielkość dostępnego budżetu. Innymi słowy, grupa ta „zasługuje”, aby projekty na które zagłosowała zostały sfinansowane. W tym przypadku można udowodnić, że metoda równych udziałów wybierze wszystkie trzy projekty.

Tę własność możemy formalnie zapisać w następujący sposób:

Twierdzenie. Rozważmy zbiór projektów $\{P_1, P_2, \ldots, P_k\}$ i załóżmy, że $t$ spośród $n$ wyborców zagłosowało dokładnie na te projekty (i na żadne inne). Przypuśćmy, że całkowity koszt tych projektów wynosi co najwyżej $t/n \cdot B$. Wtedy każdy z tych $k$ projektów zostanie wybrany przez metodę równych udziałów.

Przypadek, gdy całkowity koszt projektów popieranych przez grupę wyborców jest wyższy

Możemy wykazać podobną własność również wtedy, gdy grupa głosujących popiera zbiór projektów o łącznej kwocie przekraczającej $t/n \cdot B$. Załóżmy, że $t$ wyborców głosuje dokładnie na projekty $P_1$, $P_2$, $P_3$ i $P_4$. Załóżmy ponadto, że

$$\text{koszt}(P_1) + \text{koszt}(P_2) + \text{koszt}(P_3) + \text{koszt}(P_4) > \frac{t}{n} \cdot B.$$

W takim przypadku metoda równych udziałów wybierze tylko kilka z tych projektów tak, aby koszt tych wybranych był „w przybliżeniu” równy $t/n \cdot B$.

Twierdzenie. Rozważmy zbiór projektów $T =\{P_1, P_2, \ldots, P_k\}$ i załóżmy, że $t$ spośród $n$ wyborców zagłosowało dokładnie na te projekty (i na żadne inne). Metoda równych udziałów wybierze podzbiór projektów $T' \subseteq T$ taki, że dla każdego niewybranego projektu $P^* \in T$ zachodzić będzie $\sum_{P \in T'} \text{koszt}(P) + \text{koszt}(P^*) > t/n \cdot B$.

Grupy wyborców, którzy głosują podobnie

Powyżej rozważyliśmy przypadek, w którym grupa wyborców głosuje na dokładnie ten sam zestaw projektów. W praktyce jednak rzadko się zdarza aby wyborcy byli aż tak zgodni. Dlatego istotne jest, aby zapewnić, że metoda liczenia głosów wybierze również takie projekty, które są popierane przez wyborców głosujących podobnie, choć niekoniecznie identycznie. Metoda równych udziałów posiada tę pożądaną cechę.

Matematyczny opis własności

Rozważmy wybory, w których każdy wyborca wskazuje dowolny zbiór projektów, które popiera. Niech $A_i$ oznacza zbiór projektów popieranych przez $i$-tego wyborcę. Dla zbioru projektów $T = \{P_1, P_2, \ldots, P_k\}$ przez $\text{koszt}(T)$ oznaczmy całkowity koszt projektów z $T$, czyli $\text{koszt}(T) = \text{koszt}(P_1) + \text{koszt}(P_2) + \ldots + \text{koszt}(P_k)$. Rozważmy grupę $t$ wyborców. Załóżmy, że każdy taki wyborca (nazwijmy go $i$) zagłosował na wszystkie projekty ze zbioru $T$ (czyli $T \subseteq A_i$). Część wyborców mogła do tego zagłosować również na inne projekty spoza zbioru $T$. Przyjmijmy, że $\text{koszt}(T)\leqslant t/n \cdot B$ (zatem ta grupa wyborców posiada dostatecznie dużo środków, aby „pozwolić sobie” na zakup projektów z $T$). W takim wypadku możemy zagwarantować, że wśród tych $t$ głosujących istnieje taki wyborca $i$ dla którego ilość śródków przeznaczonych na projekty, które popiera jest proporcjonalnie duża:

$$\text{koszt}(A_i \cap W) \geqslant \text{koszt}(T) - \text{koszt}(P_j) \qquad \text{dla pewnego $P_j \in T$}.$$

W powyższym wzorze $W$ oznacza zbiór projektów wybranych przez metodę równych udziałów. Co za tym idzie, $A_i \cap W$ oznacza zbiór wybranych projektów na które zagłosował $i$-ty wyborca.

Własność ta w literaturze naukowej nazywana jest „rozszerzoną uzasadnioną reprezentacją”. Więcej szczegółów na ten temat można znaleźć w pracy autorstwa Petersa, Pierczyńskiego i Skowrona (2021).

Inne podstawowe własności

Metody liczenia głosów możemy również oceniać względem innych kryteriów, które nie zawsze odnoszą się bezpośrednio do proporcjonalności. Następujące właśności są spełnione przez metodę równych udziałów:

• Obliczalność w czasie wielomianowym: Metodę równych udziałów możemy obliczać w czasie wielomianowym używając stosunkowo prostego algorytmu. Dzięki temu możemy szybko obliczać zwycięskie projekty, nawet dla dużych miast. Czas trwania takich obliczeń wynosi zwykle poniżej minuty.
• Odporność na klonowanie: Przez „klonowanie” rozumiemy zgłoszenie jednej lub kilku kopii uprzednio zgłoszonego projektu. Zakładamy, że każdy wyborca albo głosuje na wszystkie klony, albo na żaden z nich. Metoda równych udziałów ma następującą własność: jeśli przegrywający projekt jest sklonowany, żaden z klonów nie zostaje wybrany; jeśli zwycięski projekt jest sklonowany, wtedy ten projekt lub przynajmniej jeden z klonów zostaje wybrany.
• Monotoniczność: Jeśli jakiś wyborca odda dodatkowy głos na jakiś zwycięski projekt, to po takiej zmianie, projekt ten nadal będzie wybrany.
• Monotoniczność ze względu na cenę: Jeśli koszt zwycięskiego projektu zostanie zmniejszony, to po takiej zmianie, projekt ten nadal pozostanie zwycięski. Jeśli koszt przegranego projektu zostanie zwiększony, to projekt ten pozostanie niewybrany.
• Odporność na puste głosy: Jeśli do wyborów dodamy wyborcę, który nie zagłosował na żaden z projektów, to wynik wyborów się nie zmienia (zakładając, standardowy wariant dopełniania metody [więcej na ten temat]).
• Jest rozszerzeniem metody D'Hondta: Metoda równych udziałów (z wykorzystaniem standardowego dopełniania [więcej na ten temat]) jest uogólnieniem metody D'Hondta. Metoda D'Hondta jest proporcjonalną metodą podziału miejsc w parlamencie, która jest stosowana w wielu krajach. Z każdej instancji wyborów parlamentarnych możemy skonstruować instancję budżetu obywatelskiego w następujący sposób: utożsamiamy kandydatów startujących w wyborach parlamentarnych z projektami, zakładamy że koszt każdego takiego projektu/kandydata wynosi 1, że budżet jest równy liczbie miejsc w parlamencie i że każdy wyborca głosuje na wszystkich członków tej partii, którą popiera. Okazuje się, że jeśli zastosujemy metodę równych udziałów do tak skonstruowanej instancji budżetu obywatelskiego, to wynik jej działania będzie równoważny wynikowi działania metody D'Hondta dla oryginalnej instancji wyborów parlamentarnych.

Metoda równych udziałów nie spełnia następujących własności:

• Optymalność w sensie Pareto
• Monotoniczność względem wielkości budżetu (zwycięski projekt może nie zostać wybrany, jeśli zwiększymy ilość dostępnych środków w budżecie)
• Odporność na strategiczne głosowanie (wyborca nie powinien mieć możliwości uzyskania lepszego wyniku wyborów poprzez głosownie niezgodne ze swoimi prawdziwymi preferencjami). Należy jednak nadmienić, że żaden system liczenia głosów, w tym metoda większościowa, nie jest odporny na strategiczne głosowanie (jest to jeden z fundamentalnych wyników w teorii wyboru społecznego). Stosowanie metody równych udziałów, ma jednak pozytywny wpływ na strategiczne głosowanie: zapewnia, że grupa wyborców, która umówi się co do głosowania, będzie miała ograniczony (bo proporcjonalny) wpływ na wynik wyborów. W przypadku metody większościowej nawet mała grupa skoordynowanych wyborców może zdecydować o całym budżecie.