How Hard Is It for a Party to Nominate an Election Winner?

1 Introduction

The Computer Science Department of the University of Antarctica has to elect its new chair. Each of the three teams can present exactly one of two candidates: a or a0 for group A(rtificial Intelligence), b or b0 for B(usiness Informatics) and c or c0 for C(omputer Networks). The preferences of the members of the department split into four equal-size groups:

Group 1: b ≻ a ≻ c0 ≻ a0 ≻ b0 ≻ c

Group 3 : a0 ≻ c ≻ a ≻ b ≻ b0 ≻ c0

Group 2: b0 ≻ a ≻ c0 ≻ a0 ≻ c ≻ b

Group 4: c0 ≻ a ≻ c ≻ a0 ≻ b0 ≻ b

meaning that, for instance, group 1 finds b to be the best candidate, a to be the second best, then c0 , and so on. Each team has to decide whom of its two candidates to nominate. The voting rule used is Plurality: The winner is the candidate with the highest number of voters for whom it is most preferred among the running candidates (ties do not occur in this example). As there are two possible candidates for each team, there are eight possibilities, listed below (omitting curly brackets, i.e., abc stands for ¶a↪ b↪ c♦ etc.) with the associated winner:

For instance, if a, b and c run, then groups 1, 2, 3 and 4 vote respectively for b, a, c and a, and a wins. Team A has an easy strategy if it wants someone from the team to become the chair: They should nominate a, who will win against the candidates of B and C irrespective of who they nominate. What

Laurent Gourv`es, J´erˆome Lang, Julien Lesca, J´erˆome Monnot LAMSADE

Universit´e Paris-Dauphine, France tfirstname.lastname@dauphine.fr

about team C? It might well be the case that team A nominates a0 (maybe because the choice is made by the chair and she has a secret incentive for the candidate of her group not to win, or because members of the team vote for choosing their candidate and a majority of them doesn't trust a); therefore, even if they clearly cannot ensure their candidate's victory, they can choose a candidate that at least might win under favorable circumstances: They should nominate c0 , who wins provided that A nominate a0 . Finally, there is not even a hope that the winner comes from team B.

Reasoning about outcomes of elections with uncertainty and/or with strategic behaviour from some agents that are part of the process has received a lot of attention in computational social choice and, more generally, in Artificial Intelligence due to the increasing frequency of common decision making processes allowed by online tools (Doodle TM being one typical example), that take place within societies of agents (e.g., in social networks, or in more classical groups that share a working place or a living place). Being able to predict possible outcomes of such elections is often an important issue, and sometimes needs the resolution of hard combinatorial problems. Previous work has focused on strategic behaviour from the voters (manipulation), from the chair (control), from the candidates (strategic candidacy, cloning), from anyone including outsiders (bribery), as well as computing outcomes of elections under incomplete information. For recent surveys see the works of Conitzer and Walsh [2016] (manipulation), Faliszewski and Rothe [2016] (control and bribery) and Boutilier and Rosenschein [2016] (incomplete information).

Beyond low-stake voting in small-scale communities or social networks, the problem of choosing a candidate to run for a party is also highly relevant in political science, as it arises in most countries using uninominal voting systems (consider, for example, presidential elections where parties nominate their candidates). It is a well-known fact that the decisions made by parties (sometimes made by the party's governing body, sometimes by a popular vote) have a tremendous impact on the final outcome, and that parties don't always make the "right" choice. 1

Exploring the implications of choosing who the runner should be for parties, or more generally for well-defined groups such as in our introductory example, is a highly interesting topic that can be studied from various angles. The task of computing which party can possibly win seems to be among the most obvious problems to study and this is the very topic of this paper. Although this problem is new (as far as we know), related problems have been studied.

1 An example: the designation of Bob Dole as the candidate of the Republican party in the 1996 US presidential election led to a quasi-certainty of victory for Bill Clinton.

Related Work. Ding and Lin [2014] consider a party-list voting system where parties have to choose which of their candidates should run, given voters' preferences over candidates. They define a game-theoretic model for the two-party case, and show that pure Nash equilibria are guaranteed to exist but are hard to compute. Another problem occurring in a (real-life) party-list system is studied by Ricca et al. [2011]: A candidate may run (and be elected) in several regions, and parties have to find a 'giving up' strategy for choosing which candidate must give up in which region, a problem for which the authors give polynomial-time algorithms.

In strategic candidacy games, initiated by Dutta et al. [2001], candidates have preferences over the set of all potential candidates and choose to run or not (while in our model, candidates have neither preferences nor any power to decide to run or not). In candidate control, initiated by Bartholdi et al. [1992], the chair may add or remove candidates, and the problem is to decide whether the chair can act so as to make a particular candidate win. A common point between our work and that on strategic candidacy and candidate control lies in reasoning about who will run for an election. However, the notion of a party, which is central to our work, is absent from the latter two classes of problems. (However, see, e.g., the work of Guo et al. [2015] for an example of a complexity study of an election problem with parties.)

A series of works, initiated by Konczak and Lang [2005], deals with determining the candidates that can possibly or necessarily win in an election where voters' preferences are incompletely known or specified. We also consider, in some sense, possible and necessary winners in incompletely specified elections, but the incompleteness does not lie in the voters' preferences but on the set of running candidates.

Our Results. We focus on the Plurality rule and the following two problems (for the Plurality rule only). In both we are given an election, i.e., a set of candidates split into parties, a collection of voters (each with his or her ranking of the candidates), and a party P . In the POSSIBLE PRESIDENT problem, we ask if it is possible to choose nominees of all the parties so that the nominee of party P wins (i.e., we ask if there are some circumstances where the nominee of P wins). In the NECESSARY PRESIDENT problemwe ask if it is the case that party P has a nominee who wins irrespectively of which candidates other parties nominate.

We obtain the following main results, all for the Plurality rule:

1. The POSSIBLE PRESIDENT problem is NP-complete and the NECESSARY PRESIDENT problem is coNPcomplete (for the case of unrestricted elections).
2. The POSSIBLE PRESIDENT problem remains NPcomplete even if the voters' preferences are single-
3. peaked 2 , and even 1D-Euclidean single-peaked. However, it is in P if the candidates belonging to each given party form a consecutive block on the societal axis.
4. The NECESSARY PRESIDENT problem is polynomialtime solvable for single-peaked elections.

That is, our problems are computationally hard, but as soon as we assume a more natural model (even if still not completely realistic), we obtain polynomial-time algorithms.

2 Preliminaries

An election consists of a set of candidates C = ¶c1↪ ▷ ▷ ▷ ↪ cm♦ and a collection of voters V = (v1↪ ▷ ▷ ▷ ↪ vn). Each voter vi has a preference order ≻i, i.e., a ranking of the candidates from the most to the least desirable one. We refer to the sequence (≻1↪ ▷ ▷ ▷ ↪ ≻n) as a preference profile.

If in a description of a preference order we put some set A of candidates, this means listing them in some arbitrary, but fixed, order. Similarly, putting - A in a preference order means listing the candidates in the reverse of this order.

A voting rule R is a function that given an election E = (C↪ V ) outputs a set W, W ✓ C, of the candidates that tie as election winners. We focus on the Plurality rule, where given an election E = (C↪ V ) the winners are the candidates that are ranked on the first place by the largest number of candidates. We refer to the number of voters in election E that rank some candidate c first as the score of c in E and denote it as scoreE(c).

Note that we assume the nonunique-winner model, that is, if there are several highest-scoring candidates, we consider all of themwinners. In practice, one has to use some tie-breaking mechanism (and its choice may affect the complexity of an election problem [Obraztsova and Elkind, 2011; Obraztsova et al., 2011]) but for the sake of simplicity, we disregard this issue.

3 The Problems

We study the following setting. A society is going to have an election to make some choice (presidential elections are one example that may particularly appeal to one's intuition). There is a set of parties, P = ¶P1↪ ▷ ▷ ▷ ↪ Pt♦, that can nominate candidates for the election. Indeed, we view each party Pi as the set of candidates from which this party can choose its nominee. 3 We assume that each party picks exactly one candidate and submits him or her to the final election (for the Plurality rule, on which we focus, nominating more than one candidate can only reduce the chances that the winner belongs to the party) and that no candidate belongs to more than one party. Finally, we also assume that there is a collection of voters V with preference orders over the whole set of possible candidates, Sti=1 Pi (such data, albeit approximate, is typically available from election polls or from experience).

2 Single-peaked preferences are a natural model of voter behavior for the case where the voters are polarized over a single issue; e.g., the standard political left-right spectrum can be seen as leading to single-peaked preferences.

3 While the term "party" is associated with political elections, in our problem it may mean any group of people capable of nominating a candidate from some predetermined set.

Definition 1. Let R be a voting rule, P = ¶P1↪ ▷ ▷ ▷ ↪ Pt♦ a set of parties, where each party is a set of candidates disjoint from all the other parties, and V a collection of voters, each with a preference order over the candidates from Sti=1 Pi.

1. Party Pw is said to have a possible president if there is a set of candidates C such that: (a) for each i, 1  i  t, C contains exactly one candidate from Pi (the nominee of party Pi), and (b) R(C↪ V ) contains a member of Pw.
2. Party Pw is said to have a necessary president if there is a candidate c of Pw such that for each candidate set C-w that contains one candidate from each party except Pw, R(C-w [ ¶c♦↪ V ) contains c.

Informally put, party Pw has a possible president if there is a choice of nominees for all the parties so that the nominee of Pw wins, and party Pw has a necessary president if it can nominate a candidate who wins irrespectively of whom the other parties nominate.

We are interested in the complexity of determining whether a party has a possible (respectively, a necessary) president. We define the following two problems.

Definition 2. Let R be a voting rule. In the RPOSSIBLE PRESIDENT (respectively, R-NECESSARY PRESIDENT) problem, we are given a set of parties P = ¶P1↪ ▷ ▷ ▷ ↪ Pt♦, a collection of voters V , and an integer w, 1  w  t, and we ask if Pw has a possible (respectively, a necessary) president.

The above two problems present two extreme cases: Testing if a party has a chance of winning an election and testing if the party has a candidate who is certain to win the election. In practice, it might be interesting to study some sort of middle-ground approach (e.g., computing the probability that a given party wins, given some probability for each of the candidates being nominated, somewhat along the lines of the research of Hazon et al. [2012], Betzler et al. [2010], and Wojtas et al. [2012]). Still, our problems can be quite practical. For example, using the POSSIBLE PRESIDENT problem, a party can compute which of its candidates have any chance of winning, and limit the nomination process to only these.

4 Results

We now present our results. We first present a simple, but important, setting where our problems are trivial. Then we move on to studying them for the case of the Plurality rule, both for unrestricted and restricted voter preferences (see discussion below).

4.1 Parties as Clone Sets

If each party forms a clone set in the given election, then our problems turn out to be trivial (the study of clone sets was initiated by Tideman [1987] and Zavist and Tideman [1989]; in the computational social choice literature, it was picked up by Elkind et al. [2011; 2012] and Cornaz et al. [2012; 2013]).

Definition 3. A subset A of candidates from election E = (C↪ V ) is a clone set for this election if every voter in V ranks the candidates from A in a consecutive block (but, possibly, in different order for each of the voters).

We use the following notation. If E = (C↪ V ) is an election and ¶A1↪ ▷ ▷ ▷ ↪At♦ is a partition of C into clone sets for E, then by E(a1 A1↪ ▷ ▷ ▷ ↪ at At) we mean an election E0 = (¶a1↪ ▷ ▷ ▷ ↪ at♦↪ V 0 ), where we obtain V 0 from V by replacing each group of consecutive candidates Ai with a single candidate ai (this process is known as decloning [Elkind et al., 2012]).

Proposition 1. Consider an instance of R-POSSIBLE PRESIDENT (R-NECESSARY PRESIDENT) problem with parties P1↪ ▷ ▷ ▷ ↪ Pt, voters V , and integer w, such that for each j, 1  j  t, Pj is a clone set in election E = (Sti=1 Pi↪ V ). This is a yes instance if and only if candidate pw is a winner of the election E(p1 P1↪ ▷ ▷ ▷ ↪ pt Pt).

Proof. Irrespective of which candidates the parties nominate, always the candidate from the same party wins.

Proposition 1 has a very natural interpretation. It says that if the parties' candidates form clone sets, i.e., if the voters have a clear view of each party and can easily distinguish between them, then the choice of parties' nominees does not matter and the election is settled based on how the voters rank the parties. Yet, it is quite likely that in practice the parties' candidates would not form clone sets because, typically, each party (political or not) has some odd member who stands out from the rest, and who is difficult to rank.

4.2 Plurality and Unrestricted Preferences

We now show that when the parties' candidates are not restricted to be clone sets, then our problems are computationally hard, even if the parties are very small.

Theorem 1. Plurality-POSSIBLE PRESIDENT and PluralityNECESSARY PRESIDENT are NP-complete and coNPcomplete, respectively, even if sizes of parties are at most two.

Proof. It is clear that Plurality-POSSIBLE PRESIDENT is in NP and that Plurality-NECESSARY PRESIDENT is in coNP.

We now show NP-hardness of the former problem by a reduction from the standard 3-SAT problem. An instance of 3SAT consists of a set of Boolean variables X = ¶x1↪ ▷ ▷ ▷ ↪ xs♦ and a set of clauses C = ¶C1↪ ▷ ▷ ▷ ↪ Ck♦, with at most three literals per clause. We ask if it is possible to set the values of the variables so that the formula C1 ^ · · · ^ Ck evaluates to true.

Consider an instance of 3-SAT as described above. We form an instance of the Plurality-POSSIBLE PRESIDENT as follows:

1. We form two parties, P = ¶p♦ and P 0 = ¶p0 ♦ (we want to see if it is possible that P has a possible president, that is, it is possible that p is a winner ).
2. For each variable xi 2 X, we form a party Pi = ¶pi↪ ¯ pi♦. Intuitively, nominating candidate pi corresponds to assigning variable xi to true.

We introduce the following voters. For each voter, we list only the prefix of his or her preference order, until the first candidate that comes from a size-1 party, who certainly participates in the election. The remaining part of the preference order is completed arbitrarily.

1. There are k voters with preference order p ≻ ▷ ▷ ▷.
2. There are k voters with preference order p0 ≻ ▷ ▷ ▷.
3. For each clause Ci 2 C, we introduce one voter (referred to as the Ci-voter) with preference order `1 ≻ `2 ≻ `3 ≻ p0 ≻ ▷ ▷ ▷, where the top three candidates correspond to the literals of Ci (e.g., for literals xj and ≻xr we would have candidates pj and ¯ pr ).

We claim that there is a satisfying truth assignment for the input formula if and only if there is a way for the parties to nominate candidates so that p is a Plurality winner. To this end, note that p wins if and only if for each clause C one of the parties nominates a candidate ranked ahead of p0 . One can verify that each such set of nominated candidates corresponds to a satisfying truth assignment for the variables in X.

For the case of NECESSARY PRESIDENT, we give a reduction from the complement of 3-SAT. We use the same construction, with the following two changes: There are only k -1 voters that rank p0 on top, and we ask if P 0 has a necessary president (i.e., if p0 is a winner irrespective which candidates are nominated by their parties).

4.3 Plurality and Single-Peaked Preferences

The settings considered in the previous two sections are quite extreme. Effectively, in Section 4.1 we assume that the voters have preferences over parties rather than over the candidates (and the whole process of finding nominees is superfluous). On the other hand, in Section 4.2 we-implicitly-assume that members of a given party have nothing to do with each other (since each voter can mix and match members of different parties arbitrarily in his or her preference order). It is hardly realistic that completely unrelated candidates would be in one party. In this section we seek some middle ground, by considering electorates with single-peaked preferences.

On an intuitive level, an election is single-peaked if it is possible to arrange the candidates on a line (e.g., according to the standard political left-right axis) so that each voter picks a position on this line and ranks the candidates in the order of increasing distances from the voter's position. The formal definition is somewhat more general (but see the discussion later) and instead of using distances on the line, uses a combinatorial approach (the notion is due to Black [1958]).

Definition 4. Let C be a set of candidates. A societal axis for C is a linear order over C. We say that a preference order ≻ is consistent with respect to societal axis B if for each three candidates a↪ b↪ c 2 C it holds that:

An election (C↪ V ) is single-peaked with respect to axis B if each vote in v 2 V is consistent with B. An election is single-peaked if it is single-peaked with respect to some axis.

It is well-known that given an election E = (C↪ V ) it is possible to check if it is single-peaked (and, if so, to compute one of the axes with respect to which it is singlepeaked) in polynomial time [Bartholdi and Trick, 1986; Doignon and Falmagne, 1994; Escoffier et al., 2008]. Thus, whenever we consider single-peaked elections, we assume to also have an axis available.

It turns out that Plurality-POSSIBLE PRESIDENT is in P for the case of single-peaked elections, provided that the candidates from each party are ordered consecutively on the societal axis. If party members are not required to form consecutive groups, then the problem remains NP-complete. On the other hand, for single-peaked elections PluralityNECESSARY PRESIDENT is in P irrespective how the candidates are arranged on the societal axis.

Example 1. Assuming that candidates from the same party are ranked consecutively in the societal axis does not mean that the voters necessarily rank all of them consecutively. Let us consider four parties P1 = ¶a1↪ a2♦, P2 = ¶b1↪ b2↪ b3♦, P3 = ¶c1↪ c2♦, and P4 = ¶d1↪ d2♦. We have societal axis:

The following voters have preference orders consistent with the axis:

It is quite natural to require that candidates from the same party are consecutive on the societal axis as, for example, this justifies why they formed the party to begin with.

Let us move on to the technical discussion. In our algorithms, we rely heavily on the following lemma, due to Faliszewski et al. [2011].

Lemma 1 (Faliszewski et al. [2011]). Let (C↪ V ) be an election where C = ¶c1↪ ▷ ▷ ▷ ↪ cm♦ is a set of candidates, V is a collection of voters whose preferences are single-peaked with respect to a societal axis B, and where c1 B c2 B · · · B cm. If m ≥ 2, then under the Plurality rule, the following holds:

Intuitively, Lemma 1 says that in a single-peaked Plurality election, where the set of voters is fixed but the set of candidates can change, the score of a candidate c depends only on the identities of c's direct neighbors on the societal axis.

Theorem 2. Plurality-POSSIBLE PRESIDENT is in P provided that the input election is single-peaked and we are given an axis where the candidates from each party are ranked consecutively.

Proof. Our algorithm is as follows. We are given a set of parties P = ¶P1↪ ▷ ▷ ▷ ↪ Pt♦, a collection of voters with preferences over Sti=1 Pi, an integer w, 1  w  t, and societal axis B. Without loss of generality, we assume that the axis is of the form P1 BP2 B · · · BPt (that is, it first lists all the candidates from P1, then all the candidates from P2, and so on). The goal is to test if it is possible that a candidate from party Pw is a Plurality winner. We assume that Pw is neither P1 nor Pt (including this possibility is straightforward, but obfuscates the description).

First, we guess three candidates, cw-1 2 Pw-1, cw 2 Pw, and cw+1 2 Pw+1, and we take them to be the nominees of their parties. By Lemma 1, we know that irrespective which other candidates we choose, the score of cw will be S = score(¶cw-1↪cw↪cw+1♦↪V )(cw). Our goal is to test if it is possible to pick the nominees of the other parties, so that no candidate receives more than S points. We consider parties to the left and to the right of Pw separately.

Let us consider the parties to the left of Pw (on the societal axis). We define function f, so that for each i, 2  i  w - 1, and for each pair of candidates ci-1 2 Pi-1, ci 2 Pi, f(i↪ ci-1↪ ci) = 1 if it is possible to choose nominees c1↪ ▷ ▷ ▷ ↪ ci-2 for parties P1↪ ▷ ▷ ▷ ↪ Pi-2, so that:

1. score(¶c1↪c2♦↪V )(c1)  S, and

Otherwise, f(i↪ ci-1↪ ci) = 0.

It is straightforward to compute the values of f for i = 2. For larger values of i, we use the following recursive formulation (we assume i to be a number greater or equal to 2, ci and ci+1 to be candidates from Pi and Pi+1, respectively):

f(i + 1↪ ci↪ ci+1) = 1 if and only if there exists a candidate ci-1 2 Pi-1 such that f(i↪ ci-1↪ ci) = 1 and score(¶ci-1↪ci↪ci+1↪V )(ci)  S.

Thus, using standard dynamic programming techniques, it is possible to compute the values of f in polynomial time.

Clearly, it is possible to ensure that the nominees of the parties to the left of Pw have scores at most S if f(w↪ cw-1↪ cw) = 1. Handling parties to the right of Pw is analogous and we omit it. If we can ensure that all the nominees have score at most S, then we accept. If we do not accept after trying all choices of cw-1, cw, cw+1, we reject.

Without the assumption on the parties' candidates being consecutive in the societal axis, Plurality-POSSIBLE PRESIDENT is NP-complete. The result is based on a reduction from VERTEX COVER, a standard NP-complete problem.

Definition 5. An instance of the VERTEX COVER problem consists of an undirected graph G and a nonnegative integer k. We ask if there exists a set of up to k vertices such that every edge is incident to at least one vertex from the set.

Typically, we reserve symbols E and V to mean, respectively, an election and a collection of voters. By a slight abuse of notation, to denote the sets of vertices and edges of a graph G we write V (G) and E(G), respectively.

Theorem 3. Plurality-POSSIBLE PRESIDENT is NPcomplete even if the voters' preferences are single-peaked.

Proof. It is clear that the problem is in NP. To show that it is NP-hard, we give a reduction from VERTEX COVER.

Let (G↪ k) be an input instance of the VERTEX COVER problem, where G is an undirected graph and k is a positive integer. We write V (G) = ¶v1↪ ▷ ▷ ▷ ↪ vn♦ to denote the set of G's vertices. We form an instance of Plurality-POSSIBLE PRESIDENT as follows. We introduce the following parties:

1. We form party P = ¶p♦. Our goal will be to check if it is possible to ensure that P has a possible president (i.e., if it is possible to ensure that p is a winner).
2. For each vertex v` 2 V (G), we form a party Pv` = ¶v`↪ f 1 ` ↪ ▷ ▷ ▷ ↪ f n-k ` ♦. Intuitively, choosing a candidate v` for the party will correspond to accepting that v` is part of the vertex cover.
3. For each vertex v`, we have two parties P 0v` = ¶a0` ♦ and P 00 v` = ¶a00 ` ♦. We will use these candidates to ensure that candidates that correspond to vertices not in the cover do not have too many points.
4. For each edge e = ¶vi↪ vj♦ 2 E(G), we introduce party Pe = ¶eij↪ eji♦. Intuitively, choosing eij as the nominee of the party corresponds to deciding that vertex vi covers e, and choosing eji corresponds to deciding that vj covers e.
5. For each j, 1  j  n - k, we introduce party Pj = ¶gj♦. We will use the nominees of these parties to ensure that the vertex cover that we simulate uses at most k vertices.

For each vertex v` 2 V (G), let δ(v`) mean the degree of v`, and for each j, 1  j  δ(v`), by f(`↪ j) we mean the (index of the) j'th vertex connected by an edge to v` (in some fixed, arbitrary order; e.g., if the j'th vertex connected to v` is v7 then f(`↪ j) = 7).

We now define the societal axis B. For each vertex v` 2 V (G), we set A` to be the following fragment of the axis:

For each j, 1  j  n-k, we define Gj to be the f j 1 B· · ·B f jn B gj fragment of the axis. The complete axis is:

We introduce the following voters. As in the proof of Theorem 1, for each voter we list only the prefix of his or her preference order, until the first candidate that comes from a size-1 party. We assume that the remaining part of the preference order is completed arbitrarily, but so that the vote is single-peaked with respect to our axis.

1. There are two voters with preference order p ≻ · · · .
2. For each vertex v` 2 V (G), we introduce one voter with preference order:

and two voters with preference order:

We refer to these voters as v`-voters.

1. For each j, 1  j  n - k there are two voters with preference order gj ≻ · · · and one voter with preference order f j 1 ≻ f j 2 ≻ · · · ≻ f jn ≻ gj ≻ · · · . We refer to these three voters as gj-voters.

We claim that there is a size-k vertex cover for G if and only if it is possible to pick parties' nominees so that p wins.

First, let us assume that there is a size-k vertex cover for G and let us rename the vertices (and all the other entities in our construction) so that v1↪ ▷ ▷ ▷ ↪ vk is a vertex cover for G. We choose the following nominees for the parties (we only mention those parties that have more than one candidate):

1. For each party Pv` , 1  `  k, we choose as the nominee candidate v`.
2. For each party Pv` , k + 1  `  n, we choose as the nominee candidate f `-k ` .
3. For each party Pe, where e 2 E(G) and e = ¶vi↪ vj♦ for some two vertices (i < j), we choose eij (note that by renaming of the vertices, it must be that vi belongs to the vertex cover).

In effect, p gets 2 points and every other candidate gets at most 2 points. This is so for the following reasons: Every group of gj-voters gives two points to gj and one point to f j j+k . Every group of v`-voters, for 1  `  k, gives one point to v` and two points to some candidate of the form e` f(`↪j) for some value of j. Every group of v`-voters, for k + 1  `  n, gives one point to a0` and two points to a00 ` .

For the other direction, let us assume that it is possible to pick the nominees for the parties so that p is a winner. This means that in the final election every candidate receives at most two points. In particular, this means that at least n - k of the parties Pv1 ↪ ▷ ▷ ▷ ↪ Pvn have nominees that do not correspond to the vertices (otherwise, some gj-voters would give three points to gj). Indeed, without loss of generality, we can assume that there are exactly k parties among Pv1 ↪ ▷ ▷ ▷ ↪ Pvn whose nominees correspond to the candidates, and we can assume (by appropriate renaming of all the candidates) that these nominees are v1↪ ▷ ▷ ▷ vk.

For every edge e = ¶vi↪ vj♦ 2 E(G), party Pe picks either eij or eji as the nominee. Let us consider what happens if it chooses eij (the other situation is analogous). If vi is not a nominee of his or her party, then-by the choice of the preference orders of the vi-voters-either eij receives three points or some other candidate of the form eik, 1  k  n, receives three points. Since this is impossible, we know that vi is a nominee of his or her party. However, this means that for every edge e = ¶vi↪ vj♦ 2 E(G), one of vi↪ vj is in v1↪ ▷ ▷ ▷ ↪ vk. This means that v1↪ ▷ ▷ ▷ ↪ vk is a vertex cover for G.

It turns out that the above proof is much stronger than it may initially appear. In fact, it shows that PluralityPOSSIBLE PRESIDENT is NP-complete even when the voters' preferences are 1D-Euclidean single-peaked:

Definition 6. We say than election E = (C↪ V ) is 1DEuclidean single-peaked if there exists a function f : C [ V ! R such that for each voter vt 2 V and each two candidates ci↪ cj 2 C it holds that ci ≻t cj if and only if ♣f (vt) - f (ci)♣ < ♣f (vt) - f (cj )♣.

Intuitively, 1D-Euclidean single-peakedness means that we can put voters and candidates on a line, and each voter forms his or her preference order by sorting the candidates with respect to the increasing distances from him or herself.

All 1D-Euclidean single-peaked elections are also singlepeaked in the classic sense. It is also known that all 1DEuclidean single-peaked elections satisfy the single-crossing property 4 (not discussed here in much detail, it was introduced by Mirrlees [1971] and Roberts [1977]). As shown independently by Elkind et al. [2014] and Chen et al. [2015], there are elections that are both single-peaked and singlecrossing, but not 1D-Euclidean.

The preference orders used in the proof of Theorem 3 are so simple that our election can be implemented as 1DEuclidean (details omitted) and we get the next corollary

Corollary 1. Plurality-POSSIBLE PRESIDENT is NPcomplete even if the voters' preferences are 1D-Euclidean single-peaked (so, also if the preferences are single-crossing).

Finally, we show that for single-peaked elections PluralityNECESSARY-PRESIDENT is in P.

Theorem 4. Plurality-NECESSARY PRESIDENT is in P provided that the input election is single-peaked.

Proof sketch. Consider an input for Plurality-NECESSARY PRESIDENT (using notation as in the definition). First, we guess a candidate p from party Pw, for whom we will check if p is a necessary president. To conduct this test, we check if there is some candidate d from some other party and a way for yet other parties to nominate candidates so that d has more points than p. By Lemma 1, the scores of p and d depend only on the identities of their direct (nominated) neighbors on the societal axis. We check if it is possible to fix d and these (at most four) candidates so the score of d is higher than the score of p. If so, we drop the guess of p and try another candidate from Pw (if there are no other candidates to try, we reject). If not, we try another candidate d, and we accept after we run out of all choices for d without rejecting. Altogether, we have to try at most m6 6-tuples of candidates, so the algorithm runs in polynomial time.

5 Conclusions

Our problems model the setting where parties can nominate candidates in some (Plurality) election and want to make sure they win or, at least, want to make sure if they have a chance of winning. We have shown that in general our problems are computationally hard, but become polynomial-time solvable under appropriate (fairly natural) restrictions.

There is a number of possibilities for future research. For example, one might study more voting rules or, perhaps more interestingly, one may consider our setting from a gametheoretic perspective. Indeed, we do follow-up on this latter idea in our ongoing research.

Acknowledgments

Laurent Gourv`es, J´erˆome Lang, Julien Lesca and J´erˆome Monnot acknowledge support from the ANR project CoCoRICo-CoDec. Part of the work was conducted when Piotr Faliszewski visited Paris Dauphine as invited professor.

4 Voters can be ordered such that, for every pair a, b of candidates, there exists a position tab such that voters from position 1 to position tab prefer a to b and the remaining voters prefer b to a.