Fairness in Long-Term Participatory Budgeting

Martin Lackner, Jan Maly, Simon ReyIJCAI 2021 · DOI

TL;DR

This paper introduces "perpetual participatory budgeting" (PPB), a framework for modeling multi-year citizen budgeting processes. It proposes and analyzes three fairness criteria—equal welfare, Gini-optimality, and long-term convergence—demonstrating that long-term planning can achieve fairness unattainable in single-round processes, though computational complexity remains a challenge.

What Problem Does This Paper Address?

Participatory Budgeting (PB) is a democratic process where citizens decide how to allocate public funds. While existing research often treats PB as a one-off event, real-world PB processes are frequently designed to run for multiple years, allowing for adjustments and long-term planning. This temporal aspect is crucial because achieving fairness in a single round might be impossible, but a series of decisions over time could lead to a fairer outcome. This paper bridges this gap by formalizing long-term PB and developing a theory of fairness specifically for these multi-year processes. The core problem is to define and analyze fairness in a dynamic setting where decisions in one year can influence outcomes in subsequent years.

Methods

The authors introduce a formal framework called Perpetual Participatory Budgeting (PPB), which models PB as a sequence of budgeting problems over several rounds (years). They define three main fairness criteria:

  1. Equal-F: This is a strong egalitarian criterion requiring all voter "types" (e.g., demographic groups, districts) to achieve the same level of welfare in each round.
  2. F-Gini-optimality: This criterion uses the Gini coefficient, a measure of inequality, to find solutions that minimize welfare disparities among types. It's a relaxation of Equal-F, aiming for the "least unequal" distribution of welfare.
  3. Convergence to Equal-F: This criterion focuses on long-term fairness, requiring that welfare levels for different types become asymptotically equal over an infinite horizon.

To analyze these criteria, they define three welfare measures:

  • Satisfaction: Based on the cost of approved projects.
  • Relative Satisfaction: Satisfaction normalized by a voter's maximum possible satisfaction.
  • Share: The amount of budget allocated to a type, aiming for proportionality to the type's size.

They then analyze the computational complexity of verifying these fairness criteria and explore conditions under which they can be guaranteed, particularly for two types.

Datasets

Not discussed in the paper. The paper uses synthetic examples to illustrate its concepts and theorems.

Key Insights and Ideas

  • Long-term perspective unlocks new fairness possibilities: Fairness that is impossible in a single round can become achievable when decisions are made sequentially over multiple years. This is a fundamental shift from prior PB research.
  • Different fairness notions capture distinct goals: The paper distinguishes between immediate equality (Equal-F), minimizing inequality (Gini-optimality), and asymptotic fairness (Convergence to Equal-F), showing that each has different properties and guarantees.
  • Welfare measures matter: The choice of how to measure "welfare" (satisfaction, relative satisfaction, share) significantly impacts which fairness criteria can be met and under what conditions.
  • Two types are often "easy": Many fairness guarantees, especially for convergence, are achievable for two types but become impossible or much harder to guarantee for three or more types. This highlights a common pattern in social choice and fair division problems.
  • Computational complexity is a significant hurdle: While long-term planning offers theoretical fairness gains, verifying these properties can be computationally hard (NP-complete or co-NP-complete), suggesting practical challenges in implementing these fair systems.

Key Results

  • Equal-F is rarely achievable: For all defined welfare measures, achieving perfect equal welfare in every round is generally impossible, even for simple cases. Checking for its existence is NP-complete.
  • Gini-optimality is computationally challenging: Optimizing for Gini-optimality (minimizing inequality) is co-NP-complete, even in single-round scenarios.
  • Convergence to equal-satisfaction is possible for two types: Under mild conditions (bounded budgets, non-empty ballots), a solution that converges to equal satisfaction can always be found for two types. This guarantee breaks down for three or more types.
  • Convergence to equal-relative satisfaction is possible for two types: This is a more general result than for equal-satisfaction, holding for any number of agents within two types, provided ballots are "knapsack ballots" (feasible subsets of approved projects).
  • Convergence to equal-share is difficult: Similar to equal-satisfaction, achieving equal shares in the long run is generally not guaranteed, even for two types, due to inherent differences in how resources might be distributed.

Limitations and Future Work

  • Generalization to more than two types: The paper highlights that many positive results (especially for convergence) are limited to two types. Extending these guarantees to three or more types remains an important open question.
  • Computational tractability: The NP-completeness results for checking fairness criteria suggest that finding fair solutions in practice might require approximation algorithms or heuristics.
  • Real-world procedures: The paper focuses on theoretical properties. Future work could explore actual PB procedures that naturally lead to fair outcomes or approximate them.
  • Price of fairness: Investigating how much overall welfare or efficiency is sacrificed to achieve fairness is a key direction.
  • Connection to fair division: Exploring how concepts from fair division (like envy-freeness) can be adapted to the PB context is suggested.
  • Empirical validation: Analyzing real-world long-term PB data to quantify the gains of a temporal perspective is proposed.

Summary updated

BibTeX
@inproceedings{lackner2021fairness,
  author = {Martin Lackner and Jan Maly and Simon Rey},
  title = {{Fairness in Long-Term Participatory Budgeting}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/42},
}
Figure