Driving Behaviour in Multi-Winner Elections (BMW)

现代社会往往需要根据多个利益攸关方的意愿和偏好做出选择：这种选择范围从当地社区的交通政策到加入或退出主要的政治或经济联盟。许多商业和非营利组织都面临着类似的挑战：例如，招聘决定、确定战略优先事项和预算分配。同样，在共同环境中相互作用的独立人工代理人可能需要商定一项联合行动计划或资源分配。从历史上看，这种情景是使用社会选择的方法来分析的，社会选择是一门结合了数学、经济学和政治学工具的学科。最近，很明显，人们还需要考虑所提出的解决方案的算法方面，这导致了计算社会选择(COMSOC)领域的出现。虽然许多早期的COMSOC研究考虑的是目标是根据选民的偏好选出一个获胜的备选方案的背景，但最近重点已经转移到多赢家投票环境，其中一个人的目标是选择k个备选方案(委员会)。这种模式的应用包括选举政治领导人、将工作或人才竞赛的申请者列入候选名单、创建投资组合或根据其他用户的经验确定要推荐给在线媒体用户的项目等。更一般的设置是参与式预算(PB)--收集选民的偏好，从选项列表中选择要实施的项目子集，其中每个项目都有成本，总成本不应超过给定的预算。PB于1989年在巴西发起，被设想为当地居民在其社区分配公共资金的一种方式。在接下来的几十年里，它迅速蔓延到世界各地：例如，在2022年，巴黎将通过PB的方式拨出超过7500万欧元用于城市发展。PB可以捕获城市规划以外的各种应用，例如，决定一组实现特定目标的措施(如减少碳排放或控制病毒传播)，或在开源软件社区中分配程序员的时间。多赢家投票和参与式预算都受到了COMSOC社区的大量关注，研究人员确定了选择好的解决方案(公理)和提出(计算效率高的)投票规则的一般原则，以满足这些公理(或证明不可能性/硬性结果)。然而，现有的许多工作都假设选民完全了解他们的偏好，并如实报告。这两种假设都不完全现实：选民可能很难就复杂的提案做出决定(例如，评估不同能源的风险和好处，或者实施教育改革)，如果他们可以从中受益，他们可能会错误地报告自己的偏好。我们建议的主要重点是系统地理解多赢家投票和参与式预算编制中的战略行为，重点放在相关的算法挑战上。具体地说，我们将评估战略投票稳定结果的质量，确定计算它们的复杂性，并分析迭代投票的动态。我们还将研究与代理商将他们的决定委托给更有见识的代理商相关的激励措施。总的来说，我们的目标是确定集体决策的工具，这些工具可以推动投票行为达到理想的结果，并在现实环境中表现良好--即在存在不确定性和有限理性的情况下。然后，我们将与我们的项目合作伙伴合作，将这些结果应用到城市生活和分布式自治组织的实际决策场景中。

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 oreconomic 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 socialchoice-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 leadto 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 oftheir 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 benefitsof 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.