Driving Behaviour in Multi-Winner Elections

The long-term goal of this project is to enable groups of strategic users (either human or artificial) to reach high quality, mutually agreed decisions when selecting multiple alternatives. 

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. For example, in 2022, the city of Paris will allocate over 75 million Euros for urban development by means of PB. PB can capture a variety of applications other than urban planning, such as 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 PB have received a lot of attention from the COMSOC community, with researchers identifying general principles for selecting good solutions (axioms) and proposing (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. Neither assumption is fully realistic. Voters may have a hard time making up their minds concerning complex proposals (such as 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 this project is to develop a systematic understanding of strategic behaviour in multi-winner voting and PB, with a focus on the associated algorithmic challenges. Specifically, it will 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. It will also examine the incentives associated with agents delegating their decisions to more knowledgeable agents. Broadly, the project aims 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. Working with project partners, these results will be applied in practical decision-making scenarios in the contexts of urban living and distributed autonomous organisations.