Submodular Participatory Budgeting
This work addresses the limitation of additive utility assumptions in participatory budgeting, which is important for public resource allocation, but it is incremental as it extends existing studies with a submodular model.
The paper tackles the problem of participatory budgeting by proposing a submodular utility model to better reflect real-world scenarios where utility does not scale additively, and it introduces preference elicitation methods that achieve improved distortion bounds, such as a better distortion than state-of-the-art for additive cases.
Participatory budgeting refers to the practice of allocating public resources by collecting and aggregating individual preferences. Most existing studies in this field often assume an additive utility function, where each individual holds a private utility for each candidate project, and the total utility of a set of funded projects is simply the sum of the utilities of all projects. We argue that this assumption does not always hold in reality. For example, building two playgrounds in the same neighborhood does not necessarily lead to twice the utility of building a single playground. To address this, we extend the existing study by proposing a submodular participatory budgeting problem, assuming that the utility function of each individual is a monotone and submodular function over funded projects. We propose and examine three preference elicitation methods, including \emph{ranking-by-marginal-values}, \emph{ranking-by-values} and \emph{threshold approval votes}, and analyze their performances in terms of distortion. Notably, if the utility function is addicative, our aggregation rule designed for threshold approval votes achieves a better distortion than the state-of-the-art approach.