Részvételi költségvetési algoritmus - Participatory budgeting algorithm

A részvételi költségvetés (PB) algoritmus a részvételi költségvetés megvalósításának algoritmusa .

A PB algoritmus bemenetei a következők: a lehetséges finanszírozást igénylő projektek listája, a projektek finanszírozására rendelkezésre álló teljes költségvetés , valamint a szavazók preferenciái a projekttel szemben. A PB algoritmus kimenete a költségvetés felosztása a projektek között - meghatározza, hogy mennyi pénzt kell elkülöníteni az egyes projektekhez.

A PB algoritmus oszthatónak vagy oszthatatlannak tudja kezelni a projekteket :

Egy osztható PB -algoritmus tetszőleges összeget allokálhat bármely projekthez, amennyiben az allokációk összege megegyezik a költségvetéssel. Alkalmas olyan projektekhez, amelyekben minden további dollár hatékonyan felhasználható, például jótékonysági adományok.
Egy oszthatatlan PB algoritmus további inputként veszi a projektek költségeit. Visszaadja a projektek egy részhalmazát, így a kiválasztott projektek összköltsége nem haladja meg a költségvetést. Minden kiválasztott projekthez hozzárendelik a teljes költséget, míg minden nem kiválasztott projekthez semmit. Jobban alkalmas olyan projektekre, amelyeket teljes mértékben finanszírozni kell a működéshez, például új épületek építéséhez.

Beviteli formátumok

A PB algoritmus tervezésekor fontos szempont, hogy milyen bemeneti formátumot kell használni a preferenciakibocsátáshoz - hogyan kell minden szavazónak kifejeznie preferenciáit a projektekkel szemben. A gyakorlatban számos beviteli formátumot használnak:

Jóváhagyó szavazás : minden szavazó meghatározza az általuk jóváhagyott (értékesnek tekintett) projektek egy részhalmazát, míg a többi nem jóváhagyott. Ez olyan, mint egy bináris pontozási rendszer, amelyben minden szavazó minden projektet 1 -re vagy 0 -ra értékelhet.
k -jóváhagyó szavazás : minden szavazó meghatározza legjobb k projektjeinek egy részhalmazát - azokat a k projekteket, amelyeket a legértékesebbnek tart.
Küszöbérték-jóváhagyási szavazás : adott t küszöbérték mellett minden szavazó meghatározza az összes olyan projekt részhalmazát, amelyet legalább t-nek értékelnek .
Rangsorolt szavazás : minden szavazó megad egy teljes preferencia-viszonyt a projektekkel szemben, megadva azt a projektet, amelyet a legértékesebbnek, a 2. legértékesebbnek, stb.

Ezek a bemeneti formátumok problémákat okoznak az oszthatatlan PB számára, mivel figyelmen kívül hagyják a projektek különböző költségeit. Néhány újabb beviteli formátum, amelyek figyelembe veszik a költségeket, a következők:

Hátizsákos szavazás : minden szavazó meghatározza a projektek egy részhalmazát úgy, hogy az alcsoportba tartozó projektek összköltsége legfeljebb a költségvetés legyen (függetlenül attól, hogy hány projekt van az alcsoportban). Így minden választópolgárnak meg kell oldania egy egyéni hátizsák problémát - meg kell találnia azt az alhalmazt, amely a költségvetési korlátok mellett maximalizálja személyes hasznosságát. A hátizsákos szavazás előnye, hogy ha az algoritmus minden projektet a kapott szavazatok számával pontoz, és a projekteket mohón választja a pontszám csökkenő sorrendjében, amíg a költségvetés be nem telik, akkor a hátizsákos szavazás részben igaz mechanizmus .
Ár-érték arányú rangsor : minden szavazó a projekteket rangsorolja, nem a teljes értékük, hanem az érték/költség arányuk szerint.

A különböző bemeneti formátumok összehasonlíthatók az implicit haszonelvű szavazás alapján - az egyes bemeneti formátumok mennyire hasznosak a közművek összegének maximalizálásában. Ebből a szempontból a küszöb-jóváhagyási szavazás felülmúlja a hátizsákos szavazást, az érték szerinti rangsorolást és az ár-érték arány szerinti rangsorolást: elméletileg és empirikusan minimalizálja a maximális hasznossági összegből eredő torzulást.

Miután a rendszer megkapta a polgárok hozzájárulását, költségvetést kell kiszámítania. A költségvetés különböző kritériumok alapján értékelhető.

Hátizsákos költségvetés

A gyakorlatban leggyakrabban előforduló költségvetési módszer a hátizsák-probléma egyik változatának mohó megoldása : a projekteket a kapott szavazatok csökkenő sorrendjében sorolják fel, és egyenként választják ki, amíg a költségvetés megtelik. Alternatív megoldásként, ha a projektek száma kellően kicsi, a hátizsák problémát pontosan meg lehet oldani, ha kiválasztunk egy olyan projektrészletet, amely maximalizálja a polgárok teljes boldogságát. Ennek a módszernek, amelyet gyakran egyénileg legjobb hátizsák-költségvetésnek neveznek, az a hátránya, hogy igazságtalan lehet a kisebbségekkel szemben: ha a lakosság 51% -a 10 projektet támogat, 49% -a pedig 10 másik projektet, és a pénz csak 10 projektre elegendő, akkor A hátizsákos költségvetés az 51% által támogatott 10 projektet választja, és a 49% -ot teljesen figyelmen kívül hagyja.

Az egyénileg legjobb hátizsák két alternatívája:

Változatos hátizsák - maximalizálja azon polgárok számát, akik rendelkeznek legalább egy előnyben részesített ténnyel a költségvetésben (hasonlóan a többnyelvű szavazásra vonatkozó Chamberlin -Courant szabályhoz ).
Nash -optimális hátizsák - a polgárok közüzemi termékeinek maximalizálása.

Sajnos az általános segédprogramok esetében mindkét szabály NP-nehezen kiszámítható. A változatos hátizsák azonban polinomiálisan megoldható bizonyos preferencia területeken, vagy ha a szavazók száma kicsi.

Többségi költségvetés

Az egyik ilyen kritérium a Condorcet -kritérium : a választott költségvetésnek legalább olyan jónak kell lennie, mint bármely más javasolt költségvetésnek a szavazók többsége szerint (egyetlen módosítási javaslatot sem támogat a szavazatok többsége). Létezik egy polinomiális idejű algoritmus egy ilyen költségvetés megtalálására. Az algoritmus Schwartz halmazokat használ .

Arányos költségvetés

Egy másik kritériumrendszer az arányos képviselethez kapcsolódik . Ezek a kritériumok általánosítják a több nyertes szavazásból származó indokolt képviseleti kritériumokat . Ezeknek a kritériumoknak az az elképzelése, hogy ha kellően nagy számú választópolgár van, akik valamennyien egyetértenek egy adott projektben, akkor ez a projekt a költségvetés kellően nagy részét kapja meg.

Az alábbi kifejezések formálják ezt az intuíciót az oszthatatlan PB és jóváhagyó szavazás esetében, azaz:

Vannak m diszkrét projektek; minden j projektnek költsége van c _j .
Vannak n szavazók; minden szavazónak van egy projektje, amelyet kívánatosnak tart.
A cél az, hogy döntsön a részhalmaza projektek alapot, a teljes költség legfeljebb L .

Az alábbiakban L jelöli a költségvetési limitet.

Az erős költségvetési indokolt képviselet (BJR) azt jelenti, hogy minden, legalább n / L méretű szavazócsoport esetében , ha mindegyik támogat legalább egy projektet, akkor legalább egy projektet finanszíroznak.
Az erős költségvetés-arányos-indokolt képviselet (BPJR) azt jelenti, hogy minden k egész szám és minden kn / L méretű szavazócsoport esetében , ha az általuk támogatott projektek legalább k-ba kerülnek , akkor az összes támogatott projekt közülük legalább k támogatást kell kapniuk .

Sajnos előfordulhat, hogy nem léteznek erős BJR -költségvetések (és nyilvánvalóan ugyanez vonatkozik az erős BPJR -re is, mivel a BJR a BPJR speciális esete k = 1 esetén). Tegyük fel például, hogy két projekt költsége 2, a költségvetési korlát 3, és két szavazó van, akik mindegyik egyetlen projektre vágyik. Ekkor minden szavazó 1> 2/3 méretű csoport, így a BJR megköveteli, hogy minden szavazó projektjét finanszírozzák, de mindkét projekt költségeinek összege 4> 3. Ezért ezeknek a kritériumoknak a gyengébb változatait javasolták:

A gyenge BJR azt jelenti, hogy minden, legalább n / L méretű választói csoport esetében , ha mindegyik támogatja legalább az egyik költséget (a minimális költséget) , akkor legalább egy projektet finanszíroznak.
A gyenge BPJR azt jelenti, hogy minden k egész számra és minden kn / L méretű szavazócsoportra vonatkozóan , ha az általuk támogatott projektek költsége legalább k , akkor az általuk támogatott projektek finanszírozásának legalább egy projekt-részhalmaz maximális költsége, amelynek költsége legfeljebb k , mindannyian támogatják.

Szerencsére a gyenge BPJR költségvetések (és így a gyenge BJR költségvetések) mindig léteznek, és megtalálhatók egy szuperpolinomiális algoritmussal. A gyenge BPJR költségvetés megtalálása NP-nehéz, de a gyenge BJR költségvetés megtalálható polinomiális mohó algoritmussal .

Egy másik kritérium, a Gyenge helyi BPJR gyengébb, mint a gyenge BPJR, de erősebb, mint a gyenge BJR; a Phragmen- féle szekvenciális szabályon alapuló polinom-idő algoritmus segítségével megtalálható .

E kritériumok mindegyikének van egy gyengébb változata, ahol az L külső költségvetési korlát helyett a nevező a W , ami a finanszírozásra használt tényleges összeg. Mivel általában W < L , a W -variánsokat könnyebb kielégíteni, mint az L -változatukat.

Core költségvetés

Arra az esetre osztható PB és közüzemi szavazás, egy kényszerítő költségvetési eljárás egyik alapja a mag a mögöttes játék. A költségvetés "magban" tekintendő, ha a k szavazók egyetlen alcsoportja sem tudja kivenni a részét a költségvetésből ( k L / n ) és finanszírozni tudja a projektek egy részhalmazát úgy, hogy az egyes részszavazók hasznossága szigorúan megnő. Vannak hatékony algoritmusok az alapvető költségvetés kiszámításához a segédprogram egyes természetes osztályaihoz.

A donorok koordinációja

Az adományozói koordinációs probléma az osztható PB egyik változata, amelyben a költségvetést maguk a választók adományozzák (nem pedig előre rögzítik). Egy koordinációs algoritmus javíthatja a pénzeszközök elosztásának hatékonyságát. Tegyük fel például, hogy három projektet vesznek figyelembe: színház, sakk klub és kosárlabda pálya. Két adományozó van: Alice és Bob, mindegyik 3000 -en kíván hozzájárulni. Alice a beltéri tevékenységeket részesíti előnyben (színház vagy sakk), míg Bob a versenyképes tevékenységeket (sakk vagy kosárlabda).

Ha nem koordinálnak, akkor természetesen Alice minden beltéri tevékenységhez 1500, míg Bob minden versenytevékenységhez 1500 -at ad. Az így kapott eloszlás 1500, 3000, 1500. Minden adományozó 4500 boldogságot érez az adományoktól a kívánt projektjeiig.
Ezzel szemben, ha koordinálnak, mindent hozzá tudnak adni a sakk klubhoz, így az elosztás 0, 6000, 0 lesz. Most minden donor 6000-es boldogságot érez, tehát ez az elosztás Pareto uralja az előzőt.

Mivel az adományozás önkéntes, fontos, hogy a koordinációs algoritmus biztosítsa, hogy minden szavazó gyengén profitáljon az algoritmusban való részvételből, azaz az általa jóváhagyott projektekhez hozzájáruló összeg gyengén magasabb, amikor részt vesz, mint amikor nem. Ez a követelmény összeegyeztethetetlen a hatékony költségvetési elosztással, ha a választók közművei általános lineáris függvények.

Ez azonban akkor érhető el, ha a választók segédprogramjai lineárisak és binárisak , azaz a jóváhagyási szavazási modellben:

Vannak m jótékonysági szervezetek; minden jótékonysági szervezet bármilyen összegű pénzből részesülhet.
Vannak n donorok; minden adományozónak van egy sor jótékonysági szervezete, amivel törődik. Minden i donor hajlandó adományozni összesen C _i összeget .
A cél az, hogy az összes adományozótól összegyűjtött összes pénzeszköz (a C _i összege ) az m jótékonysági szervezetek közötti elosztásáról döntsenek . Az egyes ügynökök hasznossága egy adott forgalmazásból a szeretett jótékonysági szervezeteinek juttatott pénzösszeg.

Ebben a helyzetben több szabályt elemeztek. Az alábbiakban példákat mutatunk be egy olyan környezetben, ahol 4 jótékonysági szervezet (a, b, c, d) és 5 donor járul hozzá, akik egyenként 1 -et adnak, és akiknek szeretett készletei az ac, ad, bc, bd, a.

A koordinálatlan szabály csak megosztja a hozzájárulását az egyes szer i között jótékonysági tetszett i . Tehát a finanszírozás elosztása 2,1,1,1, az öt ügynök közüzemi díja 3,3,2,2,2. Ez a mechanizmus megvalósítható és egyénileg racionális, de nem hatékony: az eredményt uralja például a 3,2,0,0 eloszlás, ahol a közművek 3,3,2,2,3.
A Nash-optimális szabály olyan költségkeret-allokációt talál, amely maximalizálja a közművek termékét . Ez Pareto optimális , megvalósítható és egyénileg racionális. Ez azonban nem stratégiabiztos és nem erőforrás-monoton .
A kényszer-haszonelvű szabály olyan költségvetési allokációt talál, amely maximalizálja a közművek összegét az összes végrehajtható szabályból. Ez megvalósítható, egyénileg racionális, stratégiabiztos és erőforrás-monoton. Ez azonban nem Pareto-optimális.
Nincs olyan PB -szabály, amely kielégíti mind az öt tulajdonságot, még bináris preferenciák mellett is.

Lásd még

Többnyertes szavazás - a részvételi költségvetés különleges esetének tekinthető, amelyben minden jelölt "költsége" 1, a költségvetés pedig a parlament mérete.

Languages

In other projects