Introduction
Participatory budgeting is an approach to allocating budgets to different projects based on users’ preferences. For instance, a local council can propose a list of 10 projects with different costs (such as, a new park or a bike path), announce a budget, elicit the residents’ preferences over the projects, and then select a set of projects to implement to satisfy as many participants as possible while staying within the budget.
The same approach can be extended to settings where one needs to choose among unpopular measures to resolve a pressing issue faced by the community, such as reducing energy consumption to combat climate change, introducing social distancing measures to slow the spread of a virus, or cutting services to deal with a budget deficit. The negative outcomes to individuals produced in these settings are known as ‘chores’ or ‘bads’ as opposed to ‘goods’. The goal of this project is to explore algorithmic challenges associated with allocating budgets for these ‘bads’ or ‘chores’.
Explaining the science
In the context of participatory budgeting for goods (i.e., the standard model), many natural optimisation objectives lead to NP-hard problems, and researchers have explored ways of tackling them via approximation algorithms and multivariate algorithmics. Indeed, even defining what it means for an allocation to be fair is a challenging issue which depends on the preference format and the application at hand. Some novel fairness criteria, such as extended justified representation or proportionality for solid coalitions have been put forward in recent work; however, it remains unclear if they are suitable for chores/bads. Overall, the setting of participatory budgeting with bads remains largely unexplored. In a related setting of fair division, it is well-known that concepts and methods that work well for goods do not always extend straightforwardly to chores.
Project aims
In this project, we aim to formulate new conditions, capturing both fairness and welfare objectives, for the setting of selecting chores, or bads. We will verify whether existing algorithms for goods can be extended to this setting, and whether they still behave in a desirable manner when used for bads rather than goods. We will also develop new computationally efficient and fair allocation procedures tailored to our model. Towards the end of the project, we plan to explore the allocation of both goods and bads, or where the projects to be selected may be seen as goods by some agents and bads by other agents (e.g., converting a parking space to an outdoor café, or closing a nightclub).
Applications
We hope to engage local authorities and get them to incorporate our ideas in their decision-making. We have already explored collaboration opportunities with some potential stakeholders.
Organisers
Martin Bullinger
Postdoctoral researcher, University of Oxford
Ruth Drysdale
Programme Manager, Artificial Intelligence (AI)Researchers and collaborators
Sonja Kraiczy
PhD student, University of Oxford