TL;DR
This paper introduces a novel end-to-end model for participatory budgeting (PB) that accounts for both project proposal/shortlisting and final budget allocation stages. It proposes and analyzes new shortlisting rules and investigates strategic behavior incentives during the proposal stage, offering a more comprehensive view of PB processes.
What Problem Does This Paper Address?
Participatory budgeting (PB) is a democratic process where citizens decide how public funds are allocated. While existing research has largely focused on the final allocation stage (how to choose projects from a given shortlist), this paper addresses a critical gap by modeling the entire PB process. This includes the initial stage where citizens propose projects and a mechanism shortlists them before the final voting. The authors argue that understanding the interplay between these two stages is crucial for a more accurate and insightful analysis of real-world PB. They highlight that the shortlisting stage, often overlooked in formal analysis, presents its own set of challenges and opportunities for strategic behavior.
Methods
The authors develop an "end-to-end" model that formalizes two key stages of PB:
- Shortlisting Stage: Agents propose projects, and a shortlisting rule selects a subset of these proposals. The paper introduces and analyzes several new shortlisting rules, including:
- Nomination Rule: Simply accepts all proposed projects.
- k-Equal Representation Shortlisting Rule: Aims to ensure fair representation by maximizing the minimum number of selected projects per agent, with a budget constraint.
- k-Median Shortlisting Rules: Clusters projects based on a given distance metric and selects representative projects from each cluster.
- Allocation Stage: Agents vote on the shortlisted projects to decide which ones get funded. The paper utilizes and defines several standard allocation rules from the literature, such as GREEDCOST, MAXCOST, GREEDCARD, and MAXCARD.
A core methodological contribution is the formalization of agent preferences and strategic behavior. Agents have ideal sets of projects based on their awareness and preferences. The paper then analyzes "first-stage strategy-proofness" (FSSP), investigating whether agents have incentives to misrepresent their proposals in the first stage to achieve a better outcome in the second stage. They define different types of manipulation (pessimistic, optimistic, anticipatory) and corresponding FSSP concepts (restricted and unrestricted).
Datasets
Not discussed in the paper. The paper uses hypothetical examples and theoretical scenarios to illustrate its concepts and prove its theorems.
Key Insights and Ideas
- The Shortlisting Stage Matters for Strategy: Agents' decisions in the first stage (proposing projects) are influenced by how those proposals might affect the final outcome of the second stage. This creates incentives for strategic behavior before the final vote.
- No Single "Best" Shortlisting Rule: The paper identifies multiple objectives for shortlisting (reducing project numbers, ensuring representation, avoiding redundancy) and shows that different rules excel at different objectives.
- Strategic Behavior is Pervasive: The analysis reveals that many shortlisting rules, especially when combined with common allocation rules, are not immune to strategic manipulation in the first stage. Agents can often benefit from strategically withholding or altering their proposals.
- Awareness is Key to Strategy: The degree to which an agent is aware of other agents' proposals and preferences significantly impacts their ability to strategize effectively.
- Trade-offs Between Stages: The paper highlights the inherent trade-offs between the efficiency of the shortlisting stage (e.g., reducing the number of projects) and the fairness or strategic robustness of the overall PB process.
Key Results
- Shortlisting Rules Analysis: The paper formally defines and analyzes the axiomatic properties (non-wastefulness, representation efficiency) of several shortlisting rules. For instance, k-equal representation rules are non-wasteful and representatively efficient for k>=2, while k-median rules are non-wasteful but not representatively efficient.
- Strategy-Proofness Results: A significant portion of the paper is dedicated to proving impossibility results. For example, it's shown that no pair of reasonable shortlisting and determined allocation rules can be first-stage strategy-proof under certain conditions (Theorem 6). Similarly, specific shortlisting rules are shown to be vulnerable to manipulation under various assumptions about agent behavior and preferences (Propositions 8, 9, 10, 11).
- Table of Results: A comprehensive table (Table 1) summarizes the findings on first-stage strategy-proofness for different shortlisting rules under various conditions for allocation rules and completion principles. This table provides a clear overview of which rules are robust to manipulation and under what circumstances.
Limitations and Future Work
- Computational Complexity: The paper notes that some shortlisting rules, like k-median, are computationally intractable (NP-hard), suggesting the need for approximation algorithms.
- Assumptions on Preferences: The model relies on specific assumptions about agent preferences (strict linear orders) and how they derive preferences over budget allocations (completion principles). Future work could explore more general preference structures.
- Information Availability: The analysis of strategy-proofness depends heavily on what information manipulators have access to. Further research could explore more nuanced information structures.
- Refining FSSP Axioms: The authors suggest that the current FSSP axioms could be refined by considering more specific types of strategic behaviors or limitations on manipulator actions.
- End-to-End Rule Design: The paper proposes studying rules that consider both stages simultaneously, rather than composing separate shortlisting and allocation rules, to potentially improve overall fairness and efficiency.
- Loss of Efficiency: The paper mentions that the shortlisting stage can lead to a loss of efficiency, and suggests that concepts like "distortion" could be used to measure this loss.
Summary updated