The complexity of electoral campaign management by issue selection

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