Project-Fair and Truthful Mechanisms for Budget Aggregation

Rupert Freeman, Ulrike Schmidt-Kraepelin

Abstract

Budget aggregation is a central challenge in participatory budgeting, where collective decisions must be made on how to allocate a fixed budget across multiple projects. While the arithmetic mean is a natural choice for fairness, it is susceptible to strategic manipulation. This paper introduces the Ladder mechanism, a novel strategyproof mechanism within the class of moving phantom mechanisms. By optimizing for "project fairness"—defined as the maximum deviation from the mean for any single project—the Ladder mechanism achieves tight theoretical bounds on underfunding and overfunding, providing a robust solution for truthful budget allocation.

The Challenge of Strategyproofness

In a typical budget aggregation scenario, residents vote on the percentage of a budget that should be allocated to various public projects, such as parks, libraries, or infrastructure. A common approach is to take the mean of all votes. However, the mean is not strategyproof (or truthful). If a voter strongly prefers more funding for parks, they may be incentivized to report a 100% preference for parks—even if that is not their true belief—simply to pull the average in their favored direction.

To prevent this "gaming of the system," researchers look for mechanisms where the dominant strategy for every voter is to report their true preferences. While strategyproof mechanisms exist, they often produce "unfair" results where a project might receive significantly more or less than its "fair share" (the mean). This research seeks a mechanism that is both strategyproof and stays as close to the mean as possible.

The Ladder Mechanism

The authors focus on a class of strategyproof mechanisms known as moving phantom mechanisms. These can be thought of as a high-dimensional extension of the median. In a single-dimension setting, the median is strategyproof. In budget aggregation, where allocations must sum to 100%, one cannot simply take the median for each project independently. Moving phantom mechanisms solve this by introducing "phantom" votes that move as a function of a parameter $t$. As $t$ increases, the phantoms move from 0 toward 1. The mechanism identifies the specific $t$ where the medians of the real votes and the phantoms sum exactly to 1.

The paper proposes the Ladder mechanism, which uses a simple, linear definition for its phantoms.

Visualization of the Ladder mechanism's phantoms $f_k$ across different projects.

As shown in the figure above, the phantoms $f_k(t)$ are defined as $\max(t - k/n, 0)$. This can be visualized as a rope ladder being pulled upward; the rungs (phantoms) start at 0 and become "active" one by one as they cross the threshold. This mathematical simplicity allows for combinatorial proofs of fairness that were previously impossible for more complex, non-linear mechanisms.

Measuring Fairness: The $\ell_\infty$ Approach

Previous research in this field often focused on the $\ell_1$ distance (the sum of all differences from the mean). This paper argues that $\ell_\infty$ distance—the maximum difference for any single project—is a superior measure of project fairness. By minimizing the maximum deviation, the mechanism ensures that no single stakeholder group (e.g., those advocating for "Roads") feels uniquely disadvantaged by the system.

Furthermore, the Ladder mechanism satisfies the property of proportionality: it agrees with the mean when voters are "single-minded" (curing only about one project), a key requirement for perceived fairness in social choice.

Key Results and Optimality

Using mathematical proofs and worst-case analysis, the authors demonstrate that the Ladder mechanism is optimal within its class:

  • Optimal Underfunding Bound: The mechanism is guaranteed to never underfund a project by more than $\frac{1}{2} - \frac{1}{2m}$ relative to the mean. This bound is proven to be tight; no other moving phantom mechanism can perform better.
  • Overfunding Cap: It limits overfunding to no more than $1/4$ (for an even number of voters $n$).
  • Solving the 3-Project Case: For instances with three projects, the Ladder mechanism achieves an $\ell_1$ distance to the mean of exactly $2/3$, matching known lower bounds and simplifying previous complex proofs.
  • Scaling to More Projects: The paper provides the first non-trivial fairness guarantees for instances with 4, 5, and 6 projects, where previous literature offered only trivial bounds.

Conclusion and Future Directions

The Ladder mechanism represents a significant step forward in designing strategyproof and fair budget aggregation tools. While the results are optimal within the class of moving phantom mechanisms, future work may explore whether other types of anonymous and neutral strategyproof mechanisms can provide even tighter fairness guarantees. Additionally, the current analysis assumes voters have $\ell_1$ disutilities; exploring different utility models, such as squared error, remains an open area for research.

Summary updated

BibTeX
@inproceedings{freeman2024project,
  author = {Rupert Freeman and Ulrike Schmidt-Kraepelin},
  title = {{Project-Fair and Truthful Mechanisms for Budget Aggregation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28828},
}
Figure