Time-Constrained Participatory Budgeting Under Uncertain Project Costs

Dorothea Baumeister, Linus Boes, Christian LaußmannIJCAI 2022 · DOI

TL;DR

This paper tackles the challenge of allocating limited budgets to community projects when their costs are uncertain, a common real-world problem. They introduce a framework for "time-constrained participatory budgeting under uncertain project costs," exploring the trade-offs between desirable properties like punctuality, risk-aversion, and exhaustiveness, and proving that no single algorithm can achieve all of them perfectly.

What Problem Does This Paper Address?

Participatory budgeting is a process where citizens help decide how public funds are spent. Typically, this involves selecting projects from a list, subject to budget and time constraints. However, in reality, the exact cost of many projects isn't known until they're completed. This uncertainty poses a significant challenge: overestimating costs might lead to missed opportunities, while underestimating could result in projects failing or requiring additional funds. This paper addresses this by developing a framework that accounts for uncertain project costs within a time-constrained participatory budgeting setting. They aim to find methods that balance voter satisfaction with these real-world uncertainties, considering that projects might need to be undertaken sequentially to manage risk, but this can drastically increase overall completion time.

Methods

The authors build upon existing frameworks for approval-based participatory budgeting, extending them to handle uncertain project costs. They introduce a formal model that includes cost ranges (minimum, maximum, and probabilistic cost distributions), project durations, budget limits, and time limits. A key aspect of their work is the study of desirable properties for online budgeting methods (algorithms that make decisions incrementally without full future knowledge). These properties include:

  • Punctuality (PU): Projects must finish within the overall time limit.
  • α-Risk-assessment (α-RA): The probability of exceeding the budget limit should be low (at most α).
  • K-Limitation (K-LI): The budget limit should not be exceeded by more than a factor of k.
  • Exhaustiveness (EX): All projects that could be safely implemented should be.

They then investigate which combinations of these properties are compatible and which are inherently contradictory, leading to impossibility results. They also propose and analyze algorithms that aim to achieve a good balance of these properties, often sacrificing one for the sake of others, and evaluate their performance using competitive ratios. Additionally, they explore proportionality axioms (ensuring fair representation of voters) in the context of uncertain costs, proposing "ex ante" (considering maximum costs) and "ex post" (considering actual costs of implemented projects) relaxations.

Datasets

Not discussed in the paper. The authors mention that they tested their algorithms using real data from the Participatory Budgeting Library, modified to fit their uncertainty scenario, but do not provide specific details about the dataset itself.

Key Insights and Ideas

  • No Perfect Algorithm Exists: The most significant insight is that it's impossible to design an online budgeting algorithm that simultaneously satisfies all desirable properties (like punctuality, low risk, and exhaustiveness) for all scenarios. This highlights the inherent trade-offs in real-world decision-making under uncertainty.
  • Sequential vs. Simultaneous Decisions: Implementing projects sequentially can mitigate cost risk but drastically increases the time to complete a set of projects. Conversely, simultaneous implementation is faster but riskier.
  • The Importance of Cost Ranges: Simply having a single estimated cost is insufficient. The paper emphasizes the need to consider cost ranges and probabilistic distributions to make informed decisions.
  • Proportionality Under Uncertainty is Tricky: Adapting fairness concepts like proportionality to uncertain costs is complex. The paper shows that some standard proportionality axioms don't directly translate and require careful redefinition (ex ante vs. ex post).
  • Trade-offs are Inevitable: The paper provides concrete theorems demonstrating these trade-offs. For instance, achieving low risk (α-RA) and punctuality (PU) makes exhaustiveness (EX) impossible.

Key Results

  • Impossibility Theorems: The paper proves that for any fixed α < 1, no online budgeting method can simultaneously satisfy α-risk-assessment, punctuality, and exhaustiveness. Similar impossibility results are shown for K-limitation.
  • Competitive Ratios: The authors establish bounds on the competitive ratios (how close an online algorithm's solution is to the optimal offline solution) for algorithms satisfying certain properties. For example, algorithms satisfying α-risk-assessment have a competitive ratio of at least Ω(m), where m is the number of projects.
  • Algorithm Performance: They propose "Best Effort Exhaustiveness" (BEE) and "Best Effort Punctuality" (BEP) algorithms that trade off properties. BEE prioritizes punctuality, risk-assessment, and limitation, while BEP prioritizes exhaustiveness. Experiments suggest that BEE performs well when time limits are generous.
  • Proportionality Axioms: They introduce ex ante and ex post relaxations for proportionality axioms like BPJR-L and EJR. They show that EJR implies its ex post and ex ante versions, but BPJR-L does not. They also prove that no online budgeting method can satisfy α-risk-assessment and ex post BPJR-L simultaneously.

Limitations and Future Work

  • Limited Resources: The current model only considers uncertainty in one resource (cost). Future work could explore uncertainty in multiple resources, such as project durations, and their interdependencies.
  • Sequential Decision Making: While the paper models sequential project implementation, more complex dependencies between projects (e.g., one project enabling another) are not considered.
  • Satisfaction Functions: The current satisfaction function is additive and based on voter approval. Future work could explore more nuanced satisfaction functions that might be affected by the actual cost of a project or its completion time.
  • Real-World Data: While real data was used for testing, a more extensive empirical evaluation with diverse datasets would be beneficial.
  • Extending Models: The authors suggest extending the model to incorporate resource constraints like machines or workers, which would add another layer of complexity to project scheduling. They also propose investigating the impact of uncertainty in project durations instead of costs.

Summary updated

BibTeX
@inproceedings{baumeister2022time,
  author = {Dorothea Baumeister and Linus Boes and Christian Laußmann},
  title = {{Time-Constrained Participatory Budgeting Under Uncertain Project Costs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/11},
}
Figure