# strategic_candidacy_games_with_lazy_candidates__6dfa908a.pdf

Strategic Candidacy Games with Lazy Candidates

Svetlana Obraztsova Tel Aviv University Tel Aviv, Israel

Edith Elkind University of Oxford Oxford, United Kingdom

Maria Polukarov University of Southampton Southampton, United Kingdom

Zinovi Rabinovich Mobileye Vision Technologies Ltd. Israel

In strategic candidacy games, both voters and candidates have preferences over the set of candidates, and candidates may strategically withdraw from the election in order to manipulate the outcome according to their preferences. In this work, we extend the standard model of strategic candidacy games by observing that candidates may ﬁnd it costly to run an electoral campaign and may therefore prefer to withdraw if their presence has no effect on the election outcome. We study the Nash equilibria and outcomes of natural best-response dynamics in the resulting class of games, both from a normative and from a computational perspective, and compare them with the Nash equilibria of the standard model.

1 Introduction

In his paper Independence of clones as a criterion for voting rules [1987] Nicolaus Tideman tells the following story:

When I was 12 years old I was nominated to be treasurer of my class at school. A girl named Michelle was also nominated. I relished the prospect of being treasurer, so I made a quick calculation and nominated Michelle s best friend, Charlotte. In the ensuing election I received 13 votes, Michelle received 12, and Charlotte received 11, so I became treasurer.

Tideman uses this story to motivate the concept of clones candidates that are so similar to each other that all voters rank them consecutively and considers the problem of designing clone-proof voting rules. However, one can also look at this story from a somewhat different perspective: It is plausible that both Michelle and Charlotte preferred either of them becoming the treasurer to the outcome where both of them lost. Thus, either girl could have decided to withdraw her candidacy to obtain a more desirable election result. Now, while a typical teenager may ﬁnd it difﬁcult to make a calculated choice in such situations (Tideman s younger self

being an obvious exception), candidates in high-stakes elections often have strong preferences over possible election outcomes as well as strategic reasoning skills, and may therefore consider withdrawing from an election so as to change its winner to one they prefer to the current one. The resulting interaction among the candidates can be described as a non-cooperative game, where players are the candidates, each candidate can choose whether to participate or not, the voters (who are typically not considered to be strategic players see, however, [Brill and Conitzer, 2015], where the model is extended to strategic voters) choose among the available candidates, and each player compares possible outcomes according to his ranking of the candidates. Such games are known as strategic candidacy games; they were introduced by Dutta, Le Breton and Jackson [2001; 2002], and have subsequently been studied by several other authors [Ehlers and Weymark, 2003; Eraslan and Mc Lennan, 2004; Rodriguez-Alvarez, 2006a; 2006b; Lang et al., 2013; Polukarov et al., 2015].

In the model of Dutta et al., which was also adopted in subsequent work on strategic candidacy games, it is assumed that each player is indifferent between any two strategy proﬁles that result in the same election outcome. However, in practice candidates often have to take into account the monetary and reputational costs of running an electoral campaign. In particular, it is often natural to assume that candidates are lazy , i.e., they prefer not to participate in the election if doing so has no impact on who becomes the winner. This type of secondary preferences has been recently considered in the context of analyzing the behavior of strategic voters, i.e., voters were assumed to abstain when they were not pivotal (see, e.g., [Desmedt and Elkind, 2010; Elkind et al., 2014] and references therein). However, to the best of our knowledge, strategic candidacy games with lazy candidates have not been investigated in prior work.

The goal of this paper is to initiate the study of this class of games. For simplicity, we focus on the case where the voters make their choice among the available candidates using the Plurality rule. We consider Nash equilibria of such games as well as analyze two natural best-response dynamics for this setting: one where initially the set of active candidates is empty and the candidates join one by one, and one

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)

where initially all candidates are present, but then withdraw one by one. We relate the properties of strategic candidacy games with lazy candidates to those of vanilla strategic candidacy games, explore the role of Pareto dominance and Condorcet winners in this setting, and prove a number of computational complexity results. In particular, we show that checking whether a given strategic candidacy game with lazy candidates admits a Nash equilibrium is NP-complete.

2 Preliminaries and Model We consider settings where there is a ﬁnite set of potential candidates C = {c1, c2, . . . , cm} and a ﬁnite set of voters V = {v1, v2, . . . , vn}; we assume C V = . Given a set A C, let L(A) denote the set of all linear orders over A. Each voter v V is associated with a preference order v L(C); the list P V = ( v)v V is referred to as the voters preference proﬁle. An election proceeds as follows. First, a subset of candidates A C announces that they will participate in the election; we refer to the candidates in A as the actual candidates. If A = , a pre-determined candidate from C is declared to be the election winner. Otherwise, each voter v V reports her preferences over the candidates in A; these preferences are obtained by restricting v to A. We assume that all voters report their preferences sincerely. A voting rule takes the set A and the list of voters preferences over A as input, and outputs a candidate w A; this candidate is called the election winner. In this paper, we will only consider the Plurality rule. Under this rule, the score sc(c) of a candidate c A is equal to the number of voters who rank c ﬁrst among the candidates in A; the winner is the candidate with the highest score, with ties broken according to a ﬁxed priority order over C (i.e., if sc(a) = sc(b) > sc(c) for every c A\{a, b} and a b, then a is declared to be the election winner). For consistency, we assume that, when A = , the winner is the top candidate in ; we denote this candidate by c .

Candidacy games Candidacy games are characterized by two important features: (1) candidates themselves also have preferences over the set C, and (2) each candidate can choose whether to run in the election. Formally, each candidate c C has two available actions: 1 (run) and 0 (abstain). Also, each candidate c C is endowed with a preference order c over C; the list P C = ( c )c C is referred to as the candidates preference proﬁle. We say that a candidate c C has self-supporting preferences if c c a for all a C \ {a}. While much of the work on candidacy games assumes that all candidates have selfsupporting preferences, and, indeed, this assumption is reasonable in many real-life scenarios, there are settings where it is not satisﬁed. For example, a person may volunteer for a leadership position because her colleagues expect her to do so, but secretly hope not to be elected because of the associated workload. Therefore, instead of making this assumption in our work, we explicitly indicate which of our results hold for candidates with self-supporting preferences. The tuple C, V, P V , P C, deﬁnes two related strategic games: the vanilla strategic candidacy game (VSCG)

Γ = Γ(C, V, P V , P C, ) and the lazy strategic candidacy game (LSCG) ΓL = ΓL(C, V, P V , P C, ). In both games, the set of players is C and each player s set of actions is {0, 1}. We denote the action (strategy) of a player c C by sc; the vector s = (sc)c C is called the strategy proﬁle. A strategy proﬁle s deﬁnes the set of actual candidates A(s) = {c C | sc = 1}. Consequently, each strategy proﬁle deﬁnes an outcome w(s) C: w(s) is simply the outcome of Plurality voting by voters in V over candidates in A(s) when A(s) is not empty (with ties broken according to ), and w(s) = c when A(s) = . We denote by sc(c, s) the Plurality score obtained by a candidate c A(s) when voters in V vote over candidates in A(s). The only difference between Γ and ΓL is in the players preferences over the states of the game: in Γ a player c prefers s to t (denoted by s >c t) if and only if w(s) c w(t), whereas in ΓL a player c prefers s to t (denoted by s >L c t) if and only if (i) w(s) c w(t) or (ii) w(s) = w(t), sc = 0 and tc = 1. That is, in ΓL a candidate is willing to run if his presence can change the election outcome for the better; however, if his presence has no effect on the election outcome, he prefers not to participate. These deﬁnitions extend to voting rules other than Plurality in an obvious way. We will be interested in Nash equilibria of VSCGs and LSCGs. Recall that a strategy proﬁle s is said to be a pure strategy Nash equilibrium if no player in the game can profitably deviate. Formally, given a VSCG Γ (respectively, an LSCG ΓL) described by a 5-tuple C, V, P C, P V , , we say that a strategy proﬁle s is a pure strategy Nash equilibrium (PNE) of Γ (respectively, ΓL) if for every candidate c C it is not the case that t >c s (respectively, t >L c s), where t is the strategy proﬁle given by ta = sa for a C \ {c}, tc = 1 sc. In what follows, we write v : abc (respectively, c : abc) to indicate that the preference order of voter v (respectively, candidate c) is a b c. When voters names are not important, we omit them, and write, e.g., (abc, abc, bca) to denote a proﬁle where two voters rank the candidates as a b c and one voter ranks the candidates as b c a. Also, we will sometimes identify a state s with its set of actual candidates A(s).

3 Nash Equilibria We start our investigation of lazy strategic candidacy games by exploring the properties of their PNE.

Properties of Nash Equilibria In this section, we consider the role of common social choice concepts, such as Pareto dominance and Condorcet winners, in LSCGs. We will also compare these games to their vanilla counterparts. Pareto Dominance Consider an LSCG ΓL where candidate a Pareto-dominates candidate b in P V , i.e., every voter in V prefers a to b. One would expect that b cannot be the election winner in a PNE of ΓL. However, this turns out to depend on b s preferences and the tie-breaking order . Proposition 1. Let ΓL = ΓL(C, V, P C, P V , ). Suppose that a v b for all v V . If (1) a a b and (2) a b then for

every PNE s of ΓL we have b = w(s). However, if either of the conditions (1) and (2) is not satisﬁed, b can be a winner in a PNE of ΓL.

Proof. Suppose that conditions (1) and (2) are satisﬁed, and suppose for the sake of contradiction that there is a PNE s with w(s) = b. Note that a b implies b = c , and hence t = sc(b, s) > 0. Clearly, a A(s): otherwise no voter would rank b ﬁrst. Consider the modiﬁed strategy proﬁle s with s a = 1, s c = sc for c C \ {a}. We have sc(a, s ) t: all voters who vote for b in s would switch to voting for a in s . On the other hand, since b = w(s), for every candidate c C\{a, b} we have sc(c, s ) sc(c, s) t, and sc(c, s) = t implies b c. As a b, this means that a = w(s ); since a a b, switching from s to s is a proﬁtable deviation for a. It is easy to see that condition (1) is necessary: consider an election with C = {a, b}, a single voter who prefers a to b, and candidates preferences given by b a a, b b a. Clearly, the resulting game has a PNE s with A(s) = {b}. To see that condition (2) is necessary, let C = {a, b, c, d}, and suppose that b c a d and voters /candidates preferences are given by

P V = (dcab, cdab, cdab, abcd, abcd),

P C = (a : abcd, b : bacd, c : cabd, d : dbac).

Then the strategy proﬁle s with A(s) = {b, c, d} is a PNE, even though all voters as well as candidate a prefer a to b.

Note that condition (1) is satisﬁed whenever all candidates have self-supporting preferences. Furthermore, the reader can check that Proposition 1 remains true for VSCGs.

Condorcet Winners An important notion in social choice is that of a Condorcet winner: this is a candidate that beats every other candidate in their pairwise election. Formally, given a proﬁle P V over a candidate set C and two candidates a, b C, let nab denote the number of voters in V who prefer a to b. A candidate c C is said to be a Condorcet winner in (C, P V ) if nca > nac for all a C \ {c}. This concept turns out to be relevant for our analysis: if a candidate c is a Condorcet winner in (C, P V ), and c has self-supporting preferences, then the strategy proﬁle s with A(s) = {c} is clearly a PNE of the respective game ΓL. Indeed, if any other candidate decided to run, he would lose to c anyway, and c has no reason to withdraw. In fact, we can obtain a full characterization of PNE with exactly one participating candidate, by modifying this concept so as to take into account the candidates preferences and the tie-breaking order. Speciﬁcally, given a priority order over C, we say that a candidate c C is a (P C, )- Condorcet winner in (C, P V , P C) if for each a C \ {c} we have (i) nca > nac or (ii) nca = nac and c a or (iii) c a a. Note that an election may have several (P C, )- Condorcet winners; however, if the number of voters is odd and all candidates have self-supporting preferences, a candidate is a (P C, )-Condorcet winner in (C, P V , P C) if and only if she is a Condorcet winner in (C, P V ). We are now ready to state our characterization result.

Proposition 2. Let ΓL = ΓL(C, V, P C, P V , ). A strategy proﬁle s0 with A(s0) = is a PNE of ΓL if and only if we have c c c for all c C \ {c }. Further, for a given candidate c C the strategy proﬁle sc with A(sc) = {c} is a PNE of ΓL if and only if c is a (P C, )-Condorcet winner in (C, P V , P C), c = c , and c c c .

Proof. We have w(s0) = c . Thus, if every candidate c C \ {c } prefers c to herself, she has no reason to participate, and neither does c . Conversely, if c c c for some c C \ {c }, candidate c would prefer to join the election and win. Now, consider a candidate c and the strategy proﬁle sc. If c is a (P C, )-Condorcet winner, no candidate that can change the election outcome by participating is willing to do so. Moreover, if c = c and c c c , c prefers not to withdraw. Thus, under these conditions sc is a PNE of ΓL. Conversely, if c = c or c c c, then c would prefer to withdraw, and if c is not a (P C, )-Condorcet winner, there is a candidate a who beats c in their pairwise election and prefers herself to c; this candidate could then participate in the election and win.

Interestingly, the analysis in Proposition 2 shows that if c is a (P C, )-Condorcet winner then there is no PNE where c is the unique candidate participating in the election; in contrast, if any other candidate is a (P C, )-Condorcet winner and has self-supporting preferences, there is a PNE where this candidate is the unique participant. Elkind et al. [2014] observe that a similar phenomenon arises in equilibria of Plurality elections with lazy voters. We remark that even if an instance (C, P V , P C) has a (P C, )-Condorcet winner, it may have PNE where the (P C, )-Condorcet winner does not participate. Example 1. Let C = {a, b, c, d}, and suppose that a b c d and voters /candidates preferences are given by

P V = (bacd, cadb, dacb),

P C = (a : abcd, b : bcda, c : cbda, d : dbca).

Candidate a is the unique (P C, )-Condorcet winner, yet the strategy proﬁle s with A(s) = {b, c, d} is a PNE.

Vanilla vs. Lazy Games It is not hard to verify that every PNE of a lazy strategic candidacy game is also a PNE of the respective vanilla strategic candidacy game. Proposition 3. Consider a tuple C, V, P C, P V , and let Γ = Γ(C, V, P C, P V , ) and ΓL = ΓL(C, V, P C, P V , ). Then every PNE of ΓL is a PNE of Γ.

Proof. Consider a strategy proﬁle s for C, V, P C, P V , and a candidate c C. Suppose that s is a PNE of ΓL with winner w. If sc = 1, then, since s is a PNE of ΓL, setting sc = 0 would change the election outcome from w to some p with w c p; thus, in Γ player c would not want to change his action to 0 either. On the other hand, if sc = 0, since s is a PNE of ΓL, it has to be the case that setting sc = 1 either does not change the election outcome at all, or changes it to one that c likes less than w. Hence c cannot proﬁtably deviate in Γ either.

It is known that VSCGs under Plurality may have no PNE [Lang et al., 2013]; Proposition 3 implies that this is also the case for LSCGs. The converse of Proposition 3 is not true: a strategy proﬁle that is a PNE of Γ may fail to be a PNE of ΓL. An example is easy to construct: suppose, for instance, that C = {a, b}, all voters prefer a to b, and the candidates have self-supporting preferences. Then s = (1, 1) is a PNE of Γ, but in ΓL candidate b prefers to abstain. A somewhat more complicated example shows that there are settings where Γ has a PNE, but ΓL does not. Example 2. Let C = {a, b, c}, and suppose that we have

P V = (abc, bca, cab), P C = (a : abc, b : bca, c : cab).

Suppose also that a b c. Then Γ(C, V, P V , P C, ) has a PNE s with A(s) = {a, b}, w(s) = a. However, ΓL = ΓL(C, V, P V , P C, ) has no PNE. To see this, observe ﬁrst that LSCGs have no PNE with exactly two participating candidates: indeed, the loser would prefer to withdraw. Moreover, as GL has no (P C, )-Condorcet winner, by Proposition 2 it has no PNE with one participating candidate, and since candidates preferences are self-supporting, there is no PNE with zero participating candidates. It remains to observe that (1, 1, 1) is not a PNE of GL either, as candidate c would rather withdraw.

Complexity of PNE Proposition 2 describes PNE where the number of participating candidates is zero or one. However, Example 1 illustrates that there can be PNE with three participants, and it is easy to extend the construction in that example to obtain PNE with any number of participants. This indicates that it may be nontrivial to identify all PNE of a given game, and provides motivation for studying the complexity of computing PNE in lazy strategic candidacy games. To this end, we deﬁne the following decision problems: LAZYNE: Given a game ΓL = ΓL(C, V, P V , P C, ) and a strategy proﬁle s, decide whether s is a PNE of ΓL. LAZY NE: Given a game ΓL = ΓL(C, V, P V , P C, ) decide whether ΓL has a PNE. LAZY WNE: Given a game ΓL = ΓL(C, V, P V , P C, ) and a candidate c C, decide whether ΓL has a PNE s with w(s) = c. It is easy to see that LAZYNE is in P: as each player only has two available actions, we only need to consider n possible deviations. In contrast, LAZY NE and LAZY WNE turn out to be computationally hard. Theorem 1. For lazy strategic candidacy games, the problems LAZY NE and LAZY WNE are NP-complete, even if all candidates have self-supporting preferences.

Proof. Our observation that LAZYNE is polynomial-time solvable immediately implies that these problems are in NP. To show that these problems are NP-hard, we provide a reduction from a restricted variant of the classic EXACT 3COVER (X3C) problem. An instance of this problem is given by a set of ground elements U = {u1, . . . , u3r} and a family

Z = {Z1, . . . , Zt} of 3-element subsets of U; we assume that Zℓ= {uiℓ, ujℓ, ukℓ} for some iℓ, jℓ, kℓ {1, . . . , 3r}. It is a yes -instance if there exists a subfamily b Z Z such that Z b ZZ = U and Zi Zj = for all Zi, Zj b Z with i = j; otherwise it is a no -instance. We additionally assume that r 2 and each element of U is contained in exactly three distinct sets in Z; note that this implies that t = 3r. This variant of X3C, which we will refer to as RX3C, has been shown to be NP-complete by Gonzalez [1984]. Given an instance (U, Z) of RX3C with |U| = 3r, we set q = 30r2 and construct an LSCG with the set of candidates C = U Z {w0, w1, w2} and n = 18r+3r(q 1)+3q 3r voters. The preference proﬁles P V and P C are speciﬁed in Tables 1 and 2, respectively. In these tables we write Ui to denote the order ui ui+1 u3r u1 ui 1 over U; we write Ui \ U , where U U, to refer to the order Ui with the candidates in U removed. Also, we write Z i to refer to an arbitrary order over Z \ {Zi}; similarly, we write U and Z to refer to arbitrary orders over U and Z, respectively. Finally, we set w1 U Z w2 w0. Note that the candidates preferences are self-supporting. Let ΓL = ΓL(C, V, P V , P C, ). We will now argue that if we have started with a yes - instance of RX3C then ΓL has a PNE with winner w1, and if we have started with a no -instance of RX3C then ΓL has no PNE. This establishes NP-hardness of both LAZY NE and LAZY WNE. Speciﬁcally, it can be checked that if a collection of subsets Z provides an exact cover of U then the strategy vector s with A(s) = U {w0, w1, w2} (Z \ Z ) is a PNE with w(s) = w1. For the converse direction we show that if ΓL has a PNE s, then U {w0, w1, w2} A(s) and w(s) = w1, and use this to conclude that candidates in Z \ A(s) provide an exact cover of U. In more detail, observe ﬁrst that this proﬁle does not admit a (P C, )-Condorcet winner: indeed, the candidates preferences are self-supporting, for every candidate c C \ U at least 3r(q 1) > n/2 voters prefer any candidate in U to c, and for every candidate ui C at least (3r 1)(q 1) > n/2 voters prefer ui 1 to ui (where we let u0 := u3r). Now, suppose that ΓL had a PNE s. We will argue that U {w0, w1, w2} A(s) and w(s) = w1. To show this, we will ﬁrst prove that A(s) U = . Indeed, if A(s) U = , then if u1 were to enter the election, he would receive 3r(q 1) > n/2 votes and win. As u1 has selfsupporting preferences, this is a contradiction with s being a PNE of ΓL. Moreover, we have U A(s). Indeed, suppose that U \ A(s) = . Then there exists a candidate ui U A(s) with sc(ui, s) 2q 2. As A(s) U = , the score of each candidate in Z {w0, w1, w2} does not exceed q + 18r < 2q 2, so the winner is some candidate uj U. Applying an inductive argument to candidates uj 1, . . . , u1, u3r, . . . , uj+1 (where u0 := u3r and u3r+1 := u1), we conclude that each of these candidates prefers not to participate in the election. Thus, sc(uj, s) 3r(q 1), and therefore all candidates in Z {w0, w1, w2} prefer not to participate as well, so

Block 1 (3r votes) Block 2 (6r votes) Block 3 (9r votes) Z1 Z2 . . . Z3r Z1 Z1 . . . Z3r Z3r . . . Zℓ Zℓ Zℓ . . . w1 w1 . . . w1 w2 w2 . . . w2 w2 . . . uiℓ ujℓ ukℓ . . . w2 w2 . . . w2 U1 U1 . . . U3r U3r . . . w2 w2 w2 . . . U1 U2 . . . U3r Z 1 Z 1 . . . Z 3r Z 3r . . . Uiℓ\ {uiℓ} Ujℓ\ {ujℓ} Ukℓ\ {ukℓ} . . . Z 1 Z 2 . . . Z 3r w0 w0 . . . w0 w0 . . . Z ℓ Z ℓ Z ℓ . . . w0 w0 . . . w0 w1 w1 . . . w1 w1 . . . w0 w0 w0 . . . . . . w1 w1 w1 . . .

Block 4 (3r(q 1) + 3q 3r votes) u1 u2 . . . u3r w2 w1 w0 U1 \ {u1} U2 \ {u2} . . . U3r \ {u3r} U U U Z Z . . . Z Z Z Z w2 w2 . . . w2 w0 w2 w2 w0 w0 . . . w0 w1 w0 w1 w1 w1 . . . w1 | {z } | {z } | {z } | {z } | {z } | {z } (q 2r) copies (q r) copies q copies

(q 1) copies (q 1) copies (q 1) copies

Table 1: Proof of Theorem 1: voters preferences

A(s) = {uj}. But this is a contradiction with Proposition 2, as uj is not a (P C, )-Condorcet winner. The contradiction shows that U A(s). We can now conclude that {w0, w1, w2} A(s): if this was not the case, u1 would get at least 2q 2r 1 point and win, in which case u3r would prefer to withdraw. It follows that w1 = w(s): otherwise a candidate ui U \ {w(s), u3r} would prefer to withdraw, as this would make ui+1 the winner, and ui prefers ui+1 to all candidates other than himself and w1. Now that we have established that w1 = w(s), we can observe that exactly 2r candidates from Z participate in the election: if |A(s) Z| = 2r + x for x > 0 then sc(w1, s) < q = sc(w0, s), and if |A(s) Z| = 2r x for x > 0 then sc(w2, s) = q 2r +2(r +x) > q r +(r +x) = sc(w1, s). Let b Z = Z \ A(s). We have shown that | b Z| = r. We will now argue that b Z provides an exact cover of U. Indeed, suppose that this is not the case. As | b Z| = r, it follows that there exists an element ui U that appears in two distinct sets Zj, Zk b Z. But then we have sc(ui, s) q + 1 > q = sc(w1, s), a contradiction with w1 = w(s).

It is natural to ask whether the hardness results established in Theorem 1 still hold if the number of voters or the number of candidates is small. It turns out that both LAZY NE and LAZY WNE become easier under these constraints. In more detail, it is immediate that both LAZY NE and LAZY WNE admit an algorithm whose running time is 2mpoly(n, m), where n = |V | and m = |C|: we can simply enumerate all strategy proﬁles, and, for each of them, check whether it is a PNE and, in case of LAZY WNE, compute its winner. In fact, this procedure works not just for Plurality,

Zℓ, ℓ= 1, . . . , 3r ui, i = 1, . . . , 3r w1 w2 w0 Zℓ ui w1 w2 w0 uiℓ w1 w2 w1 w1 ujℓ Ui \ {ui} U U U ukℓ Z Z Z Z w1 w2 w0 w0 w2 Uℓ\ {uiℓ, ujℓ, ukℓ} w0 Z ℓ

Table 2: Proof of Theorem 1: candidates preferences

but for any voting rule with a polynomial-time winner determination procedure. To obtain an algorithm that performs well when the number of voters n is small, we observe that (1) in any PNE of a Plurality-based LSCG the number of candidates with a positive score does not exceed n, and (2) in any PNE s we have sc(c, s) > 0 for all c A(s). Therefore, it sufﬁces to consider strategy proﬁles s with |A(s)| n; the number of such proﬁles does not exceed mn. The following proposition summarizes these observations in the language of ﬁxed-parameter complexity (see, e.g., Niedermeier [2006]).

Proposition 4. The problems LAZY NE and LAZY WNE are in FPT with respect to the number of candidates m and in XP with respect to the number of voters n.

4 Best-response Dynamics

In practice, knowing that a game has a PNE does not necessarily mean that players will reach a stable outcome, as it may be difﬁcult for computationally bounded players to ﬁnd it. Therefore, it is important to understand which states of the game can be achieved by players that optimize their behavior in an iterative fashion. To this end, we will now consider myopic dynamics of LSCGs, i.e., sequences of states where each state is obtained from the previous one by allowing a single player to deviate in a way that is beneﬁcial for her. It is natural to assume that once a candidate withdraws from the election, he cannot rejoin it; indeed, this is typically the case in real-life elections. Under this assumption, if all candidates were present in the initial state, then at each subsequent step one candidate withdraws from the election until none of the remaining candidates has an incentive to do so; we refer to this type of dynamics as W-dynamics. We will also consider the complementary setting where initially the set of candidates is empty, and the candidates join the election one by one and are not allowed to leave; we refer to this type of dynamics as J-dynamics. Under both types of dynamics each candidate can change his action at most once, and therefore any such dynamic process converges in at most m steps, where m is the number of candidates. Note, however, that the ﬁnal state need not be a PNE: e.g., under W-dynamics it may be the case that a candidate who has withdrawn at an earlier point would prefer to rejoin, but is prevented from doing so by the no rejoining rule. Thus, the set of states reachable by such dynamics can be seen as a distinct solution concept for LSCGs. We will now discuss some properties of the W-dynamics and J-dynamics. For simplicity, we assume that the number of voters is odd and the candidates preferences are selfsupporting (and hence a candidate is a (P C, )-Condorcet winner if and only if she is a Condorcet winner); however, our results extend to the general case. Consider a game ΓL = ΓL(C, V, P C, P V , ). We have argued that if (C, P V ) has a Condorcet winner c = c then ΓL has a PNE s with A(s) = {c}. We will now investigate whether such a PNE can be achieved by W-dynamics or Jdynamics.

Proposition 5. Let ΓL = ΓL(C, V, P C, P V , ), and suppose that c = c in a Condorcet winner in (C, P V ). Then there is a J-dynamics that leads to the state s with A(s) = {c}. However, there may be no W-dynamics that terminates in a state s with c A(s ), and there may exist a J-dynamics that terminates in a state s with c A(s ).

Proof. The J-dynamics where agent c joins at the ﬁrst step terminates as soon as c joins, since the resulting state is a PNE. For W-dynamics, consider the proﬁle in Example 1: here the Condorcet winner a is the only candidate that has an incentive to leave from the original state (1, 1, 1, 1), so he is not present in any terminal state of the W-dynamics. Further, the reader can verify that {d} {c, d} {b, c, d} is a J-dynamics for this proﬁle that results in a stable state where a does not participate.

It is also interesting to ask whether our dynamics can terminate in the state where all candidates are present. Clearly, for W-dynamics this is only possible if this state is a PNE. In contrast, the following example shows that J-dynamics can reach this state even if it is not a PNE. Example 3. Let C = {a, b, c, d}, and suppose that a b c d and voters /candidates preferences are given by

P V = (abcd, bcda, cdab, dabc),

P C = (a : abcd, b : bcda, c : cdab, d : dabc).

Observe that {d} {c, d} {b, c, d} {a, b, c, d} is a J-dynamics for this proﬁle, and its ﬁnal state is not a PNE. Proposition 5 and Example 3 further illustrate that the set of terminal states of Wand J-dynamics may differ from the set of PNE of a given LSCG. Finally, we can show that deciding whether either of our dynamics can terminate in a state with a given winner/set of actual candidates is NP-hard; the proof is obtained by modifying the construction in the proof of Theorem 1 and is omitted due to space constraints. Theorem 2. Given an LSCG game ΓL, a candidate c and a state s of ΓL, the following problems are NP-complete: deciding whether J-dynamics may converge to s; deciding whether W-dynamics may converge to s; deciding whether J-dynamics may converge to a state s with w(s ) = c; deciding whether W-dynamics may converge to a state s with w(s ) = c.

5 Related Work and Discussion Early work on strategic candidacy games [Dutta et al., 2001; 2002; Ehlers and Weymark, 2003; Eraslan and Mc Lennan, 2004; Rodriguez-Alvarez, 2006b; 2006a] focused on voting rules other than Plurality. Vanilla strategic candidate games under Plurality are brieﬂy considered by Lang et al. [2013] and then in more detail by Polukarov et al. [2015]. In particular, Lang et al. argue that any VSCG with three candidates and self-supporting preferences has a PNE, and provide an example of a Plurality-based VSCG with four candidates and no PNE. The ﬁrst of these results stands in contrast with Example 2, where we construct a three-candidate LSCG with no PNE. Polukarov et al. primarily focus on dynamics of VSCGs. However, their model is different from the one considered in Section 4, in that they allow candidates to rejoin an election after having withdrawn. Their results imply that the problems of checking whether a given VSCG has a PNE, or, more narrowly, a PNE with a speciﬁc winner (i.e., the vanilla analogues of LAZY NE and LAZY WNE) are NP-complete. These results together with the analysis in our paper indicate that VSCGs and LSCGs are broadly similar: in both, Condorcet winners can win in PNE under mild additional assumptions, and computational problems related to PNE of both types of games are NP-hard. However, Example 2 points to a crucial difference: laziness may destroy stability. Intuitively, the impact of laziness can be quite substantial, as illustrated by the following simple probabilistic argument.

Consider a strategic candidacy game with C = {a, b, c} and P C = (a : abc, b : bca, c : cab). We will argue that if voters preferences are drawn uniformly at random, then with probability at least 1/2 the proﬁle s = (1, 1, 1) is a PNE of the respective VSCG; however, it is not a PNE of the respective LSCG. Indeed, assume without loss of generality that w(s) = a. Then a and c cannot beneﬁt from withdrawing, and b only wants to withdraw if the number of bca-voters is larger that the number of bac-voters. As voters who rank b ﬁrst are equally likely to be bac-voters or bca-voters, the ﬁrst claim follows. For the second claim, note that b prefers to withdraw from s. Extending the analysis in the example above to estimate the frequency of proﬁles that admit PNE (or, more narrowly, have s = (1, . . . , 1) as PNE), both for vanilla and for lazy strategic candidacy games, is an interesting direction for future work; however, Theorem 1 and the hardness results of Polukarov et al. indicate that this may be a difﬁcult problem. In this context, it may be interesting to note that, in contrast, Plurality voting games with lazy voters and lexicographic tie-breaking are known to have a very simple structure: in PNE of such games at most one voter casts his vote, and all other voters abstain. On the other hand, when voters are not lazy, there are PNE with many voters [Elkind et al., 2014]. Thus, the similarity between VSCGs and LSCGs should not be taken for granted.

6 Conclusions and Future Work

We have introduced strategic candidacy games with lazy candidates and analyzed the properties of their PNE. In contrast with much of the previous work, we explicitly examined the role of the assumption that candidates preferences are selfsupporting, as well as the impact of the tie-breaking order: for instance, Proposition 1 indicates that we need to take these into account when asking whether Pareto-dominated candidates can appear in PNE of LSCGs. As argued in Section 5, it would be interesting to obtain quantitative results regarding frequency of proﬁles with PNE in LSCGs and VSCGs; in particular, it is important to know whether the proﬁle s with A(s) = C is considerably less likely to be stable in LSCGs compared to VSCGs. Further, our model implicitly assumes that for each candidate the campaign costs are small: a candidate is willing to participate even if all that it accomplishes is changing the outcome from his 8th most preferred candidate to his 7th most preferred candidate. Alternatively, we could explicitly model both participation costs and utilities from each outcome, and allow for the possibility that some of the changes in the election outcomes are not signiﬁcant enough to justify participation. While this model is richer than the one we have considered, for large enough costs, the associated computational problems may become simpler, as in all but a handful of situations most of the candidates would prefer to withdraw.

Acknowledgments

This work was partially supported by the European Research Council under the European Union s Seventh Framework

Programme (FP7/2007-2013) / ERC grant agreement number 337122, RFFI 14-01-00156-a, and STSM Grant from the COST Action IC1205.

References [Brill and Conitzer, 2015] M. Brill and V. Conitzer. Strategic voting and strategic candidacy. In AAAI 15, pages 819 826, 2015. [Desmedt and Elkind, 2010] Y. Desmedt and E. Elkind. Equilibria of plurality voting with abstentions. In ACM EC 10, pages 347 356, 2010. [Dutta et al., 2001] B. Dutta, M. L. Breton, and M. O. Jackson. Strategic candidacy and voting procedures. Econometrica, 69:1013 1037, 2001. [Dutta et al., 2002] B. Dutta, M. L. Breton, and M. O. Jackson. Voting by successive elimination and strategic candidacy in committees. Journal of Economic Theory, 103:190 218, 2002. [Ehlers and Weymark, 2003] L. Ehlers and J. A. Weymark. Candidate stability and nonbinary social choice. Economic Theory, 22(2):233 243, 2003. [Elkind et al., 2014] E. Elkind, E. Markakis, S. Obraztsova, and P. Skowron. Equilibria of plurality voting: Lazy and truth-biased voters. Arxiv abs/1409.4132, 2014. [Eraslan and Mc Lennan, 2004] H. Eraslan and A. Mc Lennan. Strategic candidacy for multivalued voting procedures. Journal of Economic Theory, 117(1):29 54, 2004. [Gonzalez, 1984] T. F. Gonzalez. Clustering to minimize the maximum intercluster distace. Theoretical Computer Science, 38:293 306, 1984. [Lang et al., 2013] J. Lang, N. Maudet, and M. Polukarov. New results on equilibria in strategic candidacy. In SAGT 15, pages 13 25, 2013. [Niedermeier, 2006] R. Niedermeier. Invitation to Fixed Parameter Algorithms. Oxford University Press, 2006. [Polukarov et al., 2015] M. Polukarov, S. Obraztsova, Z. Rabinovich, A. Kruglyi, and N. Jennings. Convergence to equilibria in strategic candidacy. In IJCAI 15, 2015. [Rodriguez-Alvarez, 2006a] C. Rodriguez-Alvarez. Candidate stability and probabilistic voting procedures. Economic Theory, 27(3):657 677, 2006. [Rodriguez-Alvarez, 2006b] C. Rodriguez-Alvarez. Candidate stability and voting correspondences. Social Choice and Welfare, 27(3):545 570, 2006. [Tideman, 1987] N. Tideman. Independence of clones as a criterion for voting rules. Social Choice and Welfare, 4(3):185 206, 1987.