Algorytm budżetu partycypacyjnego

budżetu partycypacyjnego (PB) to algorytm wdrażania budżetu partycypacyjnego .

Dane wejściowe do algorytmu PB to: lista możliwych projektów , które wymagają finansowania, całkowity dostępny budżet na finansowanie projektów oraz preferencje wyborców co do projektu. Wynikiem działania algorytmu PB jest podział budżetu między projekty — określający, ile pieniędzy należy przeznaczyć na każdy projekt.

Algorytm PB może traktować projekty jako podzielne lub niepodzielne :

Podzielny algorytm PB może przeznaczyć dowolną kwotę pieniędzy na dowolny projekt, o ile suma alokacji jest równa budżetowi. Nadaje się do projektów, w których każdy dodatkowy dolar może być efektywnie wykorzystany, takich jak darowizny na cele charytatywne.
Niepodzielny algorytm PB przyjmuje jako dodatkowe dane wejściowe koszty projektów. Zwraca podzbiór projektów, tak aby całkowity koszt wybranych projektów nie przekraczał budżetu. Każdemu wybranemu projektowi przydzielany jest cały koszt, podczas gdy każdemu niewybranemu projektowi nie przydziela się nic. Lepiej nadaje się do projektów, które muszą być całkowicie finansowane, aby mogły działać, takich jak budowa nowych budynków.

Formaty wejściowe

Ważną kwestią przy projektowaniu algorytmu PB jest to, jakiego formatu wejściowego użyć do uzyskania preferencji - w jaki sposób każdy głosujący powinien wyrazić swoje preferencje dotyczące projektów. Kilka formatów wejściowych stosowanych w praktyce to:

Głosowanie zatwierdzające : każdy głosujący określa podzbiór projektów, które „zatwierdza” (uważa za wartościowe), podczas gdy inne są uważane za niezatwierdzone. Przypomina to binarny system punktacji, w którym każdy głosujący może ocenić każdy projekt jako 1 lub 0.
Głosowanie k-zatwierdzające : każdy głosujący określa podzbiór swoich k najlepszych projektów – k projektów, które uważa za najbardziej wartościowe.
Progowe głosowanie zatwierdzające : biorąc pod uwagę wartość progową t , każdy głosujący określa podzbiór wszystkich projektów, które ocenia jako co najmniej t .
Głosowanie rankingowe : każdy głosujący określa całą relację preferencji w stosunku do projektów, określając projekt, który uważa za najcenniejszy, drugi pod względem wartości itp.

Te formaty wejściowe są problematyczne dla niepodzielnego PB, ponieważ ignorują różne koszty projektów. Niektóre nowsze formaty danych wejściowych, które uwzględniają koszty, to:

Głosowanie plecakowe : każdy głosujący określa podzbiór projektów, tak aby całkowity koszt projektów w podzbiorze był co najwyżej budżetem (niezależnie od tego, ile projektów znajduje się w podzbiorze). Zatem każdy wyborca musi rozwiązać indywidualny problem plecakowy - znaleźć podzbiór, który maksymalizuje jego osobistą użyteczność przy ograniczeniu budżetowym. Zaletą głosowania plecakowego jest to, że jeśli algorytm ocenia każdy projekt na podstawie liczby otrzymanych głosów i wybiera projekty chciwie w malejącej kolejności punktacji, aż do zapełnienia budżetu, wówczas głosowanie plecakowe jest mechanizmem częściowo zgodnym z prawdą .
Ranking wartości do ceny : każdy głosujący klasyfikuje projekty nie według ich całkowitej wartości, ale według stosunku wartości do kosztów.

Różne formaty danych wejściowych można porównywać w oparciu o niejawne głosowanie utylitarne — o ile każdy format danych wejściowych jest użyteczny w maksymalizacji sumy użyteczności. Z tej perspektywy głosowanie progowe jest lepsze od głosowania plecakowego, rankingu według wartości i rankingu według wartości do ceny: minimalizuje zniekształcenie maksymalnej sumy użyteczności zarówno teoretycznie, jak i empirycznie.

Po otrzymaniu danych wejściowych od obywateli system powinien obliczyć budżet. Istnieją różne kryteria oceny budżetu.

Budżet plecakowy

Najbardziej powszechną w praktyce metodą budżetowania jest zachłanne rozwiązanie wariantu problemu plecakowego : projekty są sortowane według malejącej liczby otrzymanych głosów i wybierane jeden po drugim, aż do zapełnienia budżetu. Alternatywnie, jeśli liczba projektów jest wystarczająco mała, problem plecakowy można rozwiązać dokładnie, wybierając podzbiór projektów, który maksymalizuje całkowite szczęście obywateli. Wadą tej metody jest często nazywana indywidualnie najlepszym budżetowaniem plecakowym , jest to, że może to być niesprawiedliwe wobec mniejszości: jeśli 51% populacji popiera 10 projektów, a 49% wspiera 10 innych projektów, a pieniędzy starczy tylko na 10 projektów, to budżet plecakowy wybierze 10 projektów wspieranych przez 51%, i całkowicie zignoruj 49%.

Dwie alternatywy dla indywidualnie najlepszego plecaka to:

Zróżnicowany plecak – maksymalizacja liczby obywateli, którzy mają co najmniej jedną preferowaną pozycję w budżecie (podobnie jak reguła Chamberlina-Couranta dla głosowania na wielu zwycięzców ).
Plecak optymalny Nasha - maksymalizacja iloczynu użyteczności obywateli.

Niestety, w przypadku dziedzin użyteczności ogólnej obie te reguły są NP-trudne do obliczenia. Jednak zróżnicowany plecak można rozwiązać wielomianowo w określonych domenach preferencji lub gdy liczba wyborców jest niewielka.

Budżet większościowy

Jednym z takich kryteriów jest kryterium Condorceta : według większości wyborców wybrany budżet powinien być co najmniej tak dobry, jak każdy inny proponowany budżet (żadna proponowana zmiana nie ma poparcia większości głosów). Istnieje algorytm czasu wielomianowego do znajdowania takiego budżetu. Algorytm wykorzystuje zbiory Schwartza .

Budżetowanie proporcjonalne

Inny zestaw kryteriów dotyczy reprezentacji proporcjonalnej . Kryteria te uogólniają uzasadnionej reprezentacji z głosowania na wielu zwycięzców. Idea tych kryteriów polega na tym, że jeśli istnieje wystarczająco duża grupa wyborców, którzy wszyscy zgadzają się na konkretny projekt, to projekt ten powinien otrzymać odpowiednio dużą część budżetu.

Poniższe wyrażenia formalizują tę intuicję dla przypadku niepodzielnego PB i głosowania zatwierdzającego, tj.:

Istnieje m dyskretnych projektów; każdy projekt j wymaga kosztu c _j .
jest n ; każdy wyborca ma zestaw projektów, które uważa za pożądane.
Celem jest podjęcie decyzji o podzbiorze projektów do sfinansowania, których łączny koszt nie przekracza L .

Poniżej L oznacza limit budżetu.

Silna uzasadniona reprezentacja budżetowa (BJR) oznacza, że dla każdej grupy wyborców o wielkości co najmniej n / L , jeśli wszyscy popierają co najmniej jeden projekt, to co najmniej jeden projekt, którego wszyscy chcą, jest finansowany.
Silna proporcjonalna-uzasadniona-reprezentacja budżetowa (BPJR) oznacza, że dla każdej liczby całkowitej k i każdej grupy wyborców o wielkości co najmniej kn / L , jeśli projekty wspierane przez wszystkich kosztują co najmniej k , to projekty wspierane przez wszystkich z nich powinno otrzymać dofinansowanie w wysokości co najmniej tys .

Niestety, silne budżety BJR mogą nie istnieć (i oczywiście to samo dotyczy silnego BPJR, ponieważ BJR jest szczególnym przypadkiem BPJR dla k = 1). Załóżmy na przykład, że istnieją dwa projekty o koszcie 2, limit budżetowy wynosi 3 i jest dwóch głosujących, z których każdy pragnie jednego projektu. Wtedy każdy wyborca jest grupą o wielkości 1 > 2/3, więc BJR wymaga, aby projekt każdego wyborcy był finansowany, ale suma kosztów obu projektów wynosi 4 > 3. Dlatego zaproponowano słabsze warianty tych kryteriów:

Słaby BJR oznacza, że dla każdej grupy wyborców o wielkości co najmniej n / L , jeśli wszyscy poprą przynajmniej jeden projekt o koszcie 1 (koszt minimalny) , to co najmniej jeden projekt, którego wszyscy chcą, zostanie sfinansowany.
Słaby BPJR oznacza, że dla każdej liczby całkowitej k i każdej grupy wyborców o wielkości co najmniej kn / L , jeżeli projekty wspierane przez nich wszystkich kosztują co najmniej k , to finansowanie projektów wspieranych przez nich wszystkich powinno wynosić co najmniej maksymalny koszt podzbioru projektu z kosztem co najwyżej k obsługiwanym przez wszystkie z nich.

Na szczęście słabe budżety BPJR (a co za tym idzie słabe budżety BJR) zawsze istnieją i można je znaleźć za pomocą algorytmu superwielomianowego. Znalezienie słabego budżetu BPJR jest NP-trudne, ale znalezienie słabego budżetu BJR można wykonać za pomocą wielomianowego algorytmu zachłannego .

Inne kryterium, słaby lokalny BPJR , jest słabsze niż słabe BPJR, ale silniejsze niż słabe BJR; można go znaleźć za pomocą algorytmu czasu wielomianowego opartego na regule sekwencyjnej Phragmena .

Każde z tych kryteriów ma słabszy wariant, w którym zamiast zewnętrznego limitu budżetowego L mianownikiem jest W , czyli rzeczywista kwota przeznaczona na finansowanie. Ponieważ zwykle W < L , warianty W są łatwiejsze do spełnienia niż ich warianty L.

Kolejnym silnym kryterium proporcjonalności jest rozszerzone uzasadnione oświadczenie (EJR). Każda reguła spełniająca EJR jest NP-trudna do obliczenia, ale istnieje reguła obliczalna w czasie wielomianowym, Metoda równych udziałów , która spełnia nieznaczne złagodzenie aksjomatu EJR-do-jednego-projektu.

Podstawowe budżetowanie

W przypadku podzielnego PB i głosowania użyteczności przekonująca metoda budżetowania to taka, która opiera się na rdzeniu podstawowej gry. Budżet jest uważany za „w rdzeniu”, jeśli żaden podzbiór k wyborców nie może wziąć swojej części budżetu ( k L / n ) i sfinansować podzbiór projektów w taki sposób, że użyteczność każdego wyborcy w podzbiorze ściśle wzrasta. Istnieją wydajne algorytmy obliczania budżetu rdzenia dla niektórych naturalnych klas funkcji użyteczności.

Koordynacja darczyńców

Problem koordynacji darczyńców to wariant podzielnego PB , w którym budżet jest przekazywany przez samych wyborców (a nie ustalany z góry). Algorytm koordynacji może poprawić efektywność dystrybucji środków. Załóżmy na przykład, że rozważane są trzy projekty: teatr, klub szachowy i boisko do koszykówki. Jest dwóch darczyńców: Alicja i Bob, z których każdy chce przekazać 3000. Alicja woli zajęcia w pomieszczeniach (teatr lub szachy), podczas gdy Bob woli zajęcia konkurencyjne (szachy lub koszykówka).

Jeśli nie koordynują, to naturalnie Alicja wpłaca 1500 na każdą aktywność w pomieszczeniu, podczas gdy Bob wpłaca 1500 na każdą rywalizację. Wynikowa dystrybucja to 1500, 3000, 1500. Każdy darczyńca odczuwa szczęście w wysokości 4500 z darowizn na preferowane przez siebie projekty.
W przeciwieństwie do tego, jeśli koordynują, mogą wnieść wszystko do klubu szachowego, więc dystrybucja wynosi 0, 6000, 0. Teraz każdy darczyńca odczuwa szczęście 6000, więc ta dystrybucja Pareto dominuje nad poprzednią.

Ponieważ darowizny są dobrowolne, ważne jest, aby algorytm koordynacji gwarantował, że każdy wyborca odniesie niewielkie korzyści z udziału w algorytmie, tj. kwota wkładu w projekty, które zatwierdza, jest nieznacznie wyższa, gdy uczestniczy, niż gdy nie bierze udziału. Wymóg ten może być nie do pogodzenia z efektywną alokacją budżetu, gdy użyteczności wyborców są ogólnymi funkcjami liniowymi.

Jest to jednak osiągalne, gdy użyteczności wyborców są liniowe i binarne , tj. w modelu głosowania aprobującego :

Jest m organizacji charytatywnych; każda organizacja charytatywna może skorzystać z dowolnej włożonej w nią kwoty.
Jest n dawców; każdy darczyńca ma zestaw organizacji charytatywnych, na których mu zależy. Każdy darczyńca i jest skłonny przekazać łączną kwotę C _i .
Celem jest podjęcie decyzji o podziale sumy środków zebranych od wszystkich darczyńców (suma C _i ) pomiędzy m organizacje charytatywne. Użyteczność każdego agenta z danej dystrybucji to suma pieniędzy przeznaczona na jego/jej ukochane organizacje charytatywne.

W tym ustawieniu przeanalizowano kilka reguł. Są one zilustrowane poniżej dla ustawienia z 4 organizacjami charytatywnymi (a, b, c, d) i 5 darczyńcami, którzy przekazują po 1, i których ulubionymi zestawami są ac, ad, bc, bd, a.

Nieskoordynowana reguła po prostu dzieli wkład każdego agenta i między organizacje charytatywne lubiane przez i . Zatem dystrybucja finansowania wynosi 2,1,1,1, a użyteczności pięciu agentów to 3,3,2,2,2. Mechanizm ten jest wykonalny i indywidualnie racjonalny, ale nieefektywny: wynik jest zdominowany na przykład przez rozkład 3,2,0,0, gdzie użyteczności wynoszą 3,3,2,2,3.
Reguła optymalna Nasha znajduje alokację budżetu maksymalizującą iloczyn użyteczności. Jest optymalny w sensie Pareto , wykonalny i indywidualnie racjonalny. Jednak nie jest odporny na strategie ani monotoniczny pod względem zasobów .
Reguła ograniczonego utylitaryzmu znajduje alokację budżetu maksymalizującą sumę użyteczności ze zbioru wszystkich możliwych do wdrożenia reguł. Jest wykonalny, indywidualnie racjonalny, odporny na strategię i monotoniczny pod względem zasobów. Nie jest to jednak optymalne w sensie Pareto.
Nie ma reguły PB, która spełniałaby wszystkie pięć właściwości, nawet przy preferencjach binarnych.

Zobacz też

Głosowanie wielu zwycięzców - może być postrzegane jako szczególny przypadek budżetu partycypacyjnego, w którym „koszt” każdego kandydata wynosi 1, a budżet jest wielkości parlamentu.