Introduction
Participatory budgeting (PB) is a democratic process where community members decide how to spend part of a public budget. A primary goal in PB is proportionality: ensuring that groups of voters receive a share of the budget proportional to their size. The Method of Equal Shares (MES) has emerged as a standard for achieving this, yet it faces practical challenges that limit its effectiveness in real-world applications.
The Limitations of Method of Equal Shares
Despite its theoretical strengths, MES exhibits three significant "bugs" that can lead to suboptimal outcomes:
- Underspending: MES is often too conservative, stopping as soon as no group can perfectly afford a project. On average, it utilizes only about 45% of the available budget.
- The Helenka Paradox: This occurs when a small, unanimous group funds a project that marginally exhausts the budget, preventing a much larger project supported by the vast majority from being selected.
- Tail Utilities: By focusing on the least-satisfied voter in a group (an egalitarian approach), MES may ignore projects that provide high utility to nearly everyone if even one person in the group is less enthusiastic.
Proposed Solution: BOS Equal Shares
To overcome these flaws, the authors introduce BOS Equal Shares (Method of Equal Shares with Bounded Overspending). The core innovation is to view the discrete selection of projects as a rounding of a continuous, fractional solution.
Fractional Equal Shares (FrES)
The process begins with a theoretical rule where projects can be partially funded. FrES distributes the budget equally among voters and selects fractions of projects based on their "price per unit of utility" ($\rho$).
Bounded Overspending (BOS)
Since real-world projects are indivisible, BOS "rounds" the fractional solution. If the fractional method suggests funding a portion $\alpha$ of a project, BOS funds the entire project but allows voters to "overspend" their virtual budgets if necessary. Once a voter's budget is exhausted, it is set to zero for subsequent rounds.
A more advanced version, BOS+, incorporates a completion strategy to ensure high performance even in edge cases where standard BOS might pick less popular projects.
Empirical Evaluation and Results
The researchers tested BOS and BOS+ using PABULIB, a library of over 1,200 real-world PB instances, and synthetic datasets. The results highlight several key advantages:
- High Budget Utilization: BOS spends approximately 94% of the budget in a single pass, a massive improvement over the 45% achieved by basic MES.
- Robust Fairness: While BOS relaxes some strict fairness axioms to gain efficiency, it still satisfies a strong standard ("EJR+ up to one") in over 95% of real-world cases.
- Increased Voter Inclusion: Compared to MES, BOS significantly reduces the "exclusion ratio," meaning fewer voters end up with none of their preferred projects funded.
- Computational Speed: BOS is an order of magnitude faster than MES variants that require iterative completion steps, making it highly scalable for large cities.
Conclusion
BOS Equal Shares represents a significant step forward for participatory budgeting. By allowing for bounded overspending, the rule bridges the gap between theoretical proportionality and practical efficiency. While it does not strictly guarantee every fairness axiom, its empirical performance suggests it is a superior choice for real-world democratic decision-making. Future research will focus on extending these principles to non-additive utility models and other areas of social choice.
Summary updated