Anton Baychkov, Markus Brill, Markus Utke
Designing and analyzing voting rules for Participatory Budgeting (PB) elections is an active research area in computational social choice. Many PB voting rules aim to optimize a specific objective. For instance, the ubiquitous Greedy rule attempts to maximize utilitarian welfare, while the Method of Equal Shares (MES) aims to achieve proportional representation. However, it is often desirable to achieve good outcomes on multiple objectives rather than a close-to-perfect outcome for one. Inspired by mixed-member systems for parliamentary elections, we introduce mixed voting rules for PB. These are composed of a sequence of two or more rules that can each spend some fraction of the overall budget in order to add projects to the set selected by earlier rules. We develop a theoretical framework for formulating and analyzing mixed PB voting rules, and explore how existing rules can be adapted to this framework. We particularly focus on MES and its potential to address imbalances in representation created by earlier rules. We propose different ways to adjust MES voter budgets based on how satisfied voters are with previously chosen projects, and examine how well the resulting rules approximate well-known proportionality axioms such as EJR+. In particular, we show that one of these methods improves upon a natural proportionality baseline. We also extend our main positive result to general additive satisfaction functions. We complement our theoretical results with an extensive empirical analysis of real-world PB elections. Our experiments show that mixed rules can achieve favorable trade-offs between utilitarian welfare and proportionality. We identify several refinements that further improve their performance, and apply our framework to PB rules beyond Greedy and MES.