Deltagande budgeteringsalgoritm - Participatory budgeting algorithm

En algoritm för deltagande budgetering (PB) är en algoritm för att genomföra deltagande budgetering .

Ingångarna till en PB -algoritm är: en lista över möjliga projekt som kräver finansiering, den totala tillgängliga budgeten för finansiering av projekten och väljarnas preferenser framför projektet. Resultatet av en PB -algoritm är en budgetfördelning mellan projekten - bestämmer hur mycket pengar som ska avsättas till varje projekt.

En PB -algoritm kan behandla projekten som antingen delbara eller odelbara :

En delbar PB -algoritm kan tilldela valfri summa pengar till alla projekt, så länge summan av tilldelningar är lika med budgeten. Den är lämplig för projekt där varje ytterligare dollar kan användas effektivt, till exempel donationer till välgörenhet.
En odelbar PB -algoritm tar, som ytterligare ingångar, kostnaderna för projekten. Det returnerar en delmängd av projekten, så att den totala kostnaden för de valda projekten inte överstiger budgeten. Varje utvalt projekt tilldelas hela sin kostnad, medan varje icke -valt projekt tilldelas ingenting. Den är bättre lämpad för projekt som måste finansieras helt för att fungera, till exempel att bygga nya byggnader.

Inmatningsformat

En viktig övervägande vid utformningen av en PB -algoritm är vilket inmatningsformat som ska användas för att få fram preferenser - hur varje väljare ska uttrycka sina preferenser framför projekten. Flera inmatningsformat som används i praktiken är:

Godkännandeomröstning : varje väljare anger en delmängd av projekten som de "godkänner" (betraktas som värdefulla), medan de andra anses vara otillåtna. Detta är som ett binärt poängsystem där varje väljare kan betygsätta varje projekt som antingen 1 eller 0.
k -godkännande röstning : varje väljare anger en delmängd av sina bästa k -projekt - de k -projekt som de anser vara de mest värdefulla.
Tröskelvärdesgodkännande : givet ett tröskelvärde t anger varje väljar delmängden av alla projekt som de värderar som minst t .
Rankad röstning : varje väljare anger en hel preferensrelation framför projekten, specificerar projektet som de anser vara det mest värdefulla, det näst mest värdefulla, etc.

Dessa inmatningsformat är problematiska för odelbara PB, eftersom de ignorerar projektens olika kostnader. Några nyare inmatningsformat som tar hänsyn till kostnaderna är:

Ryggsäckröstning : varje väljare anger en delmängd av projekten, så att den totala kostnaden för projekten i delmängden högst är budgeten (oavsett hur många projekt som finns i delmängden). Således måste varje väljare lösa ett individuellt ryggsäcksproblem - hitta den delmängd som maximerar deras personliga nytta under budgetbegränsningen. En fördel med ryggsäckröstning är att om algoritmen gör varje projekt med antalet röster som det fick och väljer proj grådigt i fallande poängordning tills budgeten är fylld, så är ryggsäckröstning en delvis sanningsenlig mekanism .
Värde för pengarna : varje väljare rankar projekten, inte efter deras totala värde, utan efter deras värde/kostnadskvot.

De olika inmatningsformaten kan jämföras baserat på implicit utilitaristisk röstning - hur mycket varje ingångsformat är användbart för att maximera summan av verktyg. Ur detta perspektiv är tröskelgodkännande röstning bättre än ryggsäckröstning, rangordning-efter-värde och rangordning-efter-värde-för-pengar: det minimerar snedvridningen från den maximala summan av nyttor både teoretiskt och empiriskt.

Efter att systemet har fått medborgarnas insatser bör det beräkna en budget. Det finns olika kriterier för att en budget kan utvärderas.

Budget för ryggsäck

Den budgeteringsmetod som är vanligast i praktiken är en girig lösning på en variant av ryggsäckproblemet : projekten ordnas efter minskande ordning på antalet röster de fick och väljs en efter en tills budgeten är full. Alternativt, om antalet projekt är tillräckligt litet, kan ryggsäckproblemet lösas exakt genom att välja en delmängd projekt som maximerar medborgarnas totala lycka. Nackdelen med denna metod, ofta kallad individuellt bästa ryggsäckbudgettering , är att den kan vara orättvis mot minoriteter: om 51% av befolkningen stöder 10 projekt och 49% stöder 10 andra projekt, och pengarna räcker bara för 10 projekt, då ryggsäckbudgetering kommer att välja de 10 projekten som stöds av 51%, och ignorera de 49% helt och hållet.

Två alternativ till individuellt bästa ryggsäcken är:

Diverse ryggsäckar - maximerar antalet medborgare som har minst en föredragen post i budgeten (på samma sätt som Chamberlin -Courant -regeln för flervinnare ).
Nash -optimal ryggsäck - maximera produkten från medborgarnas verktyg.

Tyvärr, för allmänna användningsdomäner, är båda dessa regler NP-svåra att beräkna. Diverse ryggsäckar är emellertid polynomiskt lösbara på specifika preferensområden, eller när antalet väljare är litet.

Majoritetsbudgetering

Ett sådant kriterium är Condorcet -kriteriet : den valda budgeten bör vara minst lika bra som någon annan föreslagen budget, enligt en majoritet av väljarna (ingen föreslagen ändring av den har majoritetsstöd bland rösterna). Det finns en polynom-tidsalgoritm för att hitta en sådan budget. Algoritmen använder Schwartz -uppsättningar .

Proportional budget

En annan uppsättning kriterier är relaterad till proportionell representation . Dessa kriterier generaliserar de motiverade representationskriterierna från omröstning med flera vinnare . Tanken med dessa kriterier är att om det finns en tillräckligt stor grupp väljare som alla är överens om ett specifikt projekt, så ska detta projekt få en tillräckligt stor del av budgeten.

Uttrycken nedan formaliserar denna intuition när det gäller odelbar PB och godkännande omröstning, dvs.

Det finns m diskreta projekt; varje projekt j kräver en kostnad c _j .
Det finns n väljare; varje väljare har en uppsättning projekt som de anser vara önskvärda.
Målet är att besluta om en delmängd av projekt fond, med en total kostnad av högst L .

Nedan anger L budgetgränsen.

Strong Budget-Justified-Representation (BJR) innebär att för varje väljargrupp av minst n / L , om alla stöder minst ett projekt, finansieras minst ett projekt som alla önskar.
Strong Budget-Proportional-Justified-Representation (BPJR) betyder att för varje heltal k och varje väljargrupp med storlek minst kn / L , om projekten som stöds av dem alla kostar minst k , då projekten som stöds av alla av dem borde få en finansiering på minst k .

Tyvärr finns det kanske inte starka BJR -budgetar (och det är uppenbarligen samma sak för stark BPJR, eftersom BJR är ett specialfall av BPJR för k = 1). Anta till exempel att det finns två projekt med kostnad 2, budgetgränsen är 3 och det finns två väljare som var och en önskar ett enda projekt. Varje väljare är sedan en grupp av storlek 1> 2/3, så BJR kräver att varje väljares projekt finansieras, men summan av kostnaderna för båda projekten är 4> 3. Därför har svagare varianter av dessa kriterier föreslagits:

Svag BJR betyder att för varje väljargrupp av storlek minst n / L , om alla stöder minst ett projekt med kostnad ett (minimikostnaden) , finansieras minst ett projekt som alla önskar.
Svag BPJR betyder att för varje heltal k och varje väljargrupp av storlek minst kn / L , om projekten som stöds av dem alla kostar minst k , då finansieringen för projekt som stöds av dem alla bör vara minst maximal kostnad för en projektundermängd med högst kostnad k som stöds av dem alla.

Lyckligtvis finns svaga BPJR-budgetar (och därmed svaga BJR-budgetar) alltid tillgängliga och kan hittas av en superpolynomisk algoritm. Att hitta en svag-BPJR-budget är NP-svårt, men att hitta en svag-BJR-budget kan göras med en polynom girig algoritm .

Ett annat kriterium, Svag lokal BPJR , är svagare än svag BPJR men starkare än svag BJR; den kan hittas av en polynom- tidsalgoritm baserad på Phragmens sekventiella regel.

Var och en av dessa kriterier har en svagare variant där, i stället för den externa budgetgränsen L , nämnaren är W , vilket är det faktiska beloppet som används för finansiering. Eftersom vanligtvis W < L är W -varianterna lättare att tillfredsställa än deras L -varianter.

Kärnbudgetering

När det gäller delbar PB och verktygsröstning är en övertygande budgeteringsmetod en baserad på kärnan i det underliggande spelet. En budget anses vara "i kärnan" om ingen delmängd av k väljare kan ta sin del av budgeten ( k L / n ) och finansiera en delmängd av projekten så att användningen av varje väljare i delmängden strikt ökar. Det finns effektiva algoritmer för att beräkna kärnbudgeten för vissa naturliga klasser av verktygsfunktioner.

Givarsamordning

Den samordning mellan givarna problemet är en variant av delbart PB där budgeten doneras av väljarna själva (snarare än fast i förväg). En samordningsalgoritm kan förbättra effektiviteten i fördelningen av medel. Anta till exempel att tre projekt övervägs: teater, schackklubb och basketplan. Det finns två givare: Alice och Bob, som alla vill bidra med 3000. Alice föredrar inomhusaktiviteter (teater eller schack), medan Bob föredrar tävlingsaktiviteter (schack eller basket).

Om de inte samordnar, så bidrar Alice naturligtvis 1500 till varje inomhusaktivitet, medan Bob bidrar med 1500 till varje tävlingsaktivitet. Den resulterande fördelningen är 1500, 3000, 1500. Varje givare känner en lycka på 4500 från donationerna till hans/hennes föredragna projekt.
Om de däremot samordnar kan de bidra med allt till schackklubben, så fördelningen blir 0, 6000, 0. Nu känner varje givare en lycka på 6000, så denna fördelning Pareto-dominerar den föregående.

Eftersom donationerna är frivilliga är det viktigt att koordineringsalgoritmen säkerställer att varje väljare tjänar svagt på att delta i algoritmen, dvs det belopp som bidragit till projekt han godkänner är svagt högre när han deltar än när han inte gör det. Detta krav kan vara oförenligt med effektiv budgetallokering när väljarnas verktyg är allmänna linjära funktioner.

Det är dock uppnås när väljarnas verktyg är linjära och binära , dvs i godkännanderöstningsmodell:

Det finns m välgörenhetsorganisationer; varje välgörenhetsorganisation kan dra nytta av hur mycket pengar som helst.
Det finns n givare; varje givare har en uppsättning välgörenhetsorganisationer som han/hon bryr sig om. Varje givare i är villig att donera ett totalt belopp av C _i .
Målet är att besluta om en fördelning av de totala medel som samlats in från alla givare (summan av C _i ) mellan m välgörenhetsorganisationer. Användningen av varje agent från en given distribution är summan av pengar som tilldelas hans/hennes älskade välgörenhetsorganisationer.

Flera regler har analyserats i denna inställning. De exemplifieras nedan för en miljö med 4 välgörenhetsorganisationer (a, b, c, d) och 5 givare som bidrar med 1 vardera, och vars älskade uppsättningar är ac, ad, bc, bd, a.

Den okoordinerade regeln delar bara bidraget från varje agent i bland de välgörenhetsorganisationer som jag gillar . Så finansieringsfördelningen är 2,1,1,1 och de fem agenternas verktyg är 3,3,2,2,2. Denna mekanism är genomförbar och individuellt rationell, men inte effektiv: utfallet domineras till exempel av fördelningen 3,2,0,0, där verktygen är 3,3,2,2,3.
Den Nash optimala regeln finner en budget tilldelning maximera produkten av verktyg. Det är Pareto optimalt , genomförbart och individuellt rationellt. Det är dock inte strategiproof eller resursmonotoniskt .
Den begränsade-utilitaristiska regeln finner en budgetfördelning som maximerar summan av verktyg från uppsättningen av alla implementerbara regler. Det är implementerbart, individuellt rationellt, strategiskt bevisat och resursmonotoniskt. Det är dock inte pareto-optimalt.
Det finns ingen PB -regel som uppfyller alla fem egenskaper, även med binära preferenser.

Se även

Flervinnarröstning - kan ses som ett särskilt fall av deltagande budget, där "kostnaden" för varje kandidat är 1, och budgeten är parlamentets storlek.

Languages

In other projects