The complexity of electoral campaign management by issue selection

计算社会选择是理论计算机科学、人工智能和集体选择理论的交叉研究领域。计算社会选择中的一个突出主题是改变选举结果的复杂性。现有的研究从几个角度考虑了这个问题，例如选民错误地报告了他们的偏好(操纵)，选举当局改变了哪些选民和候选人可以参加选举(控制)，或者外部政党付钱让选民改变他们的偏好(贿赂)。然而，在实践中，改变选举结果的主要方法之一是将选民的注意力集中在特定的“热门话题”上，例如堕胎、同性婚姻、参与贸易和经济联盟或外交政策问题。这种形式的竞选管理，及其算法的复杂性，在文献中相对较少受到关注，本项目的目的是填补这一空白。我们打算将政治问题的空间建模为一个高维度的空间，选民和候选人占据了这个空间中的点。有一组默认的“重要”问题，选民对候选人的意见取决于他们与候选人之间的距离，在与这些问题相对应的子空间中(潜在地，不同的维度被赋予不同的权重)。作为第一步，我们将假设选民和候选人的立场是固定的，但竞选经理的目标是让特定的候选人赢得选举(或者，在多赢家选举的情况下，成为选定的候选人之一)，可以通过投资资金来改变一系列“重要”问题，以增加或减少每个问题的突出程度。初步工作表明，这个问题在计算上是困难的(Lu等人，AAMAS‘19，Estornell等人，UAI’20)，因此将从逼近算法和固定参数可处理性的角度对其进行探讨。随后，我们将扩展我们的模型，以允许竞选经理的首选候选人在某些或所有问题上改变立场的可能性，可能是在距离其原始值一定的时间间隔内。另一个重要的延期将是允许选民立场的不确定性。然后我们将进入一个完全博弈论的环境，其中两个或更多的竞选经理代表他们的候选人参与竞选活动，目标是分析这样的系统中的均衡行为。在方法论上，本项目将使用理论计算机科学的工具箱，重点关注NP-硬度证明、近似算法和固定参数(In)可处理性结果，将它们与模拟和对真实选举数据的分析相结合。目前，我们预计这个项目不会有任何行业合作伙伴。该项目属于EPSRC数字经济主题，特别是公平数字社会主题，因为它涉及分布式信息环境中的集体决策问题。

Computational social choice is a research area at the intersection of theoretical computer science, artificial intelligence and collective choice theory. One of the prominent topics in computational social choice is the complexity of changing the outcome of an election. Existing research considers several perspectives on this problem, such as voters misreporting their preferences (manipulation), the election authorities changing which voters and candidates can participate in the election (control), or an external party paying voters to change their preferences (bribery). However, in practice, one of the primary methods of changing the election outcome is to focus the voters' attention on a specific "hot topic", such as e.g., abortion, gay marriage, participation in trade and economic unions, or foreign policy issues. This form of campaign management, and its algorithmic complexity, has received relatively little attention in the literature, and the purpose of this project is to fill this gap. We intend to model the space of political issues as a high-dimensional space, with voters and candidates occupying points in that space. There is a default set of "important" issues, and the voters' opinions over the candidates depend on their distance to them, in the subspace that corresponds to these issues (potentially, with different dimensions being assigned different weights). As a first step, we will assume that voters' and candidates' positions are fixed, but the campaign manager, whose goal is to make a specific candidate win the election (or, in case of multiwinner elections, be among the selected candidates), can change the set of "important" issues by investing funds so as to increase or decrease the prominence of each issue. Preliminary work shows that this problem is computationally hard (Lu et al, AAMAS'19, Estornell et al., UAI'20), so will explore it from the perspective of approximation algorithms and fixed-parameter tractability. Subsequently, we will extend our model to allow for the possibility that the campaign manager's preferred candidate can change their position on some or all issues, possibly within a certain interval from its original value. Another important extension would be to allow for uncertainty with regard to the voters' positions. We will then proceed to a fully game-theoretic setting, where two or more campaign managers are participating in the electoral campaign on behalf of their candidates, and the goal is to analyze the equilibrium behaviour in such systems.Methodologically, this project will use the toolbox of theoretical computer science, with a focus on NP-hardness proofs, approximation algorithms and fixed-parameter (in)tractability results, integrating them with simulation and the analysis of real-life electoral data. At the moment, we do not envision any industry partners for this project.The project falls within the EPSRC Digital Economy theme, and specifically the Equitable Digital Society theme, as it deals with issues of collective decision-making in a distributed information environment.