Participatory Budgeting with Project Interactions

Pallavi Jain, Krzysztof Sornat, Nimrod TalmonIJCAI 2020 · DOI

TL;DR

This paper introduces a novel framework for participatory budgeting (PB) that accounts for interactions between projects, such as substitution and complementarity. They demonstrate that while this problem is generally computationally hard, efficient algorithms exist for specific, practically relevant cases, offering a path to more realistic PB systems.

What Problem Does This Paper Address?

Participatory budgeting (PB) is a democratic process where citizens decide how to allocate a portion of public funds by voting on projects. Existing PB systems typically treat projects independently, ignoring how they might influence each other. For example, funding two similar projects might be redundant (substitution), while funding one project might make another more valuable or even necessary (complementarity). This paper addresses the critical gap of modeling and computationally handling these project interactions to improve the quality and efficiency of PB outcomes.

Methods

The authors augment the standard PB model by introducing an "interaction structure," which is a partition of projects into groups that are assumed to have interactions. They then define a utilitarian utility function for voters that incorporates these interactions using a parameterized function f. This function quantifies the utility a voter derives from a certain number of their approved projects being funded within each interaction group.

The core of their work involves studying the computational complexity of finding project bundles that maximize total voter utility under these interaction structures. They identify cases where the problem is tractable:

  • Polynomial-time solvable: When the interaction structure is trivial (each project in its own group) or when the interaction function is linear.
  • Fixed-Parameter Tractable (FPT): They develop algorithms that are efficient when certain parameters are small, specifically:
  • s: the maximum size of a project group in the interaction structure.
  • m - |Z|: the number of projects minus the number of interaction groups.
  • n: the number of voters, for specific types of interaction functions (eventual-constant and concave).
  • Polynomial-time solvable under restricted domains: They show efficient solutions for specific profile structures like r-DISTRICT (where voters only approve projects in their district) and PARTITION (where voters approve all projects within a district).

Datasets

Not discussed in the paper. The paper focuses on theoretical modeling and algorithmic development rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Project interactions are crucial: Ignoring substitution and complementarity leads to suboptimal allocation of public funds.
  • General intractability: Even with simple interaction structures and functions, the problem of maximizing total utility becomes NP-complete and computationally hard.
  • Parameterization is key: The problem's complexity is highly dependent on specific input parameters. Identifying and exploiting small parameters (like the number of voters or the size of interaction groups) allows for efficient algorithms.
  • Specialized domains offer tractability: Real-world constraints on voter preferences (like districts or party lines) can simplify the problem significantly, making it computationally feasible.

Key Results

  • The general problem of maximizing voter utility with project interactions (MAX-f-PB) is NP-complete and W[1]-hard with respect to the budget limit.
  • Efficient polynomial-time algorithms exist for MAX-f-PB when there are no interactions (|Z| = m) or when the interaction function is linear.
  • Fixed-parameter tractable algorithms are provided for MAX-f-PB parameterized by s (max group size), m - |Z| (number of projects minus number of groups), and n (number of voters) under certain conditions.
  • Polynomial-time algorithms are presented for MAX-f-PB under the r-DISTRICT and PARTITION profile restrictions.

Limitations and Future Work

The authors acknowledge that their model captures only a specific type of project interaction (substitution and complementarity within predefined groups) and does not address how to determine these interaction structures themselves. Future work could explore:

  • Developing methods for automatically identifying project interactions.
  • Investigating other utility functions beyond the utilitarian model.
  • Exploring non-utilitarian approaches to aggregation.
  • Considering alternative ways to incorporate project interactions into PB.
  • Further research into approximation algorithms for the general problem.

Summary updated

BibTeX
@inproceedings{jain2020participatory,
  author = {Pallavi Jain and Krzysztof Sornat and Nimrod Talmon},
  title = {{Participatory Budgeting with Project Interactions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/54},
}
Figure