Proportional Participatory Budgeting with Additive Utilities

Version v2 -October 2022 * We study voting rules for participatory budgeting, where a group of voters collectively decides which projects should be funded using a common budget. We allow the projects to have arbitrary costs, and the voters to have arbitrary additive valuations over the projects. We formulate an axiom (Extended Justified Representation, EJR) that guarantees proportional representation to groups of voters with common interests. We propose a simple and attractive voting rule called the Method of Equal Shares that satisfies this axiom for arbitrary costs and approval utilities, and that satisfies the axiom up to one project for arbitrary additive valuations. This method can be computed in polynomial time. In contrast, we show that the standard method for achieving proportionality in committee elections, Proportional Approval Voting (PAV), cannot be extended to work with arbitrary costs. Finally, we introduce a strengthened axiom (Full Justified Representation, FJR) and show that it is also satisfiable, though by a computationally more expensive and less natural voting rule. * In arXiv version v2, we have updated the paper to follow the version at NeurIPS 2021 [Peters et al., 2021b], though this version has significant additional improvements. Changes: The paper title now refers to "additive" rather than to "cardinal" valuations. We now call our voting rule Equal Shares instead of the preliminary name "Rule X". We have added pseudocode and examples. We now use a slightly stronger definition of EJR up to one project, see Footnote 8. We have clarified the description of Equal Shares for ordinal valuations. We have added a remark that GCR satisfies FJR even for general monotone valuations. In addition, the presentation has been clarified throughout.