The complexity of electoral campaign management by issue selection

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.