Maxmin Participatory Budgeting

Gogulapati Sreedurga, Mayank Ratan Bhardwaj, Yadati NarahariIJCAI 2022 · DOI

TL;DR

This paper introduces and analyzes "Maxmin Participatory Budgeting" (MPB), a novel egalitarian voting rule for allocating a budget to indivisible projects. They demonstrate MPB's computational hardness but also identify tractable cases and propose an LP-rounding algorithm with empirical success on real-world data.

What Problem Does This Paper Address?

Participatory Budgeting (PB) is a democratic process where citizens decide how to allocate a public budget among various proposed projects. A key challenge in PB is ensuring fairness, particularly for indivisible projects (projects that are either fully funded or not at all). While egalitarian objectives (aiming for fairness across all voters) are important, they have been under-explored in the context of indivisible PB. This paper fills this gap by systematically studying the "maxmin" egalitarian objective, which aims to maximize the minimum utility received by any voter, for indivisible PB.

Methods

The paper tackles MPB from two main angles: computational and axiomatic.

Computational: * NP-Hardness: They prove that the decision version of MPB is strongly NP-hard, meaning it's computationally difficult to find an optimal solution in general. * Tractable Cases: They identify specific scenarios where MPB becomes computationally tractable: * When the number of projects is constant. * When the number of distinct voter preferences (approval votes) is constant. * When the "scalable limit" (a measure related to the greatest common divisor of project costs and budget) is constant. * Algorithms: * A pseudo-polynomial time dynamic programming algorithm is proposed for the case of a constant number of distinct votes. * An LP-rounding algorithm called ORDERED-RELAX is introduced, which provides additive approximation guarantees for certain restricted instance spaces and empirically performs very well. * Bounds: They establish an upper bound on the approximation ratio achievable by exhaustive and strategy-proof PB algorithms, showing that these desirable properties can significantly degrade performance for MPB.

Axiomatic: * Generalization of Axioms: They extend existing axioms from PB literature to rules that can output multiple feasible project sets. * New Axiom: Maximal Coverage: They introduce a new axiom, "maximal coverage," designed to capture the fairness notion of diversity by ensuring that redundant projects are funded only when no more voters can be covered otherwise. * MPB Properties: They prove that MPB satisfies splitting monotonicity, merging monotonicity, weak exhaustiveness, and the newly proposed maximal coverage axiom. They also show that MPB does not satisfy discount monotonicity, limit monotonicity, strong exhaustiveness, or the narrow-top criterion.

Datasets

The paper mentions using real-world PB datasets for empirical evaluation. Specific datasets are referenced via a GitHub repository: https://github.com/Participatory-Budgeting/maxmin_2022. The paper also references publicly available PB election datasets from Boston, New York District 8, and Seattle District 1 (2019) for their "scalable limit" parameter.

Key Insights and Ideas

  • Egalitarianism in Indivisible PB is Hard: The core insight is that while egalitarianism is desirable, achieving it for indivisible projects is computationally challenging (NP-hard).
  • Parameterization is Key: The paper highlights that MPB can be solved efficiently if certain parameters (number of projects, number of distinct votes, scalable limit) are small. This is a common theme in computational social choice, where theoretical hardness can be overcome by exploiting structural properties of instances.
  • Maximal Coverage as a Novel Fairness Notion: The introduction of "maximal coverage" is a significant contribution, offering a new axiomatic way to think about diversity in resource allocation problems, going beyond simple representation.
  • Empirical Success Despite Theoretical Hardness: The fact that their proposed algorithm (ORDERED-RELAX) empirically finds optimal solutions on real-world datasets, despite the theoretical NP-hardness, suggests that typical real-world PB instances might not exhibit the worst-case complexity.
  • Trade-offs with Strategy-Proofness: The paper demonstrates that requiring strategy-proofness (where voters cannot benefit from lying about their preferences) in conjunction with exhaustiveness can lead to poor approximation guarantees for the maxmin objective.

Key Results

  • MPB is strongly NP-hard.
  • MPB is weakly NP-hard when the number of distinct votes is constant.
  • MPB can be solved in polynomial time when the number of projects is constant.
  • MPB can be solved in pseudo-polynomial time when the number of distinct votes is constant.
  • MPB can be solved in polynomial time when both the number of distinct votes and the scalable limit are constant.
  • The ORDERED-RELAX algorithm provides additive approximation guarantees for MPB on restricted instance spaces and empirically finds exact optimal solutions on real-world PB datasets.
  • No exhaustive strategy-proof algorithm can achieve a better approximation guarantee than 3/2 for MPB.
  • MPB satisfies splitting monotonicity, merging monotonicity, weak exhaustiveness, and maximal coverage.
  • MPB does not satisfy discount monotonicity, limit monotonicity, strong exhaustiveness, or narrow-top criterion.

Limitations and Future Work

Limitations: * The theoretical approximation guarantees of the ORDERED-RELAX algorithm are limited to specific restricted spaces of instances. * The paper acknowledges that the maxmin objective can be sensitive to outlier voters, though it argues this is often mitigated in practice by voter partitioning. * The axiom of "maximal coverage" is introduced, but its full implications and comparisons with other fairness notions in PB are left for future work.

Future Work: * Developing axiomatic characterizations of MPB. * Studying other egalitarian objectives (e.g., leximin). * Establishing connections between maximal coverage and existing axioms in the literature. * Further exploring the practical implications of the identified tractable cases and parameters.

Summary updated

BibTeX
@inproceedings{sreedurga2022maxmin,
  author = {Gogulapati Sreedurga and Mayank Ratan Bhardwaj and Yadati Narahari},
  title = {{Maxmin Participatory Budgeting}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/70},
}
Figure