Knapsack Voting
Participatory budgeting (PB), where residents of a community have a direct say in how a portion of public funds are spent, has become an increasingly popular method for promoting democratic decision-making. The question then arises: what is the best way to allow individuals to express their preferences for various projects? One of the most common ways is through approval voting, where voters either "approve" or "disapprove" each project on the ballot. In this article, we explore another voting method called knapsack voting and discuss its advantages over traditional voting methods.
What is knapsack voting?
A typical knapsack voting ballot (shown below) displays how much money the voter has left. As they vote for a project, the available budget decreases. They can choose as many projects as their budget permits. Knapsack voting provides a more intuitive way for voters to weigh projects against their cost, paralleling the decisions a policymaker would make.
Knapsack voting is inspired by the computer science problem known as the knapsack problem. Imagine you have a backpack (or knapsack) and a variety of items with different weights and values. The goal is to maximize the value of items you can fit into the backpack without exceeding its weight capacity.
In the context of participatory budgeting, each project has a cost (weight) and each voter has a personal value for that project. Voters have a "budget" (akin to the knapsack's weight capacity) and they "spend" their budget on projects they support. The goal is to fund the projects that maximize the collective value for the community, without exceeding the total available funds.
How to tally votes
Once voting is complete, the votes are aggregated to determine the final result. One way to aggregate the votes is to use the knapsack aggregation (also known as the social welfare-maximizing method in some literature). In this method, each dollar in a project is viewed as an individual candidate. For instance, if a project costs $10, it is seen as having 10 candidates. When a voter allocates, say, $3 to this project, it is considered a vote for its first 3 candidates. The candidates receiving the most votes are selected in decreasing order until the budget is exhausted.
For example, suppose that in a participatory budgeting, the budget is $10, there are 3 projects on the ballot, and there are 3 voters. They vote as follows:
| Voter 1 | Voter 2 | Voter 3 | |
|---|---|---|---|
| Library | $4 | $3 | $0 |
| Sports Center | $5 | $5 | $0 |
| Art Museum | $1 | $2 | $10 |
We will tally the votes one by one.
Voter 1 allocates ($4, $5, $1) to (Library, Sports Center, Art Museum).
| Votes per dollar | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Library | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| Sports Center | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| Art Museum | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Voter 2 allocates ($3, $5, $2) to (Library, Sports Center, Art Museum).
| Votes per dollar | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Library | 2 | 2 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| Sports Center | 2 | 2 | 2 | 2 | 2 | 0 | 0 | 0 | 0 | 0 |
| Art Museum | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Voter 3 allocates ($0, $0, $10) to (Library, Sports Center, Art Museum).
| Votes per dollar | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Library | 2 | 2 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| Sports Center | 2 | 2 | 2 | 2 | 2 | 0 | 0 | 0 | 0 | 0 |
| Art Museum | 3 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
If we select the dollars that receive at least two votes (shown in green below), we get exactly $10, which exhausts the budget. Thus, the knapsack aggregation for this PB allots $3 to the Library project, $5 to the Sports Center project, and $2 to the Art Museum project.
| Votes per dollar | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Library | 2 | 2 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| Sports Center | 2 | 2 | 2 | 2 | 2 | 0 | 0 | 0 | 0 | 0 |
| Art Museum | 3 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Why knapsack voting?
Knapsack voting offers two significant advantages over approval voting: expressiveness and strategy-proofness.
Expressiveness
Knapsack voting with knapsack aggregation provides a more intuitive way for voters to weigh projects against their costs. They make the same choice as a policy maker would. With approval voting, cities often limit the number of projects voters can select. Without such limits, a ballot approving all projects would render the same outcome as a null vote. This artificial constraint can force voters to make challenging choices, potentially favoring projects that are more expensive and might not reflect their true preferences
Strategy-proofness
Strategy-proofness means that it is in the best interest of each voter to vote according to their true preference. To see what this means, consider another aggregation method called mean aggregation where we simply find the average of the votes for each project. In the example above, the mean aggregation would allot (4 + 3 + 0) / 3 = $2.33 to the Library project, (5 + 5 + 0) / 3 = $3.33 to the Sports Center project, and (1 + 2 + 10) / 3 = $4.33 to the Art Museum project. Suppose that in another PB, there are two projects on the ballot. A voter likes both projects equally and would like to vote ($5, $5). The voter hears from a poll that Project 1 is much more popular than Project 2, and that almost everyone votes ($10, $0). What should this voter do? It is in their best interest to vote ($0, $10) to "balance the scale", so that the final result gets closer to ($5, $5). Here we see a scenario where it is better for a voter to vote strategically rathen than voting according to their true preference.
In our paper, Knapsack Voting for Participatory Budgeting, we demonstrate that the knapsack voting and aggregation is strategy-proof. That is, it does not suffer from (individual) strategic voting.
Interactive knapsack aggregation
You can use the interactive widget below to try knapsack aggregation with different costs and numbers of projects and voters.
Budget: $10
Support on the platform
The Stanford Participatory Budgeting Platform supports knapsack voting alongside other voting methods. It can be enabled with just a few clicks.
If you would like to run a PB in your city or organization, please email us at contact@pbstanford.org.
Further reading
- Ashish Goel, Anilesh K. Krishnaswamy, Sukolsak Sakshuwong, Tanja Aitamurto. 2019. Knapsack Voting for Participatory Budgeting. ACM Transactions on Economics and Computation. 7, 8:1-8:27.
- Rupert Freeman, David M. Pennock, Dominik Peters, Jennifer Wortman Vaughan. 2021. Truthful Aggregation of Budget Proposals. Journal of Economic Theory, Volume 193, April 2021, 105234.