Knapsack Voting for Participatory Budgeting

Ashish Goel; Anilesh K. Krishnaswamy; Sukolsak Sakshuwong; Tanja Aitamurto

Source-linked AI summary

Knapsack Voting for Participatory Budgeting

Ashish Goel, Anilesh K. Krishnaswamy, Sukolsak Sakshuwong, Tanja Aitamurto

arXiv:2009.06856v1Sep 15, 2020cs.GTcs.CY

TL;DR

Participatory budgeting needs preference aggregation that reflects both project benefits and a fixed budget, whereas existing K-approval does not let voters express cost-aware combinations. The paper introduces Knapsack Voting and value-for-money comparisons, establishes strategy-proofness results under several utility models, extends the method to revenues and deficits, and evaluates implementations in real elections. The evidence supports more economical consideration and closer agreement with pairwise preferences than K-approval, while the authors identify limits for large ballots and societal-value claims.

Problem
Participatory budgeting requires aggregating residents’ project preferences under budget constraints, but K-approval does not let voters express cost-aware combinations.
Method
The paper introduces Knapsack Voting, value-for-money comparisons, strategic analyses under multiple utility models, extensions to revenues and deficits, and digital-election implementations.
Results
Knapsack Voting is strategy-proof under ℓ1 and Overlap utility, partially strategy-proof under additive concave utility, and empirically more economical and more aligned with pairwise comparisons than K-approval.
Takeaways & Limitations
Knapsack Voting incorporates budget constraints into preference elicitation and provides a deployable alternative whose outcomes better reflect observed value-for-money comparisons than K-approval.
Takeaways & Limitations
Knapsack Voting is not very practical with a large number of projects, and the authors do not claim that it yields outcomes more beneficial to society as a whole.

Abstract

from arXiv · show

We address the question of aggregating the preferences of voters in the context of participatory budgeting. We scrutinize the voting method currently used in practice, underline its drawbacks, and introduce a novel scheme tailored to this setting, which we call "Knapsack Voting". We study its strategic properties - we show that it is strategy-proof under a natural model of utility (a dis-utility given by the $\ell_1$ distance between the outcome and the true preference of the voter), and "partially" strategy-proof under general additive utilities. We extend Knapsack Voting to more general settings with revenues, deficits or surpluses, and prove a similar strategy-proofness result. To further demonstrate the applicability of our scheme, we discuss its implementation on the digital voting platform that we have deployed in partnership with the local government bodies in many cities across the nation. From voting data thus collected, we present empirical evidence that Knapsack Voting works well in practice.

1 Introduction

Participatory budgeting asks residents to allocate a fixed local budget among projects, but commonly used K-approval voting does not let voters express cost-aware combinations. The paper motivates mechanisms that incorporate budget constraints into preference elicitation.

Participatory budgeting lets residents vote on projects such as streets, lighting, playgrounds, and parks to allocate local-government budgets.
The proposed direction uses Knapsack Problem ideas and seeks mechanisms that consider costs and benefits while remaining implementable through digital tools.
K-approval voting: K-approval lets each voter approve at most K projects, ranks projects by approval totals, and funds them in that order until the budget is exhausted.
K-approval voting: Because K-approval does not make voters account for project costs, it can prevent them from expressing that a feasible combination of several projects is preferable to one individually stronger project.
The paper therefore asks how to elicit voter preferences and which utility models can provide insight into that problem.

1.2 Modeling assumptions: voting and utility models

The paper models participatory budgeting as allocating a fixed budget across projects, primarily allowing fractional funding. It evaluates outcomes using distance-, overlap-, and additive-concave utility models.

Participatory budgeting has projects with costs c_j and a fixed total budget B, which voters allocate across projects.
The primary model is fractional: voters may allocate the budget arbitrarily across projects, with every project fractionally implementable and the full budget spent.
The paper notes that partial funding and spending the entire budget are both common in practice, although fractional implementation may not fit every project.
The ℓ1 cost model measures how far an outcome is from a voter’s ideal allocation, while Overlap utility captures the overlap between the outcome and that allocation.
Additive concave utility generalizes Overlap utility by assigning each project a non-decreasing concave utility function of its allocation.

1.3 Our contributions

The paper introduces Knapsack Voting and value-for-money comparisons as cost-aware alternatives to K-approval, analyzes their strategic properties, and tests them in participatory-budgeting elections. Knapsack Voting is strategy-proof under ℓ1 or Overlap utility and partially strategy-proof under additive concave utility, while experiments find more economical consideration and stronger agreement with pairwise comparisons than K-approval.

Knapsack Voting: Knapsack Voting applies approval voting to participatory budgeting by requiring voters to choose projects under the budget constraint.
Knapsack Voting: Under the ℓ1 cost and equivalent Overlap utility models, Knapsack Voting is strategy-proof and welfare-maximizing.
Knapsack Voting: Knapsack Voting also extends to settings with revenues, surpluses, or deficits, where the paper proves similar strategy-proofness results.
Knapsack Voting: Under additive concave utilities, a voter’s best response is partially strategy-proof: favoring projects that win without the voter is in the voter’s best interest.
Value-for-money comparisons: Value-for-money comparisons elicit preferences by asking voters to compare projects according to utility normalized by cost.
Deployments and Data Analysis: The methods were implemented through a digital voting platform used across participatory-budgeting elections, including Knapsack Voting as the official ballot in Boston’s 2016 election.
Deployments and Data Analysis: Knapsack Voting leads to more economical project consideration and better agreement with pairwise comparisons than K-approval, while taking similar voter time.
Conclusions and ongoing work: The authors caution that Knapsack Voting is impractical with many projects and do not claim that it produces outcomes more beneficial to society as a whole.

1.4 A discussion of utility models

The paper examines utility models for participatory-budgeting allocations, including fixed and variable project costs, and relates them to Knapsack Voting. It focuses on ℓ1 distance, Overlap utility, and general additive concave utilities, with strategy-proofness motivating the modeling assumptions.

Fractional allocations: The analysis assumes a fractional budget model for variable project allocations and uses a per-dollar version of Knapsack Voting to avoid combinatorial difficulty.The same setting is relevant to budget problems with variable project funding, including broader public-budget applications.
Per-dollar voting: The paper illustrates the per-dollar procedure by dividing projects into dollar subprojects, assigning votes to preferred dollars, and selecting the highest-vote dollars within the budget.In the example, the selected dollars yield allocation (3, 5, 2) from project maximum costs (5, 5, 10).
ℓ1 cost model: Under the ℓ1 cost model, a voter’s disutility is the distance between the preferred and outcome allocations, but applying it to outcomes smaller than the total budget violates free disposal.The paper notes that the model is meaningful under the stated budget-size assumption, not in the purely integral smaller-outcome setting.
Overlap utility: In the fractional setting, the ℓ1 model is equivalent to Overlap utility, which counts matching dollar subprojects between a voter’s preference and the outcome.This equivalence is used in the proof of Result 1.1.
Additive utilities: General additive utilities assign each project a concave utility in its allocated amount and strictly generalize the Overlap utility model.The paper uses this model to establish its partial strategy-proofness result.

1.5 Related Work

Related work covers approval and ranked voting, budget-constrained set selection, and strategy-proof social choice. The paper positions Knapsack Voting as a budget-respecting aggregation rule connected to geometric medians and restricted-domain strategy-proofness.

Voting and weighted selection: Prior work studies approval, ranked voting, and algorithms for selecting weighted candidate sets under a sum-weight constraint.These lines of research provide background for comparing candidate-selection rules with participatory-budgeting aggregation.
Strategy-proofness literature: Classical work shows that strategy-proof social-choice functions are severely restricted in general, while restricted preference domains such as single-peaked preferences permit broader strategy-proof rules.Generalized Median Voter Schemes characterize strategy-proof rules in the cited single-dimensional setting.
Strategy-proof aggregation: Knapsack Voting finds a geometric median of votes on the budget simplex and is strategy-proof under specific utility models, including the ℓ1 cost model.The rule is also described as analogous to Approval Voting with dichotomous preferences.
Budget constraints: Generalized Median Voter Schemes do not respect the budget constraint when there are three or more projects.This motivates studying aggregation rules designed specifically for budget-constrained allocations.
Positioning: The paper distinguishes its approach from mechanisms that can be √m log m away from optimal outcomes, fail to extend generally to fractional settings, or lack transparency for formal ballots.It also notes that simple, well-defined participatory-budgeting items can be presented concisely on a digital platform.

2 Knapsack Voting: Imposing budget constraints

Knapsack Voting makes voters choose a budget-constrained allocation and establishes strong incentive and welfare guarantees under several utility models and budget settings.

2 Knapsack Voting: Imposing budget constraints: Voters submit consistent subsets of per-dollar sub-projects containing exactly B elements, and projects are selected by approval scores with deterministic tie-breaking.Fractional project allocations are represented by splitting projects into per-dollar sub-projects.
2.1 Strategy-proofness under the ℓ1 cost model: The outcome can be viewed as an ℓ1-median restricted to the budget simplex, minimizing the sum of voters’ ℓ1 distances.This median interpretation connects the mechanism’s outcome to aggregate welfare under the ℓ1 model.
2.1 Strategy-proofness under the ℓ1 cost model: Under Overlap utility, voting for a preferred allocation is a weakly dominant strategy, yielding strategy-proofness and welfare maximization.The paper establishes an equivalence between the ℓ1 cost and Overlap utility models in the budgeted setting.
2.1 Strategy-proofness under the ℓ1 cost model: Knapsack Voting is strategy-proof and welfare-maximizing under the ℓ1 costs model.Truthful voting is a weakly dominant strategy, and the resulting outcome maximizes social welfare.
2.2 Revenues, deficits and surpluses: Knapsack Voting remains strategy-proof with a balanced budget and extends to revenues, surpluses, and deficits.For unbalanced settings, deficit preferences are incorporated as an additional disutility term; additive concave utilities receive a partial strategy-proofness result.
2.4 Maximum Likelihood Interpretation: Under the Noisy Knapsack Vote Model, the Knapsack rule returns the maximum likelihood estimate.The model places a distribution directly over subsets and relates agreement with votes to Overlap and ℓ1 utility.

3 Voting based on value-for-money

Value-for-money voting elicits pairwise cost-benefit comparisons and supports paper-ballot implementations and empirical analysis, but lacks the strategic guarantees and extensions of Knapsack Voting.

3 Voting based on value-for-money: Value-for-money schemes cannot guarantee good strategic properties and do not naturally extend to revenues, deficits, or surpluses.They are also less transparent because voters provide different information and aggregation is less direct.
3 Voting based on value-for-money: Value-for-money schemes may reduce voters’ cognitive load and support aggregation when the budget is unknown or not fixed in advance.These are presented as potential advantages despite their weaker strategic and transparency properties.
3.1 Value-for-money ranking: In Boston 2016, voters ranked their top four projects by value-for-money on a paper ballot, and the resulting outcome matched Knapsack Voting exactly.The ballot was designed as a paper implementation because directly performing Knapsack Voting on paper is tedious.
3.2 Value-for-money comparisons: Value-for-money comparisons ask voters to choose between randomly selected pairs of projects while considering costs and benefits.These comparisons provide fine-grained information about aggregate preferences between projects.
3.2 Value-for-money comparisons: The Cambridge and Vallejo comparison data show a nearly transitive majority relation, producing an ordered structure among projects.A Condorcet winner repeatedly emerges after removing the previous winner; when this structure fails, aggregation becomes more complicated.
3.3 Set-Borda score: The Set-Borda score generalizes Borda’s rule to project sets by measuring agreement with pairwise dollar-versus-dollar comparisons.It is used as a social-welfare measure for empirically comparing outcomes of Knapsack Voting and value-for-money schemes.

4 Our digital platform, and results from our experiments

The experiments compare Knapsack Voting with K-approval and value-for-money comparisons across participatory budgeting elections. The data indicate that Knapsack produces more frugal outcomes, agrees more with pairwise preferences, and remains practical to use digitally.

4.1 Cost consideration under Knapsack: K-approval over-represents costlier projects relative to Knapsack and the uniform distribution in Cambridge 2015 and NYC District 8.The comparison uses cumulative fractions of votes above project-cost thresholds.
4.1 Cost consideration under Knapsack: Knapsack Voting reduces the average cost of winning projects by about 30% across three places compared with K-approval.The authors interpret this reduction, together with cumulative vote comparisons, as evidence that voters choose more frugally under Knapsack Voting.
4.3 Ease of use: At least one-third more voters completed value-for-money comparisons than Knapsack or the corresponding comparison condition in Boston 2015 and Cambridge 2015.Voters were randomly assigned to Knapsack or value-for-money experiments in those elections.
4.3 Ease of use: Knapsack Voting and K-approval have comparable completion times, while value-for-money comparisons impose a smaller cognitive load.In Boston 2015, median times were 61 seconds for K-approval, 70 seconds for Knapsack, and 14 seconds for four value-for-money comparisons.
4.2 Agreement with value-for-money comparisons: Knapsack achieves greater agreement with voters’ pairwise value-for-money comparisons than K-approval.The comparison is based on the difference between comparisons agreeing and disagreeing with each method’s winning set.

5 Conclusions and ongoing work

The paper concludes that Knapsack Voting and value-for-money comparisons are intuitive preference-elicitation methods for participatory budgeting. It reports strategic and empirical advantages while noting that Knapsack Voting becomes impractical with many projects.

5 Conclusions and ongoing work: Knapsack Voting is strategy-proof under an overlap-based utility model equivalent to ℓ1 distance and extends to settings with revenues, deficits, and surpluses.The conclusion also reports empirical support for the schemes across participatory budgeting elections.
5 Conclusions and ongoing work: Knapsack Voting is not very practical when the number of projects is large, whereas value-for-money comparisons impose a smaller cognitive load on large ballots.The conclusion presents both methods as suitable for interactive digital implementation.
5 Conclusions and ongoing work: The authors report that their schemes perform better on many measures in data collected from participatory budgeting elections across cities and municipalities.They also state that the schemes can be implemented with interactive digital tools.

A.1 Extending results (approximately) to an Integral Model

The strictly integral Knapsack Vote does not preserve the main strategic results, but an approximately integral variant does, extending them with an error bounded by one project.

Strictly integral model: The strictly integral model can violate strategy-proofness: changing a vote from {b,c} to {a,c} changes the outcome from {a,b} to {a,c}, which the voter prefers.The example uses a budget of 5 and project costs 2, 2, and 3.
Approximately integral model: The approximately integral model permits the first unaffordable project in approval-score order to be fractionally implemented, exhausting the budget.Projects are ordered by approval scores, funded sequentially, and the next project is partially funded when the remaining budget is insufficient.
Model assumptions: The ℓ1 cost model is unsuitable for fully integral outcomes, whereas both ℓ1 costs and Overlap utilities satisfy free disposal with approximately integral outcomes.This distinction motivates the approximately integral treatment of the integral setting.
Approximately integral model: Theorems 2.1, 2.2, and 2.4 extend to the approximately integral model, where voting for a voter’s favorite set is weakly dominant under the stated assumptions.The extension follows by simple modifications of the original proofs.
Strictly integral model: Under the strictly integral model, the results hold approximately under Overlap utilities, with the loss bounded by the value of one project.The corresponding set outcome is at least as useful as any alternative integral outcome minus the value of the fractionally implemented project.

A.2 Proof of Theorem 2.3

The proof of Theorem 2.3 transforms best responses while preserving or increasing utility, then identifies the resulting outcome as welfare-maximizing under Overlap utility.

Outcome comparison: The proof tracks score changes caused by adding two elements and shows that any changed outcome must include one of those elements.The resulting sets expand while maintaining equal cardinality.
Best-response transformation: The proof adds missing favored subprojects and corresponding revenue or deficit elements without decreasing the voter’s utility, producing an equally sized best response.The process repeatedly balances changes between the two sides until the response sizes match the original vote sizes.
Best-response transformation: After the transformation, the proof applies the argument from Theorem 2.1 until only elements in the voter’s favored set remain.The cited procedure preserves utility throughout.
Welfare maximization: The resulting consistent outcome maximizes the welfare objective, which equals welfare under the Overlap Utility Model.The proof characterizes the outcome as a pair of equally sized consistent sets maximizing the stated objective.

A.3 Proof of Theorem 2.4

The proof characterizes a focal voter’s best response under per-dollar voting and shows that beneficial replacements preserve validity while ensuring preferred candidates win. A sequence of such replacements establishes the theorem’s required best response.

The proof models voter i’s best response as a consistent vote of exactly B projects against the aggregate votes of the other voters.The resulting winner set is denoted W(S_i, S_{−i}), and the voter is assumed to know the other voters’ aggregate outcome.
A candidate j that dominates a currently selected project p must win in any best response, because replacing p with j strictly increases voter i’s utility.The proof considers whether j is already selected and handles both cases separately.
If j is not selected, switching from p to j yields a valid vote and makes j win instead of p, contradicting the assumed best response when voter i values j more.This establishes the key replacement argument for the second case.
The replacement construction preserves the vote’s size and consistency by choosing projects outside the relevant winning set and avoiding Λ_i,p when necessary.The proof verifies |S_2| = B and then repeats the replacement procedure for additional dominated candidates.