In parliamentary elections, parties compete for a limited, typically fixed number of seats. Most parliaments are assembled using apportionment methods that distribute the seats based on the parties' vote counts. Common apportionment methods include divisor sequence methods (like D'Hondt or Sainte-Laguë), the largest-remainder method, and first-past-the-post. In many countries, an electoral threshold is implemented to prevent very small parties from entering the parliament. Further, several countries have apportionment systems that incorporate multiple districts. We study how computationally hard it is to change the election outcome (i.e., to increase or limit the influence of a distinguished party) by convincing a limited number of voters to change their vote. We refer to these bribery-style attacks as \emph{strategic campaigns} and study the corresponding problems in terms of their computational (both classical and parameterized) complexity. We also run extensive experiments on real-world election data and study the effectiveness of optimal campaigns, in particular as opposed to using heuristic bribing strategies and with respect to the influence of the threshold and the influence of the number of districts. For apportionment elections with threshold, finally, we propose -- as an alternative to the standard top-choice mode -- the second-chance mode where voters of parties below the threshold receive a second chance to vote for another party, and we establish computational complexity results also in this setting.

Weighted voting games are a popular class of coalitional games that are widely used to model real-life situations of decision-making. They can be applied, for instance, to analyze legislative processes in parliaments or voting in corporate structures. Various ways of tampering with these games have been studied, among them merging or splitting players, fiddling with the quota, and controlling weighted voting games by adding or deleting players. While the complexity of control by adding players to such games so as to change or maintain a given player’s power has been recently settled, the complexity of control by deleting players from such games (with the same goals) remained open. We show that when the players’ power is measured by the probabilistic Penrose–Banzhaf index, some of these problems are complete for NPPP—the class of problems solvable by NP machines equipped with a PP (“probabilistic polynomial time”) oracle. Our results optimally improve the currently known lower bounds of hardness for much smaller complexity classes, thus providing protection against SAT-solving techniques in practical applications.

Apportionment methods allocate a fixed number of seats in a parliament to parties based on their vote counts. In many countries, parliamentary elections are organized by first holding separate elections in several districts and then putting the single results together. We call such elections multidistrict apportionment elections. Moreover, many countries have an additional general electoral threshold, i.e., a minimum number of votes a party must receive to win any seats in a parliament. For such methods, we study the complexity of bribery problems where an external agent seeks to increase the number of seats for a distinguished party by bribing voters within a given budget. Specifically, we investigate how adding either a general electoral threshold, or district limits for the budget, or both influences the complexity of bribery. District limits—which the external agent must adhere to while still respecting the overall budget—denote a maximum budget for each district, each to be spent for changing the votes only in that district. We show that adding a general electoral threshold, with or without district limits, makes the problems NP-complete for the largest-remainder method and all divisor sequence methods (including the prominent D’Hondt and Sainte-Laguë apportionment methods). We also study parameterized complexity and domain restrictions of these problems.

We survey the notion of control in various areas of computational social choice (COMSOC) such as voting, fair allocation, cooperative game theory, matching under preferences, and group identification. In all these scenarios, control can be exerted, for instance, by adding or deleting agents with the goal of influencing the outcome. We conclude by briefly covering control in some other COMSOC areas including participatory budgeting, judgment aggregation, and opinion diffusion.

Graph-restricted weighted voting games generalize weighted voting games, a well-studied class of succinct simple games, by embedding them into a communication structure: a graph whose vertices are the players some of which are connected by edges. In such games, only sufficiently connected coalitions are taken into consideration for calculating the players' power indices. Focusing on the probabilistic Penrose-Banzhaf index (which Dubey and Shapley proposed in 1979 as an alternative to the normalized Penrose-Banzhaf index) and the Shapley-Shubik index, we study control of these games by an agent who can add edges to or delete edges from the given graph. We determine upper and lower bounds on how much such control actions can change a distinguished player's power and we study the computational complexity of the related problems.

Weighted voting games are a well-known and useful class of succinctly representable simple games that have many real-world applications, e.g., to model collective decision-making in legislative bodies or shareholder voting. Among the structural control types being analyzing, one is control by adding players to weighted voting games, so as to either change or to maintain a player’s power in the sense of the (probabilistic) Penrose–Banzhaf power index or the Shapley–Shubik power index. For the problems related to this control, the best known lower bound is PP-hardness, where PP is “probabilistic polynomial time,” and the best known upper bound is the class NP, i.e., the class NP with a PP oracle. We optimally raise this lower bound by showing NPPP-hardness of all these problems for the Penrose–Banzhaf and the Shapley–Shubik indices, thus establishing completeness for them in that class. Our proof technique may turn out to be useful for solving other open problems related to weighted voting games with such a complexity gap as well.

Graph-restricted weighted voting games generalize weighted voting games, a well-studied class of succinct simple games, by embedding them into a communication structure: a graph whose vertices are the players some of which are connected by edges. In such games, only connected coalitions are taken into consideration for calculating the players’ power indices. We focus on the probabilistic Penrose–Banzhaf index [5] and the Shapley–Shubik index [18] and study the computational complexity of manipulating these games by an external agent who can add edges to or delete edges from the graph. For the problems modeling such scenarios, we raise some of the lower bounds obtained by Kaczmarek and Rothe [9] from NP- or DP-hardness to PP-hardness, where PP is probabilistic polynomial time. We also solve one of their open problems by showing that it is a coNP-hard problem to maintain the Shapley–Shubik index of a given player in a graph-restricted weighted voting game when edges are deleted.