Modern societies often need to make choices based on the desires and preferences of multiple stakeholders: such choices range from traffic policies in a local neighbourhood to joining or leaving major political or
economic alliances. Similar challenges are faced by many organisations, both commercial and non-profit: examples include hiring decisions, identifying strategic priorities, and budget allocation. Likewise, independent artificial agents interacting in a common environment may need to agree on a joint plan of action or allocation of resources. Historically, such scenarios were analysed using the methodology of social
choice-a discipline that combines tools of mathematics, economics and political science. More recently, it became clear that one also needs to consider algorithmic aspects of the proposed solutions, which lead
to the emergence of the field of computational social choice (COMSOC).
While much of the early COMSOC research considered the setting where the goal is to elect a single winning alternative based on voters' preferences over the alternatives, more recently the focus has shifted to the multi-winner voting setting, where one aims to select k alternatives (a committee). The applications of this model include electing political leaders, shortlisting applicants for jobs or talent competitions, creating portfolios or identifying items to recommend to a user of online media based on other users' experiences, etc. An even more general setting is that of participatory budgeting (PB)-the task of aggregating the voters' preferences to select a subset of projects to implement from a list of options, where each project has a cost and the total cost should not exceed a given budget. PB was initiated in Brazil in 1989 and was envisioned as a way for local residents to allocate public funds in their neighbourhood. Over the next few decades it quickly spread across the world: e.g., in 2022, the city of Paris will allocate over 75 million euro for urban development by means of PB. PB can capture a variety of applications other than urban planning, such as, e.g., deciding on a set of measures to achieve a particular target (such as reducing carbon emissions or controlling viral transmission), or allocating the programmers' time in an open-source software community.
Both multi-winner voting and participatory budgeting have received a lot of attention from the COMSOC community, with researchers identifying general principles for selecting good solutions (axioms) and pro-
posing (computationally efficient) voting rules that satisfy these axioms (or proving impossibility/hardness results). However, much of the existing work assumes that the voters have a complete knowledge of
their preferences and report them truthfully. Both assumptions are not fully realistic: voters may have a hard time making up their minds concerning complex proposals (such as, e.g., evaluating risk and benefits
of different energy sources or implementing educational reforms), and they can misreport their preferences if they can benefit from doing so. The primary focus of our proposal is to develop a systematic understanding of strategic behaviour in multi-winner voting and participatory budgeting, with a focus on the associated algorithmic challenges. Specifically, we shall evaluate the quality of stable outcomes of strategic voting and establish the complexity of computing them, as well as analyse the dynamics of iterative voting. We shall also examine the incentives associated with agents delegating their decisions to more knowledgeable agents. Broadly, we aim to identify tools for collective decision-making that can drive voting behaviour to desirable outcomes and perform well in realistic settings-i.e., in the presence of uncertainty and bounded rationality. We will then work with our project partners to apply these results in practical decision-making scenarios in the contexts of urban living and distributed autonomous organisations.
|