Municipal Budget Allocation
0-1 Knapsack · equity-aware weights · capital projects
A city council has a capital budget. It receives proposals for projects: a park, a library renovation, a water-main upgrade, a community centre. Each has a cost and an expected public-value score. Which projects do they fund? The operational problem is the classical 0-1 knapsack — Dantzig's 1957 LP formulation, Bellman's dynamic programming, Martello & Toth (1990) textbook. What makes it a public-services problem is that the “value” score is contested — utilitarian benefit-cost ratios, equity-weighted Gini corrections, and participatory-budgeting alternatives all give different answers.
Problem context
Which projects, which weights, whose value
A municipal capital budget, typically set annually, funds discrete projects — infrastructure, facilities, equipment — each with a one-time cost drawn from the budget. Operating expenses (salaries, utilities) are typically separate. Each candidate project carries a cost ci and a perceived benefit vi; the 0-1 knapsack selects a subset maximising total benefit within budget.
The OR framing is simple; the policy tension lives in vi. A cost-benefit-analysis (CBA) score is the utilitarian approach: discounted future benefits minus costs. Marsh & Schilling (1994)'s equity-aware framework adds a weight for the demographic distribution of benefits — a project that benefits already-advantaged neighbourhoods gets a lower effective weight than one benefiting under-served ones. Karsu & Morton (2015) survey inequity-averse formulations more generally.
Participatory budgeting (PB) is the institutional alternative: let residents directly vote on project selection. Pioneered in Porto Alegre, Brazil (1989), PB has spread to thousands of cities worldwide (Wampler 2007); it converts the optimisation from expert-knapsack to a social-choice problem (see the matching mechanisms page for the mechanism-design adjacent literature).
Multi-stakeholder framing
Mathematical formulation
0-1 knapsack with optional equity weights and interdependencies
| Symbol | Definition | Domain |
|---|---|---|
| I | Set of candidate projects | |I| = n |
| ci | Cost of project i | ℝ⁺ |
| B | Total budget | ℝ⁺ |
| vi | Utilitarian benefit / NPV score | ℝ⁺ |
| ei | Equity weight (demographic-distribution factor) | ℝ⁺ |
| xi | Binary: 1 if project i is funded | {0, 1} |
| Pk | Subset of projects that are interdependent (prereq / exclusion) |
s.t. Σi ci xi ≤ B // budget
xi ∈ {0, 1}
Equity-weighted variant (Marsh-Schilling 1994) max Σi ei vi xi // equity-adjusted total benefit
// e_i > 1 for projects in under-served districts; e_i < 1 for over-served. Enshrines equity pref in the objective.
With interdependencies Add: xi ≤ xj for prerequisites (i needs j done first)
xi + xj ≤ 1 for mutual exclusivity
per-category budget caps (Σi ∈ cat k ci xi ≤ Bk)
Complexity NP-hard (weakly); pseudo-polynomial dynamic programming in O(n · B); LP relaxation gives fractional-project bound; Martello-Toth-style branch-and-bound practical for n ≲ few thousand.
Interactive solver
Select projects under budget, compare utilitarian vs equity-weighted
Budget Knapsack Solver
Solution interpretation
Utilitarian vs equity-weighted: what changes
DP finds the exact optimum; greedy by value/cost ratio typically gets within a few percent. For small n (≤ 30), DP is instant and gives the right answer.
Switching to equity-weighted typically moves the funded set toward projects in under-served districts — even when those projects have lower utilitarian vi. The total unweighted benefit may fall; the equity-weighted objective is what rises.
Budget tightening exposes the priorities: at 20% budget, only the highest value/cost projects make the cut; at 70% budget, almost everything is funded and the choice of weights barely matters. The action is in the middle.
Limitations & Critique
Why a knapsack isn't a budget
Benefit scores are contested
vi is supposedly a dollar-denominated benefit, but many public-service benefits resist dollar valuation — parks for children, library hours for seniors, accessibility improvements. Setting arbitrary dollar values compresses the problem into a knapsack but smuggles in contestable assumptions.
Equity weights are political, not technical
Marsh-Schilling equity weights require specifying how much to favour under-served districts. There is no neutral answer: ei = 1 (utilitarian) and ei proportional to historical underinvestment are both defensible; neither is “correct.” The optimiser surfaces the choice but cannot make it.
Project interdependencies are non-trivial
Building a library without a road to it is pointless; opening a facility needs an operating budget too. Pure knapsack ignores these logical relationships. Adding prerequisite / mutual-exclusion / category-cap constraints extends the MILP and is routinely needed in practice.
Log-rolling & political feasibility
Real councils trade votes: “I vote yes on your library if you vote yes on my pool.” This log-rolling produces outcomes that are not knapsack-optimal but are the only politically-passable set. An OR-optimal budget that cannot pass council is less useful than a somewhat-inferior one that can.
Participatory budgeting as an alternative
Porto Alegre (1989), New York City (2011), and many others let residents directly vote on project selection. PB trades away some utilitarian efficiency but gains legitimacy and accountability. For many small/mid-sized cities, PB outperforms expert optimisation on political-sustainability metrics.
Multi-year dynamics
A one-year knapsack ignores capital-project life cycles, maintenance obligations, and future constraints. A cheap-looking capital project with a large ongoing operations cost is bad news; dynamic multi-year formulations exist but are rarely solved exactly in practice.
Extensions & variants
Multi-dimensional, dynamic, participatory
Multi-dimensional knapsack
Separate budget constraints per category (infrastructure vs parks vs buildings). Standard extension; NP-hard.
Participatory-budgeting optimisation
Social-choice-based allocation aggregating voter preferences; Goel-Krishnaswamy-Sakshuwong-Aitamurto 2019.
Dynamic multi-year budgeting
Projects span multiple years; maintenance obligations; net-present-value discounting. Drezner-Erkut 1995.
Stochastic benefits
Project outcomes uncertain; robust / stochastic knapsack formulations. Morton-Wood 1998.
Integer-programming decomposition
Lagrangian relaxation, Benders decomposition for large-scale MILP with category caps and interdependencies.
Bi-objective Pareto frontier
Explicit tradeoff between utilitarian and equity-weighted objectives; presents a frontier rather than a single solution.
Fair allocation axioms
Proportional representation, Nash social welfare, max-min share. Connects to fair-division literature; Procaccia 2013.
Ranking vs. approval PB
Voting structures differ — ranked-choice, approval, cumulative, knapsack voting. Benadè et al. 2021 on fair allocation in PB.
Key references
Cited above
Related applications
Allocation, fairness, and social-choice siblings