# Strategic Candidacy Equilibria for Common Voting Rules

Jérôme Lang, Nicolas Maudet, Maria Polukarov, Alice Cohen-Hadria

► To cite this version:

Jérôme Lang, Nicolas Maudet, Maria Polukarov, Alice Cohen-Hadria. Strategic Candidacy Equilibria for Common Voting Rules. Theory of Computing Systems, 2025, 69 (2), pp.23. 10.1007/s00224-025-10220-3. hal-05117445

HAL Id: hal-05117445

https://hal.science/hal-05117445v1

Submitted on 17 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Strategic Candidacy Equilibria
for Common Voting Rules *

Jérôme Lang¹, Nicolas Maudet², Maria Polukarov³, and Alice Cohen-Hadria⁴

1 CNRS, Paris-Dauphine University, PSL, Paris, France
lang@lamsade.dauphine.fr

2 Sorbonne Université, CNRS, LIP6, Paris, France
nicolas.maudet@lip6.fr

3 King's College London, United Kingdom
maria.polukarov@kcl.ac.uk

4 IRCAM, Sorbonne Université
alice.cohenhadria@ircam.fr

**Abstract.** In strategic candidacy games, both voters and candidates have prefer-ences over possible election outcomes, and candidates may strategically choose to join or leave the election. Following the model by Dutta *et al.* [15, 16], this pa-per presents a first systematic analysis of such games for a list of common voting procedures. We address the question of whether such games possess a pure strat-egy Nash equilibrium in which the outcome is the same as if all candidates run (which we call genuine equilibria). We give a number of negative results: unless the number of candidates is small (less than 3, 4 or 5, depending on the voting rule), there may be games without such stable outcomes. When the existence of genuine equilibria is not guaranteed, we also consider a weaker stability version, namely the existence of a pure strategy Nash equilibrium. Although most of our results are on the negative side, we identify one prominent rule that guarantees the existence of a genuine equilibrium, for any number of candidates, and for an odd number of voters: the Copeland rule. However, strong equilibria, where no coalition of candidates has a profitable collective deviation, are not guaranteed to exist, for almost any voting rule, including Copeland. Finally, we establish for the first time a strong relationship between equilibria of candidacy games and a form of voting control by adding or removing candidates, where candidates must consent to addition or deletion, and we initiate the study of resistance to this new version of control in elections.

# 1 Introduction

Voting mechanisms (or, rules) are a common tool for making collective decisions by aggregating the preferences of concerned agents. A critical issue for the evaluation (and hence, comparison) of voting rules is their ability to resist various sorts of strategic behavior by the election participants. Strategic behavior can come from the voters re-reporting insincere votes (*manipulation*) or from a third party, typically the chair, acting on the set of voters or candidates (*control*), or on the votes (*bribery*, *lobbying*). However, strategic behavior by the candidates has received very little attention compared to

<footnote>* A (very) preliminary version of this paper was presented at SAGT-2013 [29].</footnote>
that by the voters and (to a lesser extent) by the chair: one form thereof involves choosing optimal political platforms, while another simply reflects the ability of candidates to strategically decide whether to run for the election or withdraw. In this paper, we focus on this latter form of strategic behavior by the candidates.

Table 1 below gives a summary of strategic behavior in elections, split into two dimensions corresponding to types of the agents that act strategically and whether their strategic action impacts voters, votes, or candidates.<fnref n="1" />

<table><caption>**Table 1.** Strategic behavior in elections. Rows correspond to types of strategic agents, columns indicate the direction of strategic action.</caption><thead><tr><th>impact →<br>agents ↓</th><th>voters</th><th>votes</th><th>candidates</th></tr></thead><tbody><tr><th>voters</th><td>strategic abstention</td><td>manipulation</td><td>-</td></tr><tr><th>third party / chair</th><td>voter control</td><td>bribery, lobbying</td><td>candidate control,<br>cloning</td></tr><tr><th>candidates</th><td>-</td><td>-</td><td>strategic candidacy</td></tr></tbody></table>

Strategic candidacy often occurs in real-life scenarios, both in large-scale political elections and in small-scale, low-stake elections. In the political arena, perhaps the most typical example of strategic candidacy is due to the high vulnerability of the voting rules in use (typically, plurality or plurality with runoff) to *cloning* [41]. A *spoiler* is a candidate *c* whose platform is close enough to that of another (more important) candidate *c'*, and who will “steal” enough votes from the supporters of *c'* to prevent their victory. Strategic candidacy can occur in both directions: spoiler candidates can be encouraged to run by the competitors of *c'*, or (more often) they can be encouraged to withdraw by the promoters of *c'* to help them win. As an example, in the 2017 presidential election in France (where the voting rule was plurality with runoff), centrist candidate Bayrou withdrew to help Macron qualify to the second round (successfully), and green candidate Jadot withdrew to help the socialist candidate Hamon qualify (not successfully).

In low-stake contexts, strategic candidacy is even more frequent. On electronic democracy platforms, candidates are typically suggested by citizens or groups of citizens, who also have the power to withdraw them.<fnref n="2" /> We are also aware of the chair elections for research or teaching departments in an academic institution where the set

<footnote n="1">¹ This classification is not complete, as there are other types of strategic behavior such as, e.g., *agenda control* (by the chair), but we exclude these for the sake of brevity. There are also some forms of strategic behavior that are specific to multiwinner elections such as *gerrymandering* (by the chair) – see [7] for a recent survey – or *vote pairing/swapping* (by the voters) [3, 13]. This paper, however, only addresses single-winner elections.</footnote>

<footnote n="2">² A well-documented example (prior to the electronic age) is the vote for the choice of the name of the City of Thunder Bay. Quoting Wikipedia (https://en.wikipedia.org/wiki/Thunder_Bay#Amalgamation), its name was the result of a referendum held previously on 23 June 1969, to determine the new name of the amalgamated Fort William and Port Arthur. Officials debated over the names to be put on the ballot, taking suggestions from residents</footnote>
of candidates kept evolving until it stabilized (sometimes, to a singleton). Moving away
from single-winner elections, strategic candidacy also occurs in committee elections,
such as in the board of scientific associations: if the number of candidates related to a
particular subfield is too low, more candidates have an incentive to run, while if it is too
high, some have an incentive to withdraw.

Against this background, we consider a setting with a finite set of *potential candidates*
(which we simply call *candidates* when this is not ambiguous), where:

(1) each candidate may choose to run or not for the election;

(2) each candidate has a preference ranking over the candidates;

(3) each candidate places themselves on the top of their ranking;

(4) the candidates' preferences are common knowledge among them;

(5) the outcome of the election as a function of the set of candidates who choose to
participate, is common knowledge among the candidates.

These features are part of the original model by Dutta *et al.* [15], which we discuss below. Assumption (2) amounts to saying that a candidate only cares about who wins the election,<fnref n="3" /> and has no indifferences or incomparabilities. Assumption (3) (considered as a domain restriction in [15]; still, their main result holds even under this restriction) is natural in most contexts; and, as noted in [15], without such a domain restriction, there may be extreme cases where all candidates prefer to exit. Assumptions (4) and (5) are common game-theoretic assumptions: note that we do not have to assume that the candidates know precisely how voters will vote, nor even the number of voters who participate in the election; all they need to know is the choice function mapping every subset of candidates (the runners) to a winner of the election. In fact, assumption (4) is only required when strong equilibria are considered.

*Related work on strategic candidacy.* Existing work on strategic candidacy is rather scarce. Dutta *et al.* [15] formulate the strategic candidacy game and prove that no non-dictatorial voting procedure satisfying unanimity is candidacy-strategyproof (or equivalently, that for any non-dictatorial and unanimous voting procedure, there is a profile for which the joint action where all candidates enter the election is not stable). In [16], Dutta *et al.* study the implications of strategic candidacy on binary tree voting, and as a particular case, voting by successive elimination with sophisticated voters. For sophisticated voting by successive elimination, they show that the candidacy game always possess a pure strategy Nash equilibrium. For sophisticated binary tree voting, they show that the set of winners in some Nash equilibrium when candidates’ preferences vary is contained in the top cycle, and contains the genuine winner. (However, for fixed candidate preferences, the existence of a pure strategy Nash equilibrium for the candidacy game is an open question.) A more detailed, technical comparison of our results with the results in [15, 16] is exposed in Section 2.3.

<footnote>including “Lakehead” and “The Lakehead”. Predictably, the vote split between the two, and
“Thunder Bay” was the winner.</footnote>

<footnote n="3">³ In some contexts, candidates may have more refined preferences that bear, for instance, on the number of votes they get, how their score compares to that of other candidates, etc. We do not consider these issues here.</footnote>
Some of these results are discussed further (together with simpler proofs) by Ehlers and Weymark [17], and extended to voting correspondences by Ereslan [19] and Rodriguez [37], and to probabilistic voting rules by Rodriguez [36].

Studying the equilibria of a candidacy game helps predicting the set of actual candidates and therefore the outcome of the vote. However, little was known about this from earlier research, like for instance whether such equilibria always exist for common voting rules such as plurality, Borda or Copeland.

A systematic analysis of candidacy games under common classes of voting mechanisms has only started a few years later with our SAGT paper that was a preliminary version of this work [29]. Subsequent papers on strategic candidacy propose different variants of the model and explore the conditions for equilibrium existence, as well as its reachability by iterative dynamic processes. Brill and Conitzer [6] extend the analysis to the setting where both candidates and voters act strategically, but focus on two special cases: namely, of majority-consistent voting with single-peaked preferences and of voting by successive elimination. Polukarov et al. [35] study equilibrium dynamics in candidacy games, where candidates may strategically decide to enter the election or withdraw their candidacy in each iteration of the process until (and if) it converges to a stable state. Obraztsova et al. [33] analyze strategic candidacy games with so called lazy candidates, whose utility function results form the outcome of the election minus a small penalty for running for election. Obraztsova et al. [34] extend the candidacy game model to the setting of multiwinner elections, where the goal is to select a fixed-size subset of candidates (a committee), rather than a single winner. Sabato et al. [40] introduce what they term real candidacy games where candidates have a continuous range of positions that affect their attractiveness for voters and also have their own non-trivial preferences over the candidate set.

Finally, two lines of work that are somewhat related to strategic candidacy, albeit with notable differences, include the *strategic nomination by parties*, and *Hotelling-Downs games*. Recall that strategic candidacy games assume that candidates are independent and have full power to decide whether to run for the election or not; in strategic nomination by parties [20, 25, 8], the set of potential candidates is clustered into political parties, and that the decision for a candidate to enter the election is decided by their party. In Hotelling-Downs games [28, 14], candidates lie on a left-right political axis, and have to choose which position to adopt on the line. These games have recently been studied on richer structures [31].

*Related work on voting control and cloning.* Strategic candidacy is highly related to a family of problems that have received a great deal of focus in computational social choice: *voting control*. As opposed to manipulation (which is a strategic action performed by voters), control is performed by the chair or the election organizer, who is assumed to have the power to change the structure of the election by adding, deleting or partitioning voters or candidates. The existence of pure strategy Nash equilibria of strong Nash equilibria is highly related to a stronger variant of candidate control, termed
consenting control, whose only difference with the standard version of control is that
candidates have their word to say about being deleted or added.<fnref n="4" />

Constructive control by adding or deleting candidates (where the control action is
successful if some designated candidate wins) was introduced by Bartholdi et al. [2].
Hemaspaandra et al. [26] introduce more control types, including destructive control
(where the control action is successful if some designated candidate does not win). For
each control type *T*, voting rules can be partitioned into those (rare) that are immune to
*T* (successful control actions cannot occur), those that are resistant to *T* (deciding the
existence of a successful control action is NP-hard) and those that are vulnerable to *T*
(deciding the existence of a successful control action is in P). See [23] for a survey of
work on the topic until 2016; since then, research has focused on parameterized studies
of resistance to candidate control [9, 12] or sequential candidate control [27].

Candidate cloning [41, 18] also deals with a dynamic set of candidates: given an
initial election with a set of candidates and a profile, cloning of the candidate, say *z*,
into a set of clones *Z* = {*z*₁, ..., *z*ₜ}, results in a new profile where all voters rank all
candidates on *Z* contiguously, and where for each *z*ᵢ ∈ *Z* and *x* ∉ *Z*, a voter prefers *z*ᵢ
to *x* (respectively, *x* to *z*ᵢ) if and only if she prefers *z* to *x* (respectively, *x* to *z*) in the
initial profile. A resolute rule is clone-proof if for any initial profile *P* and profile *P*'
obtained after cloning *z* into a set of clones *Z*, either the winner in *P* is *z* and the winner
in *P*' is in *Z*, or the winner in *P* is *x* ≠ *z* and the winner in *P*' is *x*. When the rule is
not clone-proof, candidate cloning can be a way for the chair to influence the outcome
of an election, and for a candidate to join or to withdraw. As a matter of fact, many
instances of strategic candidacy in the real world are due to a spoiler effect caused by
some candidate having some clones (or quasi-clones). Note that the impact of a cloning
action on the outcome of an election varies largely with the voting rule [18].

Finally, other (albeit somewhat less relevant) works that also consider a dynamic
set of candidates include the computation of possible winners when new candidates
join [10], and the unavailable candidate model [30].

*Contribution.* Following the model by Dutta *et al.* [15, 16], here we give a first sys-
tematic analysis of candidacy games for a list of common voting rules. Our results
demonstrate that voting rules behave very differently with respect to the guarantee of
existence of genuine equilibria and pure strategy Nash equilibria (see Section 2.3 for
formal definitions of these notions and the different degrees of stability in candidacy
games, as well as a more detailed discussion of the results presented in this paper and
their implications). In short, while for most scoring rules, as well as for single trans-
ferable vote and plurality with runoff, there is no such guarantee from four candidates
already, Condorcet-consistent rules offer a more diverse picture. We show, in particu-
lar, that for the Copeland rule, and an odd number of voters, there is always a genuine
pure strategy Nash equilibrium, no matter what the number of candidates is. Other
Condorcet-consistent rules provably ensure the existence of such equilibria for mod-
erate numbers of candidates, but fail to provide a general guarantee. We also prove a

<footnote n="4">⁴ Control by partitioning candidates will not be discussed since it not obviously related to strategic candidacy, and also perhaps less common. We shall not discuss the control on the voters either, although its consenting version looks particularly interesting.</footnote>
simple impossibility theorem showing that strong equilibria are not guaranteed to exist
for a class of voting rules characterized by two natural properties, which are satisfied
by almost any common voting rule. Finally, by exhibiting a strong connection between
the strategic candidacy model and the well-studied problem of control by adding or
deleting candidates, we define the notion of *consenting control* and initiate the study of
resistance to this new version of control in elections.

*Organization.* The paper unfolds as follows. In Section 2, we formally define the framework for strategic candidacy games and state a few preliminary results on their genuine and pure strategy Nash equilibria, which give the basis to a deeper analysis presented in following sections. We start with the special case of three candidates only, for which in Section 3 we present an exact characterization of voting rules that guarantee the existence of a genuine equilibrium. For larger numbers of candidates, we study candidacy games based on common classes of voting rules and demonstrate how they differ with respect to their stability properties: Section 4 deals with positional scoring rules; in Section 5, we focus on the rules based on successive elimination; and finally, Condorcet-consistent rules are analyzed in Section 6. In Sections 7 and 8, we discuss the concept of strong equilibrium in strategic candidacy and relate the model to candidate control. We conclude with discussion in Section 9. This paper comes with a repository<fnref n="5" /> providing the code used to derive some of the results.

## 2 Model and preliminaries

In this section, we formally define the strategic candidacy model in a framework of
ordinal normal form games [24], and present several preliminary observations on their
stability properties. We start with describing a voting setting with strategic candidates
in 2.1; accordingly, in 2.2, we adjust the definitions of common classes of voting rules
to apply to varying subsets of candidates who may strategically choose to run in the
election. The induced game form and related solution concepts are formulated in 2.3;
finally, 2.4 states the preliminary results on stability of candidacy games, useful for their
further analysis in the remainder of the paper.

### 2.1 Setting

Let $X = \{x_1, x_2, \dots, x_m\}$ be a set of *m* potential candidates and $N = \{1, 2, \dots, n\}$ a set of *n* voters so that $X \cap N = \emptyset$. We assume *n* is *odd*, so that pairwise majority ties do not occur: while this is a mild assumption when the number of voters is large, if this implies a loss of generality for any of our results, we shall make it clear.

Unlike in traditional voting settings where candidates merely represent the alterna-
tives for voters to choose from but themselves are assumed to be “unconcerned” about
the outcome of the election (as their opinions about it are not specified), in strategic
candidacy [15] both candidates and voters have explicit preferences over the set of po-
tential candidates, defined for each $i \in X \cup N$ by a linear ordering $\succ_i$ over $X$. As

<footnote n="5">⁵ Available at https://gitlab.lip6.fr/projects/2071</footnote>
in [15], we also assume that the candidates' preferences are self-supporting—that is, each candidate places themselves at the top of their ranking. Let $C = (\succ_c)_{c \in X}$ denote the candidates' preference profile, and let $V = (\succ_v)_{v \in N}$ be the voters' profile.

Depending on their preferences, each candidate may strategically choose to run in the election or withdraw, in which case we shall refer to them as active or idle, respectively. The election outcome is then determined by a voting rule that selects a winner among the active candidates, based on reported voter preferences (or, votes). Note that votes are only submitted by voters, while candidates' preferences play the role in their own strategic considerations regarding entering the race.

Traditionally, voting rules are defined for a fixed set of candidates; in strategic candidacy though, the set of active candidates to which they are applied may vary, so we extend the definition to an arbitrary subset of the set of potential candidates. We say that for any $Y \subseteq X$, a $Y$-vote is a linear ordering over $Y$, and a $Y$-profile $P$ is a collection of $n$ such $Y$-votes. A (resolute) voting rule maps every $Y$-profile, for every $Y \subseteq X$, to a candidate in $Y$. We shall only consider rules which are resolute: formally, we shall first define their irresolute version, and then break the ties according to a fixed priority relation over the candidates, which is given by the restriction of a linear ordering on the whole set of potential candidates $X$, projected to $Y$ such that: if $a$ is prioritized over $b$ (denoted $a \succ b$) in $X$, then $a$ is prioritized over $b$ in any $Y \subseteq X$ containing $a$ and $b$.

We assume that voters are sincere; thus, when the set of active candidates is $Y \subseteq X$, each voter $v$ reports the restriction of $\succ_v$ to $Y$, and the obtained $Y$-profile $P$ is the restriction of $V$ to $Y$, denoted by $V^{\downarrow Y}$. For a given voter profile $V$, a voting rule $r$ can then be seen as a mapping of each $Y \subseteq X$ to a winner $r(V^{\downarrow Y})$ in $Y$. We use the notation $Y \mapsto_{V,r} x$, or simply $Y \to x$ when there is no ambiguity, to state that the outcome of rule $r$, applied to profile $V$, restricted to the subset of candidates $Y \subseteq X$, is $x$.

## 2.2 Voting rules

We now list the common classes of voting rules studied in this work, and adjust their definitions to accommodate varying sets of active candidates. Recall that $|X| = m$, and for any $Y \subseteq X$ let $|Y| = k$ where $k \le m$.

*Scoring rules.* A scoring rule is defined by a collection of vectors $S_k = (s_1, \dots, s_k)$ for all $k \le m$, with $s_1 \ge s_2 \ge \dots \ge s_k$ and $s_1 > s_k$. For each $k \le m$ and each $i \le k$, $s_i$ is the number of points given to a candidate ranked in position $i$, and the winning candidate(s) maximize(s) the sum of points received from all $n$ votes. Formally speaking, defining a family of scoring rules requires to specify a scoring vector for each size $k \le m$ of an active candidate set (for instance, $\langle 3, 1, 0 \rangle$ for three candidates, $\langle 4, 3, 2, 0 \rangle$ for four candidates, and so on). However, for the most popular scoring rules, these collections of vectors are defined in a natural way:

- plurality: $S_k = \langle 1, 0, \dots, 0 \rangle$;

- veto (or antiplurality): $S_k = \langle 1, \dots, 1, 0 \rangle$;

- Borda: $S_k = \langle k-1, k-2, \dots, 1, 0 \rangle$.
**Condorcet-consistent rules.** For any $Y \subseteq X$, let $P$ be a $Y$-profile and $N_P(c, x)$ be the number of votes in $P$ who rank $c$ above $x$. The majority graph $M(P)$ associated with $P$ is a graph whose vertices are the candidates in $Y$, with an edge from $x$ to $y$ whenever $N_P(x, y) > \frac{n}{2}$ (in which case we say that $x$ beats $y$ in $M(P)$, denoted by $x \to_P y$). Since $n$ is odd, $M(P)$ is a tournament, i.e., a complete asymmetric graph. A candidate $c$ is a **Condorcet winner** if $c \to_P y$ for all $y \neq c$. A voting rule $r$ is **Condorcet-consistent** if $r(P) = \{c\}$ whenever there exists a (unique) Condorcet winner $c$ for $P$. A candidate $c$ is a **Condorcet loser** if $y \to_P c$ for all $y \neq c$.

Given a $Y$-profile $P$, the *top cycle* $TC(P)$ is the smallest set $S \subseteq Y$ such that for every $x \in S$ and $y \in Y \setminus S$, $x \to_P y$. The *uncovered set* $UC(P)$ is the set $S \subseteq Y$ of candidates such that for any $c \in S$ and for any other candidate $x$, if $x \to_P c$ then there is some $y$ such that $c \to_P y$ and $y \to_P x$. The *maximin* rule chooses the candidate(s) $c$ that maximize(s) $\min_{x \in Y \setminus \{c\}} N_P(c, x)$. The *Copeland* rule chooses the candidate(s) $c$ that maximize(s) $|\{x \in Y | c \to_P x\}|$.

**Majority-consistent rules.** A rule is called *majority-consistent* if it selects a majority winner (i.e., a candidate which is ranked first by a majority of voters) when one exists; for two candidates only, such rule coincides with majority.

*Rules based on successive elimination of candidates.* Plurality with runoff proceeds in two rounds: we first select the two candidates $x$ and $y$ with highest plurality scores, and then choose the majority winner between the two. *Single transferable vote (STV)* proceeds in $k-1$ rounds: at each round, the candidate with the lowest plurality score among the remaining candidates (using tie-breaking if necessary) is eliminated.

## 2.3 Game-theoretic formulation

*Strategic candidacy games.* Each voting rule $r$ induces a natural *game form*, where the set of players is given by the set of potential candidates $X$, and the strategy set available to each player is $\{0, 1\}$ with 1 corresponding to entering the election and 0 standing for withdrawal of candidacy. A *state* $s$ of the game is a vector of strategies $(s_c)_{c \in X}$, where $s_c \in \{0, 1\}$. For convenience, we use $s_{-z}$ to denote $(s_c)_{c \in X \setminus \{z\}}$—i.e., $s$ reduced by the single entry of player $z$. Similarly, for a state $s$ we use $s_Z$ to denote the strategy choices of a coalition $Z \subseteq X$ and $s_{-Z}$ for the complement, and we write $s = (s_Z, s_{-Z})$.

The outcome of a state $s$ is $r(V^\downarrow Y)$ where $c \in Y$ if and only if $s_c = 1$.6 Coupled with a voter profile $V$ and a candidate profile $C$, this defines an *ordinal normal form game* $\Gamma = (X, V, r, C)$ with $m$ players.<fnref n="7" /> Here, player $c$ prefers outcome $\Gamma(s)$ over outcome $\Gamma(s')$ if ordering $\succ_c$ ranks $\Gamma(s)$ above $\Gamma(s')$.

<footnote n="6">⁶ When clear from the context, we use notation $s$ to also indicate the set of active candidates $Y$ that corresponds to state $s$: e.g., for $X = \{x_1, x_2, x_3\}$, we use $(1, 0, 1)$ and $\{x_1, x_3\}$ interchangeably; we also generally omit curly brackets and write $x_1x_3$ instead of $\{x_1, x_3\}$.</footnote>

<footnote n="7">⁷ See [24] for discussion of ordinal preference models versus traditional cardinal expressions of preference and particularly, their representation based on an ordinal normal form game.</footnote>
*Related solution concepts.* Having defined a normal form game, we can now apply standard game-theoretic solution concepts. Let $\Gamma = \langle X, V, r, C \rangle$ be a candidacy game, and let $s$ be a state in $\Gamma$. We say that a coalition $Z \subseteq X$ has an improving move in $s$ if there is $s'_Z$ such that $\Gamma(s_Z, s'_Z)$ is preferred to $\Gamma(s)$ by every $z \in Z$. In particular, the improving move is unilateral if $|Z| = 1$. A state is a pure strategy Nash equilibrium (PSNE)<fnref n="8" /> if it has no unilateral improving moves, and a k-PSNE if no coalition $Z$ with $|Z| \le k$ has an improving move. A strong equilibrium (SE) [1] is an n-PSNE, that is, a state with no improving moves by any coalition.

The concept of strong equilibrium captures stability not only at the individual level but also against coalitions of candidates. While a pure strategy Nash equilibrium ensures that no single candidate has an incentive to deviate unilaterally, it does not prevent groups of candidates from benefiting by coordinating their actions. In contrast, strong equilibrium provides a more robust solution concept in candidacy games, where candidates might have both individual and collective incentives to alter their strategies. Thus, it offers a stricter criterion for stability, making it particularly relevant in scenarios where cooperation or collusion among candidates is possible.

Furthermore, to evaluate the effects of strategic behavior in the specific context of candidacy games, we are interested in solution concepts indicating whether strategic candidacy can effectively change the election winner. We say that a candidate $w$ is a genuine winner if it gets elected when all candidates run; that is, $w = r(V)$. A state $s$ is called genuine if its outcome is genuine; that is, if $r(V^{\downarrow s}) = r(V)$. A genuine state $s$ which is also a PSNE is called a genuine PSNE.

The following Example 1 illustrates these notions. The first row in $V$ indicates the number of voters casting different ballots, which are presented in the corresponding columns, with the topmost candidate being preferred. The candidates' preferences $C$ are detailed in a similar way.

*Example 1.* Consider game $\Gamma = \langle abcd, V, r, C \rangle$ with 4 potential candidates, where $r$ is the Borda rule (with an arbitrary tie-breaking relation) and $V$ and $C$ are given as follows:

<table><thead><tr><th>V</th><th>C</th></tr></thead><tbody><tr><td>1 1 1 1 1 1</td><td>a b c d</td></tr><tr><td>b c c a d b a</td><td>a b c d</td></tr><tr><td>d d d c a c b</td><td>d a b a</td></tr><tr><td>a a b b c d c</td><td>b d a c</td></tr><tr><td>c b a d b a d</td><td>c c d b</td></tr></tbody></table>

The state (1,1,1,1) is not a PSNE: $abcd \mapsto c$, but $abc \mapsto a$, and $d$ prefers $a$ to $c$, so for $d$, leaving is an improving move. Now, (1,1,1,0) is a PSNE, as no one has an improving move neither by joining ($d$ prefers $a$ over $c$), nor by leaving (obviously, not $a$; if $b$ or $c$ leaves then the winner is still $a$). It can be checked that this is also an SE. It is however not a genuine PSNE, since the winner is $a$ whereas the winner in state $abcd$ is $c$.

*Degrees of stability.* There is a hierarchy of stability properties of particular interest in the context of candidacy games. Previous work has made some important initial steps towards their exploration, that motivated the systematic analysis we offer in this paper. Below, we list these properties and outline the respective results.

<footnote n="8">⁸ Also referred to as entry equilibrium in the context of strategic candidacy [15].</footnote>
1. Candidate Stability (CS): the set of all candidates is a (clearly, genuine) PSNE.

2. Entry Equilibrium Stability (EES): there exist PSNE, and all of them are genuine.

3. Convergence to Genuine Equilibrium (CGE): from the initial state where all candidates run, there is a deviation path towards a genuine PSNE.

4. Existence of Genuine Equilibrium (EGE): there always exists a genuine PSNE.

5. Convergence to Equilibrium (CE): from the set of all candidates there is a deviation path towards a PSNE.

6. Existence of Equilibrium (EE): the existence of a PSNE is guaranteed.

The first two properties, CS and EES, were considered in [15], and we follow their original terms referring to them. The convergence properties, CE and CGE, are relaxations of the notion of weak acyclicity that requires the existence of an improving path leading to a stable state (usually, PSNE, but here we also consider genuine PSNE) from any initial state, while we have a designated initial state.<fnref n="9" /> These properties can be seen as a weak form of implementability in the mechanism design sense. Finally, the existence of a stable state (again, usually of PSNE or SE, but here we extend consideration to genuine PSNE) is one of the fundamental questions studied in game-theoretic analysis, and most of our results are also about EE and EGE.

Now, for scenarios where the sets of candidates and voters do not intersect (which is the case in our setting), it was shown in [15] that EES implies CS. We thus have the following implications:

$$ - EES \Rightarrow CS \Rightarrow CGE \Rightarrow EGE \Rightarrow EE $$

$$ - EES \Rightarrow CS \Rightarrow CGE \Rightarrow CE \Rightarrow EE $$

Note that EGE and CE are incomparable: for illustration, recall Example 1 where there exists a deviation path to a non-genuine PSNE, regardless of whether genuine equilibria may or may not exist in the game.

Dutta et al. [15] focus on CS and EES and observe that such high degrees of stability cannot be expected from any non-dictatorial voting rule satisfying unanimity.<fnref n="10" /> In their follow-up paper [16], they also consider EE, and exhibit one voting rule that satisfies it: namely, sophisticated voting by successive elimination. As for EGE, it was mentioned in [15] (page 14, condition (i)), however, a more systematic study of EE and EGE is left for further research, which is what we do in this work.

Our main result shows EGE for Copeland with any number of candidates, and for other rules we show that the property holds for small sizes of candidate sets. Note that EGE is a stronger notion of stability than EE and, arguably, more desirable, as it means that there exists a stable candidacy configuration, under which the original winner is preserved. However, whenever EE holds in the absence of EGE, this means that strategic candidacy can effectively change the election outcome, which in certain situations

<footnote n="9">⁹ See [32] for the formal definitions of different degrees of acyclicity in normal form games, and their analysis in settings with strategic voters.</footnote>

<footnote n="10">¹⁰ This, however, is in contrast with settings with approval-based votes, for which, in the context of multi-winner elections, Obraztsova et al. [34] identify classes of voting rules that satisfy both CS and EES (in which case, they term the respective candidacy game genuine), as well as families of rules, for which CS but not EES holds (which is in contrast with the result of [15] showing that EES implies CS in the ordinal (and single-winner) setting).</footnote>
(for instance, in scenarios with highly polarized populations of voters) may in fact be
desirable.<fnref n="11" /> Further, negative results on EE are also important, as they imply negative
results on EGE and generally, indicate the susceptibility of the voting procedure to
strategic candidacy. Indeed, our work demonstrates that for most of the common voting
rules we can only expect stability of small candidate sets. This, clearly, also refutes the
possibility to reach such states from the initial candidacy configuration, so positive re-
sults about CGE and CE are hard to hope for (and indeed, we show negative result even
for Copeland where, as we prove, EGE does hold). A natural question is then to decide
whether an equilibrium outcome exists, and can be reached, in a particular instance of
a candidacy game, and consider the computational complexity of respective decision
problem, in spirit of the analysis done in [35] for the special case of plurality.

Our storyline is the following:

- From [15], we know that in general, candidacy games are helplessly unstable.

- However, we can obtain positive results under strong domain restrictions such as Condorcet domains (under which Condorcet-consistent rules are stable).

- We also explore another way of obtaining positive results: we do not assume any domain restriction but consider specific classes of voting rules separately.

- On the positive side, we identify a natural voting rule (Copeland) for which EGE is guaranteed to exist for an arbitrary number of candidates; for other rules we show positive results only for low numbers of candidates (between 3 and 6); on the negative side, we obtain a number of negative results for EE (and hence, EGE).

**2.4 Preliminary results**

Regardless of the number of voters and the voting rule used, a straightforward observa-
tion is that a candidacy game with $m = 3$ always admits a PSNE. Moreover, for this
case we are also able to provide an exact characterization of voting rules that guarantee
the existence of a genuine equilibrium (see Section 3).

For $m > 3$ candidates, we find examples of games without equilibria, and the first
question that comes to mind is whether they can be easily adapted to transfer these
results to larger sets of candidates. The following Lemma 1 shows that they do indeed,
under a really mild assumption. We say that a voting rule is *insensitive to bottom-ranked
candidates* (IBC) if given any $Y$-profile $P$ over $Y \subseteq X$ with $|Y| = k \le m$, if $P'$ is the
profile over $Y \cup \{x_{k+1}\}$ obtained by adding $x_{k+1}$ at the bottom of every vote in $P$, then
$r(P') = r(P)$. This property is extremely weak (much weaker than Pareto efficiency)
and is satisfied by almost all common voting rules.

**Lemma 1.** For any voting rule $r$ satisfying IBC, if there exists a candidacy game $\Gamma = \langle X, V, r, C \rangle$ with no (genuine) PSNE, then there is also a game $\Gamma' = \langle \tilde{X}', V', r, C' \rangle$ with no (genuine) PSNE where $|\tilde{X}'| = |X| + 1$.

<footnote n="11">¹¹ For instance, in the 2024 French legislative elections, strategic withdrawing has prevented the election of more than 100 far-right candidates.</footnote>
*Proof.* Take a candidacy game $\Gamma$ with the set of potential candidates $X = \{x_1, \dots, x_m\}$, and let $X' = X \cup \{x_{m+1}\}$, $V'$ be the voter profile obtained from $V$ by adding $x_{m+1}$ at the bottom of every vote, and $C'$ be the candidate profile obtained by adding $x_{m+1}$ at the bottom of every ranking of a candidate $x_i$, $i \le m$, and whatever ranking for $x_{m+1}$.

Assume $\Gamma$ has no PSNE. Let $Y \subseteq X$. Since $Y$ is not a PSNE for $\Gamma$, there is some candidate $x_i \in X$ that has an interest to either leave or join the election, and so $Y$ is also not a PSNE for $\Gamma'$. Furthermore, since $r$ satisfies IBC, such candidate $x_i \in X$ will have an incentive to also leave (resp., join) $Y' = Y \cup \{x_{m+1}\}$, as the winner in $Y' \setminus \{x_i\}$ (resp., $Y' \cup \{x_i\}$) is the same as in $Y \setminus \{x_i\}$ (resp., $Y \cup \{x_i\}$), and so $Y'$ is not a PSNE either. Therefore, $\Gamma'$ has no PSNE in such case.

Now assume that $Y$ is a non-genuine PSNE for $\Gamma$. Then, no candidate $x_i \in X$ wants to leave or join $Y$, and candidate $x_{m+1}$ has no interest to join as their presence will not affect the outcome due to IBC. Moreover, $Y' = Y \cup \{x_{m+1}\}$ yields the same, non-genuine, outcome as $Y$, and due to IBC no candidate $x_i \in X'$ has an incentive to deviate, so both $Y$ and $Y'$ are non-genuine PSNE for $\Gamma'$. Coupled with the above arguments regarding non-PSNE states of $\Gamma$, we get that $\Gamma'$ has no genuine PSNE. $\square$

We shall use this induction lemma to extend some of our negative results to an arbitrary number of candidates. A noticeable exception is the veto rule, which does not satisfy IBC. In the appendix, we provide a specific lemma to handle this rule.

Unlike genuine and pure strategy equilibria, strong equilibria are not guaranteed even for games with $m = 3$ candidates, as we show in Section 7. However, there are positive results for some families of voting rules or restricted preference profiles. Brill and Conitzer [6] prove that under the assumption of single-peaked preferences, if the voting rule is majority-consistent, then the candidacy game has an SE, and in all such equilibria, the winner is the Condorcet winner. Here, we present the following result, that applies to all Condorcet-consistent rules, with any number of candidates.

**Proposition 1.** Let $\Gamma = (X, V, r, C)$ be a candidacy game where $r$ is Condorcet-consistent. If $V$ has a Condorcet winner $c$ then for any $Y \subseteq X$,

$$Y \text{ is a SE} \Leftrightarrow Y \text{ is a PSNE} \Leftrightarrow Y \text{ is a genuine PSNE} \Leftrightarrow c \in Y.$$

The proof of Proposition 1 can be found in the appendix. If the voter profile $V$ has no Condorcet winner, the analysis becomes more complicated. We provide results for this more general case in the following sections.

## 3 Three candidates

We study the case of three candidates separately as here we obtain an exact characterization of voting rules for which the existence of a genuine equilibrium is guaranteed (see Proposition 2). Recall that we assume the number of voters to be odd, to avoid ties.<fnref n="12" />

<footnote n="12">¹² Without this assumption, the following weakening of Proposition 2 holds: a genuine PSNE exists if $r$ never elects a candidate which, in the majority graph, is beaten or tied with any other candidate, and beaten by at least one candidate.</footnote>
**Proposition 2.** Let $\Gamma = \langle X, V, r, C \rangle$ be a candidacy game form where voting rule $r$ is majority-consistent. For $m = 3$ candidates, a genuine PSNE exists for all preference profiles if and only if $r$ never elects a Condorcet loser.

*Proof.* Let $m = 3$ and let the candidates be $a, b, c$.

Assume there is a voter profile $V$ for which there is a Condorcet loser $a$ and $r(V) = a$. We have $abc \mapsto a$ because $r(V) = a, ab \mapsto b, ac \mapsto c$ because $a$ is a Condorcet loser and $r$ is majority-consistent. Assume also that $c$ prefers $b$ to $a$: then, $abc$ is not a PSNE because $c$ prefers to withdraw. The only other state where $a$ wins is the state where only $a$ runs; however, it is not a PSNE because $b$ (and $c$) wants to join.

Assume $r$ never elects a Condorcet loser. Let $V$ be a voter profile. If $V$ has a Condorcet loser $a$ then $r(V) \neq a$. Without loss of generality, assume $r(V) = b$. We have $ab \mapsto b$ because $r$ is majority-consistent. Therefore, $ab$ is a genuine PSNE. If $V$ has no Condorcet loser then because $n$ is odd, the majority graph associated with $V$ has a preference cycle, say $a \to b \to c \to a$. Without loss of generality, assume $r(V) = b$. Then $bc$ is a genuine PSNE. $\square$

# 4 Positional scoring rules

As a corollary of Proposition 2, the only scoring rule for which the existence of a genuine PSNE is guaranteed for games with three candidates $m = 3$, is the Borda rule, as this is the only one that never elects a Condorcet loser. Now we move to $m \ge 4$.

We make use of the powerful result by Saari [38], stating that for almost all scoring rules, any choice function can result from a voting profile. For four candidates [39], we define a Saari rule as a rule for which, when the scoring vector for three candidates is of the form $\langle w_1, w_2, 0 \rangle$, then the vector for four candidates is not $\langle 3w_1, w_1+2w_2, 2w_2, 0 \rangle$. For instance, plurality and veto are Saari rules, but Borda is not a Saari rule.

Now, since for any Saari rule, any choice function can result from a voting profile [38, 39], this means that our question boils down to check whether a choice function, together with some coherent candidates' preferences, can be found such that no PSNE exists for $m = 4$. We answer this question by encoding the problem as an Integer Linear Program (ILP).

It turns out that such choice functions do exist. We depict one such function in Fig. 1, where the outcome of the choice function (the winner in each state) is given in boldface. The arrows in the figure denote deviations, based on the following candidates' preferences:

$a : a \succ b \succ c \succ d$

$b : b \succ a \succ c \succ d$

$c : c \succ d \succ a \succ b$

$d : d \succ a \succ b \succ c$

The next results then follow directly.

**Proposition 3.** For $m = 4$ candidates, if $r$ is a Saari rule, there are candidacy games without pure strategy Nash equilibria.
<figure><img src="image_2.png" /><figcaption>Fig. 1. A choice function without PSNE</figcaption></figure>

**Corollary 1.** For $m = 4$ candidates, for plurality and veto voting rules, there are candidacy games without PSNE.

Note that the result holds more generally for $k$-approval with any $k$. We emphasize that even though Saari's result suggests that counterexamples can be obtained for all these scoring rules, it does not directly provide a profile that would satisfy such a choice function. These profiles may involve a large number of voters. For plurality, we exhibit a profile with 13 voters corresponding to the choice function given in Fig. 1, whose preferences are shown on the left part of the table below. Tie-breaking is lexicographic. The right part of the table represents the candidates' preferences.

<table><tr><td>3</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>2</td><td>2</td><td>a</td><td>b</td><td>c</td><td>d</td></tr><tr><td>d</td><td>d</td><td>d</td><td>a</td><td>a</td><td>a</td><td>b</td><td>b</td><td>c</td><td>a</td><td>b</td><td>c</td><td>d</td></tr><tr><td>c</td><td>b</td><td>a</td><td>b</td><td>c</td><td>d</td><td>c</td><td>a</td><td>b</td><td>b</td><td>a</td><td>d</td><td>a</td></tr><tr><td>a</td><td>c</td><td>b</td><td>c</td><td>b</td><td>b</td><td>d</td><td>c</td><td>d</td><td>c</td><td>c</td><td>a</td><td>b</td></tr><tr><td>b</td><td>a</td><td>c</td><td>d</td><td>d</td><td>c</td><td>a</td><td>d</td><td>d</td><td>d</td><td>b</td><td>c</td></tr></table>

Similar profiles can be obtained for other Saari rules. As for the Borda rule, which is not a Saari rule, it stands as an exception.

**Proposition 4.** For $m = 4$ candidates, for the Borda voting rule, (i) every candidacy game has a PSNE. However, (ii) the existence of a genuine PSNE is not guaranteed.

*Proof.* (i) This result relies on the fact that the outcome of Borda winner can be computed from the weighted majority graph. We create an Integer Linear Program (ILP) aiming at finding a counterexample for Borda: the infeasibility of the resulting set of constraints shows that no instances without PSNE can be constructed.

We now give the details of this ILP. Let $S$ be the set of states, and $A(s)$ be the set of agents who are candidates in state $s \in S$. Note that $|S| = 2^{|X|}$.
*Choice functions with no PSNE.* We introduce a binary variable $w_{si}$, meaning that agent $i$ wins in state $s$. We add constraints enforcing that there is a single winner in each state:

$$ \forall i \in X, \forall s \in S: w_{s,i} \in \{0, 1\} \qquad (1) $$

$$ \forall s \in S: \sum_{i \in X} w_{s,i} = 1 \qquad (2) $$

$$ \forall s \in S, \forall i \in X \notin A(s): w_{s,i} = 0 \qquad (3) $$

Now, we introduce constraints related to deviations. We denote by $D(s)$ the set of possible deviations from state $s$ (state where a single agent's candidacy differs from $s$). We also denote by $a(s,t)$ an agent potentially deviating from $s$ to $t$. We define binary variables $d_{s,t}$ indicating a deviation from state $s$ to state $t$. In each state, there must be at least one deviation, otherwise this state must be a PSNE:

$$ \forall s \in S, \forall t \in S: d_{s,t} \in \{0, 1\} \qquad (4) $$

$$ \forall s \in S: \sum_{t \in D(s)} d_{s,t} \geq 1 \qquad (5) $$

Now we introduce constraints related to the preferences of the candidates. For this purpose, we introduce a binary variable $p_{i,j,k}$, meaning that agent $i$ prefers candidate $j$ over candidate $k$. If there indeed is a deviation from $s$ to $t$, the deviating agent must prefer the winner of the new state compared to the winner of the previous state:

$$ \forall s \in S, \forall t \in D(s), \forall i \in X, \forall j \in X: w_{s,i} + w_{t,j} + d_{s,t} - p_{a(s,t),i,j} \leq 2 \qquad (6) $$

Finally, we ensure that the preferences are irreflexive and transitive, and respect the constraint of being self-supporting:

$$ \forall i \in X, \forall j \in X: p_{i,j,j} = 0 \qquad (7) $$

$$ \forall a \in X, \forall i \in X \forall j \in X, \forall k \in X: p_{a,i,j} + p_{a,j,k} - p_{a,i,k} \leq 1 \qquad (8) $$

$$ \forall i \in X, \forall j \in X: p_{i,i,j} = 1 \qquad (9) $$

*Constraints for Board.* We introduce a new integer variable $N_{i,j}$ to represent the number of voters preferring $i$ over $j$ in the weighted tournament. We first make sure that the values of $N_{i,j}$ are consistent throughout the weighted tournament:

$$ \forall i \in X, \forall j \in X, \forall k \in X, \forall l \in X: N_{i,j} + N_{j,i} = N_{k,l} + N_{l,k} \qquad (10) $$

In each state, when agent $i$ wins, we must make sure that its total amount of points is the highest among all agents in this state (note that $i$ can simply tie with agents it has priority over in the tie-breaking; we omit this for the sake of readability):

$$ \forall s \in S, \forall i \in A(s), \forall k \in A(s) \setminus \{i\}: (1 - w_{s,i}) \times M + \sum_{j \in A(s) \setminus \{i\}} N_{i,j} > \sum_{j \in A(s) \setminus \{k\}} N_{k,j} \qquad (11) $$

Here, $M$ is a large value, used to relax the constraint when $w_{s,i}$ is 0. For this we need to find a large enough value of $M$ such that every choice function that can be obtained for Board and 4 candidates is implementable with a weighted tournament where the largest
value occurring is lower than $M$. To find such an $M$, we first write a computer program that enumerates all such choice functions. Then, for each of these choice functions, write a dedicated MIP which returns the minimum value $N$ occurring in the weighted tournament when it is feasible, or unfeasible otherwise. By calling this MIP for each choice functions (up to symmetries), we retrieve the maximal value required overall).

(ii) To see that there may be no genuine PSNE, consider the following profile.

<table><tr><td>1</td><td>1</td><td>2</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>a</td><td>b</td><td>c</td><td>d</td></tr><tr><td>c</td><td>c</td><td>a</td><td>d</td><td>b</td><td>d</td><td>b</td><td>a</td><td>a</td><td>a</td><td>b</td><td>c</td><td>d</td></tr><tr><td>d</td><td>b</td><td>c</td><td>c</td><td>c</td><td>a</td><td>b</td><td>d</td><td>d</td><td>d</td><td>c</td><td>c</td><td>a</td><td>b</td></tr><tr><td>b</td><td>a</td><td>d</td><td>b</td><td>a</td><td>d</td><td>c</td><td>c</td><td>b</td><td>c</td><td>d</td><td>d</td><td>b</td><td>a</td></tr><tr><td>a</td><td>d</td><td>b</td><td>a</td><td>d</td><td>c</td><td>a</td><td>a</td><td>c</td><td>b</td><td>b</td><td>a</td><td>d</td><td>c</td></tr></table>

The corresponding choice function is detailed below. Tie-breaking is lexicographic.

$$ 
\begin{array}{l@{\quad}l@{\quad}l@{\quad}l}
\mathbf{a} & b+ & \mathbf{ac} & b+ & \mathbf{abc} & a- \\
\mathbf{b} & c+ & \mathbf{ad} & & \mathbf{abd} & c+ \\
\mathbf{c} & d+ & \mathbf{bc} & d+ & \mathbf{acd} & b+ \\
\mathbf{d} & a+ & \mathbf{bd} & a+ & \mathbf{bcd} & a+ \\
& & \mathbf{cd} & a+ & & 
\end{array}
\quad \mathit{abcd} \ d- 
$$

As in Fig. 1, winners are indicated in boldface, and to make the representation more compact, next to each state we just indicate one deviation from this state, where $x+$ (respectively, $x-$) means that $x$ has a profitable deviation by joining (respectively, by leaving) this state. There are only two PSNE $(ab$ and $ad)$ but neither of them is genuine as the Borda winner in the full profile $abcd$ is $c$. $\square$

The existence of PSNE with four candidates makes Borda a noticeable exception from the family of scoring rules, for most of which Proposition 3 implies negative result. However, as Proposition 4 demonstrates, we cannot guarantee the existence of genuine equilibria for Borda with $m = 4$ and, as we show in the following Proposition 5, there is no longer guarantee for the PSNE existence when the number of candidates is $m = 5$.

**Proposition 5.** For the Borda rule with $m = 5$ candidates, there are candidacy games with no pure strategy Nash equilibria.

*Proof.* The following counterexample has been obtained by applying the same ILP technique as described above. We do not specify the voter profile $V$ explicitly, but only give its majority margin matrix in the left part of the table, where the number corresponding to row $x$ and column $y$ is given by $N_V(x, y) - N_V(y, x)$; by Debord's theorem [11], the existence of a profile $V$ realizing this matrix is guaranteed because all elements of the matrix have the same parity. Tie-breaking is irrelevant. The candidates' preference are specified explicitly in the right part of the table. Tie-breaking is irrelevant.
<table><thead><tr><th></th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>a b c d e</th></tr></thead><tbody><tr><th>a</th><td>0</td><td>-3</td><td>-1</td><td>+1</td><td>+3</td><td>a b c d e</td></tr><tr><th>b</th><td>+3</td><td>0</td><td>-5</td><td>+1</td><td>-1</td><td>b a a c c</td></tr><tr><th>c</th><td>+1</td><td>+5</td><td>0</td><td>-5</td><td>-1</td><td>e e d e d</td></tr><tr><th>d</th><td>-1</td><td>-1</td><td>+5</td><td>0</td><td>-3</td><td>c c e a a</td></tr><tr><th>e</th><td>-3</td><td>+1</td><td>+1</td><td>+3</td><td>0</td><td>d d b b b</td></tr></tbody></table>

Below we give the explicit listing of all 31 states, using the same representation as in Proposition 4:

<figure><img src="image_3.png" /></figure>

Alternatively, one can also depict the deviation graph explicitly (see Figure 2). ☐

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /><figcaption>**Fig. 2.** Borda, five candidates: a choice function without NE</figcaption></figure>
Now, we finally move to the general case with an arbitrary number of candidates. For all rules that satisfy IBC and for which we have already found a counterexample for some $m$, we know that counterexamples exist for any number of candidates $m' \ge m$. As we previously noted, veto is an example of a rule not satisfying IBC, but an adapted version of Lemma 1 can easily be derived (see Lemma 2 in the appendix). As a corollary of these, and of Propositions 3 and 5 we thus get:

**Corollary 2.** *There exist profiles with no PSNE in the following cases:*

- For all Saari scoring rules satisfying IBC (including plurality), as well as for veto, for all $m \ge 4$.

- For Borda, for all $m \ge 5$.

**5 Rules based on successive elimination**

Let us now focus on plurality with runoff and single transferable vote (STV). For these rules, it is no longer the case that any choice function can be implemented by such rules. For instance, for plurality with runoff, a necessary condition for the choice function to be implementable is that, for any subset of candidates $Y$ with $|Y| \ge 3$, if $r(V^{\downarrow Y}) = x$, then $x$ must win in pairwise comparison against some candidate $y \in Y \setminus \{x\}$. For STV, even a stronger condition is required: for any subset of candidates $Y$, if $r(V^{\downarrow Y}) = x$, it must be the case that $r(V^{\downarrow Z}) = x$ for some set $Z \subset Y$ such that $|Z| = |Y - 1|$.

We make no claim that these conditions are sufficient to ensure a possible implementation. However, by adding these constraints into our ILP, we generated a choice function that we could in turn implement with a specific profile, thus providing us with the following result.

**Proposition 6.** For $m \ge 4$ candidates, for plurality with runoff and single transferable vote, there are candidacy games without PSNE.

*Proof.* We exhibit a counterexample with 19 voters. Tie-breaking is lexicographic. The corresponding choice function is identical for plurality with runoff and single transferable vote.

<table><tr><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>1</td><td>a</td><td>b</td><td>c</td><td>d</td></tr><tr><td>b</td><td>b</td><td>d</td><td>d</td><td>d</td><td>c</td><td>c</td><td>a</td><td>a</td><td>a</td><td>b</td><td>c</td><td>d</td></tr><tr><td>c</td><td>a</td><td>b</td><td>c</td><td>a</td><td>d</td><td>a</td><td>b</td><td>c</td><td>b</td><td>b</td><td>d</td><td>b</td><td>b</td></tr><tr><td>d</td><td>d</td><td>c</td><td>b</td><td>c</td><td>a</td><td>b</td><td>d</td><td>b</td><td>c</td><td>c</td><td>a</td><td>d</td><td>c</td></tr><tr><td>a</td><td>c</td><td>a</td><td>a</td><td>b</td><td>b</td><td>d</td><td>c</td><td>d</td><td>d</td><td>c</td><td>a</td><td>a</td><td>a</td></tr></table>

We detail the choice function below, with one example deviation per state :

$$ 
\begin{array}{l@{\quad}l@{\quad}l}
\begin{array}{l} ab \ d+ \\ a \ c+ \end{array} & \begin{array}{l} ac \ b+ \end{array} & \begin{array}{l} abc \ d+ \\ a \ c \ d+ \end{array} \\
\begin{array}{l} bd \ c+ \\ b \ c+ \end{array} & \begin{array}{l} ad \ c+ \end{array} & \begin{array}{l} abd \ a- \\ abcd \ a- \end{array} \\
\begin{array}{l} cd \ d+ \\ b \ c \ d+ \end{array} & \begin{array}{l} ac \ d+ \end{array} & \\
\begin{array}{l} bd \ b+ \\ b \ c \ d+ \end{array} & \begin{array}{l} ac \ d+ \end{array} & \\
\begin{array}{l} cd \ a+ \\ b \ c \ a+ \end{array} & \begin{array}{l} bcd \ b- \end{array} & \\
\end{array}
$$
Regrading the general case with an arbitrary number of candidates, we simply note that the rules satisfy IBC. As we have already found a counterexample for 4, we know that counterexamples exist for any number of candidates greater than 4. $\square$

Finally, since plurality with runoff and STV never elect a Condorcet loser, then for $m = 3$ candidates the existence of a PSNE is guaranteed as a corollary of Proposition 2.

# 6 Condorcet-consistent rules

We now turn our attention to Condorcet-consistent rules. First, we show that candidacy games with four candidates, must have a PSNE under any such rule. Recall that we assume the number of voters $n$ to be odd.

**Proposition 7.** For $m = 4$ candidates (and odd number of voters), if $r$ is Condorcet-consistent then every candidacy game has a PSNE.

*Proof.* For any voter profile $V$, let $G_V$ be the complete tournament obtained from the majority graph associated with $V$. Although we do not assume that $r$ is based on the majority graph, we nevertheless prove our result by considering all possible tournaments on four candidates. In fact, the proof never uses the fact that two profiles having the same majority graph have the same winner.<fnref n="13" /> In the proof, when we speak of a “PSNE in $G$” we mean a PSNE in any candidacy game for which the profile $V$ is associated with the majority graph $G$. There are four tournaments to consider (all others are obtained from these ones by symmetry).

<figure><img src="image_6.png" /></figure>

For $G_1$ and $G_2$, any subset of $X$ containing the Condorcet winner is a PSNE (see Proposition 1). For $G_3$, we note that $a$ is a Condorcet loser. That is, $N(a, x) < N(x, a)$ for all $x \in \{b, c, d\}$. Note that in this case, there is no Condorcet winner in the reduced profile $V \downarrow \{b,c,d\}$ as this would imply the existence of a Condorcet winner in $V$ (case $G_1$ or $G_2$). W.l.o.g., assume that $b$ beats $c$, $c$ beats $d$, and $d$ beats $b$. W.l.o.g. again, assume that $bcd \mapsto b$. Then, $\{b, c\}$ is a PSNE. Indeed, in any set of just two candidates, none has an incentive to leave. Now, $a$ or $d$ have no incentive to join as this would not change the winner: in the former case, observe that $b$ is the (unique) Condorcet winner in $V \downarrow \{a,b,c\}$, and the latter follows by our assumption. There is always a PSNE for $G_3$.

The proof for $G_4$ is more complex and proceeds case by case. Since $r$ is Condorcet-consistent, we have $acd \mapsto a$, $bcd \mapsto c$, $ab \mapsto b$, $ac \mapsto a$, $ad \mapsto a$, $bc \mapsto c$, $bd \mapsto d$ and $cd \mapsto c$. The sets of candidates for which $r$ is undetermined are $abcd$, $abc$ and $abd$.

<footnote n="13">¹³ For instance, we may have two profiles $V, V'$ both corresponding to $G_4$, such that $r(V) = a$ and $r(V') = b$; the proof perfectly works in such a case.</footnote>
We have the following easy facts: (i) if $abcd \mapsto a$ then $acd$ is a PSNE, (ii) if $abcd \mapsto c$ then $bcd$ is a PSNE, (iii) if $abc \mapsto a$ then $ac$ is a PSNE, (iv) if $abd \mapsto a$ then $ad$ is a PSNE, (v) if $abc \mapsto c$ then $bc$ is a PSNE. The only remaining cases are:

1. $abcd \mapsto b, abc \mapsto b, abd \mapsto b$.

2. $abcd \mapsto b, abc \mapsto b, abd \mapsto d$.

3. $abcd \mapsto d, abc \mapsto b, abd \mapsto b$.

4. $abcd \mapsto d, abc \mapsto b, abd \mapsto d$.

In cases 1 and 3, $ab$ is a PSNE. In case 2, if $a$ prefers $b$ to $c$ then $abc$ is a PSNE, and if $a$ prefers $c$ to $b$, then $bcd$ is a PSNE. In case 4, if $a$ prefers $c$ to $d$, then $bcd$ is a PSNE; if $b$ prefers $a$ to $d$, then $ad$ is a PSNE; finally, if $a$ prefers $d$ to $c$ and $b$ prefers $d$ to $a$, then $abcd$ is a PSNE. $\square$

Thus, the picture for four candidates shows a sharp contrast. On one hand, we show that “almost all scoring rules” [38], single transferable vote, and plurality with run-off, may fail to have a PSNE. On the other hand, Condorcet-consistency alone suffices to guarantee its existence.<fnref n="14" /> Note though, that the proof of Proposition 7 does not extend to imply the existence of genuine PSNE for Condorcet-consistent rules with $m = 4$ candidates. As can be seen from the remainder of this section, different families of Condorcet-consistent rules show different results with respect to the EGE property for $m = 4$ candidates, as well as w.r.t. the EE property for $m > 4$.

## 6.1 Maximin, uncovered set, and top cycle

As the following Proposition 8 demonstrates, for the maximin rule and the uncovered set rule, the existence of PSNE is no longer guaranteed beyond four candidates. The proof, consisting of two counterexamples, is detailed in the appendix.

**Proposition 8.** For the maximin rule and the uncovered set rule, with $m = 5$ candidates, there are candidacy games without PSNE.

However, this negative result does not extend to all Condorcet-consistent rules, as can be seen from the Proposition 9 below and the following Proposition 13.

**Proposition 9.** For the top cycle rule, every candidacy game with $m \le 6$ candidates has a PSNE, and for $m = 7$ candidates, there are candidacy games without PSNE.

*Proof.* The proof for 5 candidates is reasonably easy to follow. Let $V$ be a voter profile over $X = \{a, b, c, d, e\}$ and without loss of generality, assume that the tie-breaking priority ranks $a$ above all other candidates. If $|TC(V)| \le 4$ then consider the restriction $V \downarrow^{TC(V)}$ of $V$ to $TC(V)$. It is a $q$-candidate profile for $q \le 4$, therefore by Proposition 7 the corresponding candidacy game has a PSNE $Z \subseteq TC(V)$. Since it is a PSNE in $V \downarrow^{TC(V)}$, no candidate in $TC(V)$ has an incentive to deviate. Now, if a candidate in

<footnote n="14">¹⁴ Note that this positive result holds as well for the Banks rule, since uncovered set and Banks do coincide up to six candidates [5].</footnote>
$X \setminus TC(V)$ joins, the outcome does not change, therefore no candidate outside $TC(V)$ has an incentive to join. Therefore, $Z$ is a PSNE for $V$.

Assume now that $TC(V) = \{a, b, c, d, e\}$, so $a$ is preferred by the tie-breaking. Without loss of generality, let the majority graph contain $a \to b \to c \to d \to e \to a$. For $abcde$ not to be a PSNE, a withdrawing agent $x$ has to induce a new top cycle not containing $a$. If this top cycle is a singleton, then $X \setminus \{x\}$ is a PSNE. Therefore, the top cycle after the withdrawal of $x$ must be of size 3: it can only be $\{c, d, e\}$, with $b$ withdrawing because it prefers the most prioritized candidate (let us call it $y$) among $\{c, d, e\}$ to $a$. At this stage, we know that $d \to a, c \to a, e \to a, c \to d \to e \to c$, and that the winner in $abcde$ is $y$. Observe that, irrespective of the tie-breaking winner, agent $a$ will not leave because the winner would remain the same. Thus, there are three cases to consider:

- Case 1: $y = c$. Consider $acd \mapsto c$. Since $ac \mapsto c$, $cd \mapsto c$, and $abcde \mapsto c$, $acd$ is not a PSNE only if $b$ wants to join; but $abcd \mapsto a$, and $b$ prefers $c$ to $a$: $bcd$ is a PSNE.

- Case 2: $y = e$. Consider $ace \mapsto e$. Since $ae \mapsto e$, $ce \mapsto e$, and $acde \mapsto e$, $ace$ is not a PSNE only if $b$ wants to join. For this to be possible, we must have $b \to e$, and then $abc e \mapsto a$. But in this case, since $abc \mapsto a$, $abe \mapsto a$, and $abcde \mapsto a$, $abc e$ is a PSNE. Therefore, either $ace$ or $abc e$ is a PSNE.

- Case 3: $y = d$. Consider $ade \mapsto d$. Since $ad \mapsto d$, $de \mapsto d$ and $acde \mapsto d$, $ade$ is not a PSNE only if $b$ wants to join. For this to be possible, it must be that $b \to d$ (and $b$ prefers $a$ over $d$). Thus, $abde \mapsto a$. In this case, since $abd \mapsto a$ and $abcde \mapsto a$, $abde$ is not a PSNE only if $d$ wants to leave. This is possible only if $e \to b$ (and $d$ prefers $e$ over $a$). But then, $abe \mapsto e$, $ae \mapsto e$, $be \mapsto e$, and $abc e \mapsto e$: $abde$ is a PSNE. Therefore, either $ade$ or $abde$ is a PSNE.

For the case of $m = 6$ candidates it becomes too tedious to perform a similar case analysis, so we obtain the result with the help of computer techniques. More specifically, we first prune the domain to reduce the number of majority graphs to consider (for instance, we can safely assume the existence of a top cycle involving all the candidates). Then, for each remaining graph, we compute the co-winners given by the top cycle rule, and launch a feasibility problem asking the computer to build an instance without equilibrium. This is similar in spirit to the programs used in previous sections, but including additional types of decision variables: one for encoding the fact that candidates are co-winners, and one for the tie-breaking ordering. Additional constraints then make sure that winners are indeed among the co-winners, and that if a candidate is winning among co-winners, then this has to be thanks to the tie-breaking. The feasibility of each integer program called tells us that an equilibrium always exists, but we could not extract any readable proof from the result. For the case with $m = 7$ candidates, the same methodology provided a counterexample that we detail in full in the appendix. $\square$

We now turn to show that in contrast to the EE property of Condorcet-consistent rules with four candidates, genuine equilibria may fail to exist for maximin, top cycle and the uncovered set rule with $m = 4$ candidates (see Propositions 10, 11 and 12).

**Proposition 10.** For the maximin rule, with $m = 4$ candidates, some candidacy games have no genuine PSNE.
**Proof.** Consider the following profile with 9 votes over the set *abcd* of 4 candidates.

$$ \begin{bmatrix} 3 & 2 & 1 & 3 \\ a & b & d & d \\ b & c & b & c \\ c & a & c & a \\ d & d & a & b \end{bmatrix} $$

We thus have: $N(a, b) = N(b, c) = N(c, a) = 6$ and $N(a, d) = N(b, d) = N(c, d) = 5$. Tie-breaking is arbitrary. The genuine winner in the full candidate profile *abcd* is *d*, who is a Condorcet loser, and the only other state where *d* gets elected is *d* where any other candidate would have an incentive to join. Therefore, there is no genuine PSNE. ☐

**Proposition 11.** For the top cycle rule, with $m = 4$ candidates, some candidacy games have no genuine PSNE.

*Proof.* Assume the majority graph is $G_4$ as in the proof of Proposition 7. Assume the tie-breaking priority relation is $d \succ c \succ b \succ a$. Then $abcd \mapsto d$, $abc \mapsto c$, $abd \mapsto d$, $acd \mapsto a$, $ad \mapsto a$, $bd \mapsto d$, $cd \mapsto c$. Assume that *a* prefers *c* to *d* and *b* prefers *a* to *d*. The only states where *d* is elected are

- *abcd*, which is not a PSNE because *a* wants to withdraw;

- *abd*, which is not a PSNE because *b* wants to withdraw;

- *bd*, which is not a PSNE because *c* wants to join;

- *d*, which is not a PSNE because *a* wants to withdraw.

Therefore, there is no genuine PSNE. ☐

**Proposition 12.** For the uncovered set rule, with $m = 4$ candidates, some candidacy games have no genuine PSNE.

*Proof.* We take a profile whose associated majority graph is $G_4$ as in the proof of Proposition 7. The tie-breaking priority relation is $d \succ b \succ a \succ c$. The candidates' preferences are such that *a* prefers *c* to *b*, and are otherwise arbitrary. In the state *abcd*, *a*, *b* and *c* are uncovered set co-winners (but not *d*), and by tie-breaking, the winner in *abcd* is *b* and a genuine PSNE must have *b* as winner. The choice function induced from the profile is *abcd* $\mapsto$ *b*, *abc* $\mapsto$ *b*, *abd* $\mapsto$ *d*, *acd* $\mapsto$ *a*, *bcd* $\mapsto$ *c*, *ab* $\mapsto$ *b*, *ac* $\mapsto$ *a*, *ad* $\mapsto$ *a*, *bc* $\mapsto$ *c*, *bd* $\mapsto$ *d*, *cd* $\mapsto$ *c*. In state *abcd*, *a* wants to leave. The only states other than *abcd* where the winner is *b* are *abc*, *ab* and *b*. *abc* is not a PSNE because *a* wants to leave; *ab* and *b* are not PSNEs because in both, *d* wants to join. Therefore, there is no genuine PSNE.

The only common rule we could identify for which the EGE property holds for any number of candidates, is Copeland, as we show next.
## 6.2 Copeland

Here, we prove our main positive result showing the existence of genuine pure strategy Nash equilibrium for Copeland, under deterministic tie-breaking, for any number of candidates (provided the number of voters, $n$, is odd).

**Proposition 13.** For Copeland, for any number of candidates and an odd number of voters, every candidacy game has a genuine PSNE.

*Proof.* Let $V$ be a profile and $\to_V$ its associated majority graph. Let $N(x, V)$ be the number of candidates $y \neq x$ such that $x \to_V y$. The Copeland co-winners for $V$ are the candidates maximizing $N(\cdot, V)$.

Let $Cop(V)$ be the set of Copeland co-winners for $V$ and let $c$ be the Copeland winner—i.e., the most prioritized by the tie-breaking order candidate in $Cop(V)$. Let $Dom(c) = \{c\} \cup \{y | c \to_V y\}$ and $q = N(c, V^{Dom(c)}) = |Dom(c)| - 1 \geq N(c, V)$. Also, since any $y \in Dom(c)$ is beaten by $c$, we have $N(y, V^{Dom(c)}) \leq q - 1$.

We claim that $Dom(c)$ is a PSNE. Note that $c$ is a Condorcet winner in the restriction of $V$ to $Dom(c)$, and a *fortiori*, in the restriction of $V$ to any subset of $Dom(c)$. Hence, $c$ is the Copeland winner in $Dom(c)$ and any of its subsets, and no candidate in $Dom(c)$ has an incentive to leave.

Now, assume there is a candidate $z \in X \setminus Dom(c)$ such that $r(V^{Dom(c)} \cup \{z\}) \neq c$. Note that $z \to_V c$ as $z$ does not belong to $Dom(c)$; so, $N(c, V^{Dom(c)} \cup \{z\}) = q$.

For any $y \in Dom(c)$ we have $N(y, V^{Dom(c)} \cup \{z\}) \leq (q-1)+1 = q = N(c, V^{Dom(c)} \cup \{z\})$. If $N(y, V^{Dom(c)} \cup \{z\}) < N(c, V^{Dom(c)} \cup \{z\})$, then $y$ is not the Copeland winner in $V^{Dom(c)} \cup \{z\}$. If $N(y, V^{Dom(c)} \cup \{z\}) = N(c, V^{Dom(c)} \cup \{z\})$, then $N(y, V) \geq N(c, V)$. That is, either $c \notin Cop(V)$, a contradiction, or both $y, c$ are in $Cop(V)$. The latter implies $c \succ y$; hence, $y$ is not the Copeland winner in $V^{Dom(c)} \cup \{z\}$.

Hence, $r(V^{Dom(c)} \cup \{z\}) = z$. That is, either (1) $N(z, V^{Dom(c)} \cup \{z\}) > q$, or (2) $N(z, V^{Dom(c)} \cup \{z\}) = q$ and $z \succ c$. If (1) holds then $N(z, V) > N(c, V)$, which contradicts the fact that $c$ is the Copeland winner in $V$. If (2) holds then $N(z, V) = N(c, V)$—i.e., both $c$ and $z$ are in $Cop(V)$, which implies that $c \succ z$, and $z$ cannot win in $V^{Dom(c)} \cup \{z\}$. Therefore, the Copeland winner in $V^{Dom(c)} \cup \{z\}$ is $c$, which implies that $z$ has no incentive to join $Dom(c)$. $\square$

Note that the proof of Proposition 13 not only implies the existence of a PSNE, but the existence of a genuine PSNE where the Copeland winner is the same as in the full candidate profile. This, however, does not imply the candidate stability for candidacy games under Copeland—that is, that the set of all potential candidates is a PSNE.<fnref n="15" />

When $n$ is even, the result of Proposition 13 carries on whenever no pairwise majority ties occur. In the general case, however, the result depends on the way ties are taken into account for computing the Copeland score of a candidate. For the variant

<footnote n="15">¹⁵ For instance, let $X = \{a, b, c, d\}$, and consider the majority graph $a \to b, a \to c; b \to c, b \to d; d \to a, d \to c$, with the tie-breaking priority relation $a \succ b \succ c \succ d$. The Copeland winner is $a$ (by the tie-breaking). We only need to specify that $b : d \succ a$ on top of self-supported preferences. $X$ is not a PSNE, because it is a profitable deviation for $b$ to leave.</footnote>
Copeland⁰ where the Copeland score is given by the number of outgoing edges (i.e., ties not giving any point), the result still holds. Whether it holds for other variants of the rule, is an open question.

The next step for Copeland in the hierarchy of stability properties (see Section 2.3) would be to prove CGE—that is, to show that a genuine PSNE characterized in Proposition 13 can be reached by a sequence of improving moves starting from the set of all candidates. Unfortunately, as the next Proposition 14 demonstrates, there is no such guarantee.

**Proposition 14.** For the Copeland rule, there exist candidacy games such that no genuine PSNE is reachable from the set of all candidates.

*Proof.* Consider a profile corresponding to the majority graph below, together with the following partial candidates' preferences (unspecified preferences play no role). The tie-breaking priority relation is lexicographic.

$$ 
\begin{align*}
a & : a \succ b \succ e \succ d \succ c \\
d & : d \succ c \succ e \succ a \succ b \\
b & : b \succ a \succ c \succ d \succ e
\end{align*}
$$

<figure><img src="image_7.png" /></figure>

The Copeland winner is e. The Nash equilibrium characterized in the proof of Proposition 13 is *acde* (the winner is *e* as in the full profile). The choice function, restricted to the states that contain *e*, is *acde* ↦ *e*, *abce* ↦ *c*, *abde* ↦ *a*, *acde* ↦ *e*, *bcde* ↦ *d*, *abe* ↦ *a*, *ace* ↦ *e*, *ade* ↦ *e*, *bce* ↦ *b*, *bde* ↦ *b*, *cde* ↦ *e*, *ae* ↦ *e*, *be* ↦ *b*, *ce* ↦ *e*, *de* ↦ *e*. Therefore, the other states where *e* wins are *acde*, *ace*, *ade*, *cde*, *ae*, *ce*, *de*, and *e*. The only one of them which is a PSNE is *acde*: in all other states *ace*, *ade*, *cde*, *ae*, *ce*, and *de*, *b* wants to joins. Now we show that *acde* cannot be reached by a sequence of deviations from the initial state *acde*.

We first exhibit the following sequence of deviations starting from the initial state.

$$ 
\begin{align*}
abcd & \mapsto e \\
d & \text{withdraws: } abce \mapsto c \\
a & \text{withdraws: } bce \mapsto b \\
d & \text{joins: } bcde \mapsto d \\
a & \text{joins: } abcd \mapsto e
\end{align*}
$$

We cannot reach *acde* by a series of individual deviations: not from *acde* because the winner does not change; not from *ade* (the winner is *a*, thus *b* does not want to join); not from *ace* (*e* is the winner); and not from *cde* (*c* is the winner). It is reachable
from *acd* by *e* joining, since *acd* $\mapsto$ *a* and *acde* $\mapsto$ *e*. Now, we show that *acd* cannot be reached through a deviation path from *abcde*. *acd* cannot be reached from *abcd* because *abcd* $\mapsto$ *a*, nor from *abce* because *abcd* $\mapsto$ *e*, nor from *ac* because *ac* $\mapsto$ *c* and *d* prefers *c* to *a*, nor from *ad* because *ad* $\mapsto$ *a*; it an however be reached from *cd* by *a* joining; however, *cd* cannot be reached through a deviation path from *abcde*: it cannot be reached from *acd* since *acd* $\mapsto$ *a*, nor from *bcd* since *bcd* $\mapsto$ *d* and *cd* $\mapsto$ *d*, nor from *cde* since *cde* $\mapsto$ *e*, nor from *d*; it can be reached from *c*, but *c*, like any singleton state, cannot be reached by any deviation. $\square$

# 7 Strong equilibria

Turning attention to coalitional deviations, in this section we prove that strong equilibria are not guaranteed for almost any voting rule and any number of candidates $m \ge 3$.

Let *r* be a voting rule defined for a varying set of candidates *Y* ⊆ *X*. We say that *r* is majority-extending if for any *Y* ⊆ *X* such that |*Y*| = 2, if the two candidates in *Y* are not tied in $V^{\downarrow Y}$, then *r*($V^{\downarrow Y}$) is the majority winner in $V^{\downarrow Y}$ (in case of a tie, we do not need to specify the outcome). Then we can state that:

**Proposition 15.** For any majority-extending and IBC voting rule, and for any $m \ge 3$, there is an $m$-candidate profile without a SE.

*Proof.* Let *r* be a majority-extending and IBC rule. Consider the following 3-voter, *k* + 3-candidate profile ($k \ge 0$):

<figure><img src="image_8.png" /></figure>

The preferences of candidates include: $a : a \succ b \succ c$; $b : b \succ c \succ a$; $c : c \succ a \succ b$; the preferences of candidates beyond *a*, *b*, *c* are not relevant.

By a repeated application of IBC, for any nonempty $Y \subseteq \{a, b, c\}$, and any $Z \subseteq \{x_1, \dots, x_k\}$, we have $r(V^{\downarrow Y \cup Z}) = r(V^Y)$.

We already know that $r(V^{\downarrow \{a,b,c,x_1,\dots,x_k\}} \in \{a, b, c\})$. Without loss of generality, assume that $r(V^{\downarrow \{a,b,c,x_1,\dots,x_k\}}) = a$. For any $Z \subseteq \{x_1, \dots, x_k\}$, by IBC and majority-extension, the resulting choice function must be:

$$abcZ \mapsto a; abZ \mapsto a; bcZ \mapsto b; acZ \mapsto c; aZ \mapsto a; bZ \mapsto b; cZ \mapsto c$$

But then, given the candidates' preferences, for any $Z \subseteq \{x_1, \dots, x_k\}$ we have:

- *abcZ* is not a SE: *abcZ* $\mapsto$ *a*, *b* leaves $\mapsto$ *c*

- *abZ* is not a SE: *abZ* $\mapsto$ *a*, *b* leaves and *c* joins $\mapsto$ *c*
- $acZ$ is not a SE: $acZ \mapsto c$, $a$ leaves and $b$ joins $\mapsto b$

- $bcZ$ is not a SE: $bcZ \mapsto b$, $a$ joins $\mapsto a$

- $aZ$ is not a SE: $aZ \mapsto a$, $c$ joins $\mapsto c$

- $bZ$ is not a SE: $bZ \mapsto b$, $a$ joins $\mapsto a$

- $cZ$ is not a SE: $cZ \mapsto c$, $b$ joins $\mapsto b$

- $Z$ is not a SE: any of $a$, $b$ or $c$ wants to join.

☐

The result of Proposition 15 applies to most common voting rules. A noticeable exception is veto; however, we already know that for veto, there exist profiles without PSNE, and therefore without SE.

# 8 Strategic candidacy and consenting candidate control

In this section, we present the conceptual contribution of our work. We define the notion of *consenting control* and discuss its relation to strategic candidacy; we then prove the very first results on *resistance* to this new version of candidate control. We start by listing different types of candidate control, relevant for our study.

## 8.1 Background on candidate control

Throughout this section, we continue to assume that voting rules are resolute.

Candidate control was introduced for the first time by Bartholdi et al. [2].<fnref n="16" /> Since then, several variants of candidate control have been proposed:

- An instance of *constructive control by deleting candidates* (CCDC) [2] consists of a profile $V$ over set of candidates $X$, a distinguished candidate $c$, an integer $k$, and we ask whether there exists a subset $Y$ of $X$ with $|X \ \& \ Y| \le k$ such that $c$ is the (unique) winner in $Y$.

- An instance of *constructive control by adding an unlimited number of candidates* (CCAUC) [2] consists of a profile $V$ over set of candidates $X_1 \cup X_2$, a distinguished candidate $c$, and we ask whether there exists a subset $Y$ of $X_2$ such that the winner in $X_1 \cup Y$ is $c$.

- An instance of *constructive control by adding candidates* (CCAC) [22] consists of a profile $V$ over set of candidates $X_1 \cup X_2$, a distinguished candidate $c$, and we ask if there exists a subset $Y$ of $X_2$ such that $|Y| \le k$ and the winner in $X_1 \cup Y$ is $c$.

Control by adding candidates is highly related to the determination of *robust winners* under candidate uncertainty [4]: given a set of candidates, a subset of which may turn out to be unavailable (and then decline the offer to take the position if they are elected); a winner is robust if it wins for any possible set of available candidates.

*Destructive* versions of control have been defined by Hemaspaandra et al. [26]:

<footnote n="16">¹⁶ They also defined other versions of control: control by partitioning candidates, as well as by adding, deleting or partitioning voters. We do not discuss them in this paper because they are not (as far as we can see) related to strategic candidacy.</footnote>
- destructive control by deleting (DCDC) is similar to CCDC, except that we ask whether there is a subset $Y$ of $X \setminus \{c\}$ with $|X \setminus Y| \le k$ such that $c$ is not the winner in $X \setminus Y$; and

- destructive control by adding candidates (DCAC) is similar to CCAC, except that $c$ should not be the winner in $Y$.

Finally, there are also multimode versions of control [21]: especially, constructive control by deleting and adding candidates, abbreviated into CC (DC+AC), allows the chair to delete some candidates and to add some others (subject to some cardinality constraints).

## 8.2 Consenting candidate control and its relation to strategic candidacy

Nash equilibria and strong equilibria in strategic candidacy relate to a more demanding notion of control, which we call *consenting control*, and that we find an interesting notion *per se*. In traditional control, candidates have no preferences and no choice—the chair may add or delete them as she likes. In contrast, an instance of *consenting CCDC* consists of an instance of CCDC plus, for each candidate in $X$, a preference ranking over $X$, and we ask whether there is a subset $Y$ of $X$ with $|X \setminus Y| \le k$ such that $c$ is the unique winner in $Y$, and every candidate in $X \setminus Y$ prefers $c$ to the candidate which would win if all candidates in $X$ were running. An instance of *consenting CCAC* consists of an instance of CCAC plus, for each candidate in $X_2$, a ranking over $X_1 \cup X_2$, and we ask whether there is a subset $Y$ of $X_2$, of cardinality at most $k$, such that the unique winner in $X_1 \cup Y$ is $c$, and every candidate in $Y$ prefers $c$ to the candidate which would win if only the candidates in $X_1$ were running. Consenting versions of destructive control are defined similarly.

The following observations are straightforward:

**Observation 1** For any profile $V$, the joint action $(1, \dots, 1)$ is a SE if and only if there is no consenting destructive control by deleting candidates against the current winner $r(V)$, with the value of $k$ being fixed to $m$.

The reason for $k=m$ is that the chair has no limit on the number of candidates to be deleted; on the other hand, control actions are restricted by the requirement for the deleted candidates to give consent.

**Observation 2** For any profile $V$, the joint action $(1, \dots, 1)$ is a PSNE if and only if there is no consenting destructive control by removing candidates against the current winner $r(V)$, with the maximum number $k$ of candidates to be deleted fixed to 1.

For candidate sets that are different from the set $X$ of all candidates (as some may leave and some other may join), we have to resort to *consenting DC(DC+AC)*. Let $s$ be a state and $Y$ the set of running candidates in $s$: then, $s$ is a SE if there is no consenting destructive control by removing and adding candidates against the current winner $r(V \downarrow Y)$, without any constraint on the number of candidates to be removed or added. For a PSNE, this is similar, but with the bound $k=1$ on the number of
candidates to be deleted or added. Finally, $s$ is a $k$-PSNE if $(V, Y, X \setminus Y, k)$ is a negative instance of consenting CC (DC+AC). In particular, $s$ is a PSNE if $(Y, X \setminus Y, 1)$ is a negative instance of consenting destructive control by adding or removing candidates, and $s$ is a SE if $(Y, X \setminus Y)$ is a negative instance of consenting destructive control by adding or removing an unlimited number of candidates.

## 8.3 Resistance to consenting candidate control

Given a voting rule $r$ and a type of control $T$: voting rule $r$ is said to be *immune* to $T$ if there are no positive instances of $T$ for $r$; it is *vulnerable* to $T$ if there are positive instances of $T$ for $r$ and the problem of deciding whether a successful control exists is polynomial; and *resistant* to $T$ if the problem of deciding whether a successful control exists is NP-hard. Identifying the status of the different types of control for various rules has been the topic of a number of papers, starting by [2]: see [23] for a survey at the time; several additional results have appeared since then, as detailed in Section 1.

Clearly, a consenting candidate control strategy (consisting of a set of candidates to add or delete) is also a standard candidate control strategy, while the converse is not true. However, this does not allow to derive results about resistance to consenting candidate control from results about standard candidate control. Nonetheless, in five forms of candidate control out of six, we can find a polynomial reduction from control to consenting control of the same type.

**Proposition 16.** For any resolute voting rule $r$, resistance to standard control implies resistance to consenting control, for the following five control types: CCAC, CCAUC, DCAC, DCAUC and DCDC.

*Proof.* The proof consists of a generic reduction from standard control to consenting control of the same type.

1. Let $I = (V, X_1, X_2, k, c)$ be an instance of CCAC (respectively, an instance $I = (V, X_1, X_2, c)$ of CCAUC). We extend $I$ into an instance $I'$ of consenting CCAC (respectively, CCAUC), where $V'$ is defined as follows: every candidate in $X_1$ has itself on top (and no other constraint); every candidate in $X_2$ has itself on top, then $c$, and no other constraint. If there is a succeeding constructive control for $c$, then the added candidates (all from $X_2$) consent, since they like $c$ at least as much as the previously winning candidate. Therefore, $I$ is a positive instance of CCAC (respectively, CCAUC) if and only if $I'$ is a positive instance of consenting CCAC (respectively, CCAUC).

2. Let $I = (V, X_1, X_2, k, c)$ be an instance of DCAC (respectively, an instance $I = (V, X_1, X_2, c)$ of DCAUC). We extend $I$ into an instance $I'$ of consenting DCAC (respectively, DCAUC), where $V'$ is defined as follows: candidates of $X_1$ have themselves on top, and no other constraint; candidates of $X_2$ have themselves on top, $c$ bottom-ranked, and no constraint for the candidates in-between. If there is a successful destructive control against $c$, then the deleted candidates (which do not include $c$, by definition) consent, since they prefer the new winner to $c$. Therefore, $I$ is a positive instance of DCAC (respectively, DCAUC) if and only if $I'$ is a positive instance of consenting DCAC (respectively, DCAUC).
3. let $I = (V, X, k, c)$ be an instance of DCDC. We extend $I$ into an instance $I'$ of consenting DCDC, where $V'$ is defined as follows: $c$ has itself on top and no other constraint; every other candidate has itself on top, $c$ bottom-ranked, and no other constraint in-between. If there is a successful destructive control against $c$, then the deleted candidates (which do not include $c$, by definition) consent, since they prefer the new winner to $c$. Therefore, $I$ is a positive instance of DCDC if and only if $I'$ is a positive instance of consenting DCDC. $\square$

As a corollary of Proposition 16, all results about resistance to control for these five types of standard candidate control [23] carry on to the consenting control version. As an example, plurality is resistant to these five types of consenting control.

For constructive control by deleting candidates, these simple generic reductions do not work, because a control strategy sometimes needs to delete the current winner, who will never consent to such a deletion. Worse than that, there cannot be a generic reduction from CCDC to consenting CCDC. To see it, consider the artificial voting rule $r$ that fixes a priority ranking $x_1 \succ x_2 \dots \succ x_m$ over $X$ and outputs the candidate with highest priority among those who are running. When $x_1$ runs (and in particular, when all candidates run), it wins. Therefore, there cannot be a constructive control for $c \neq x_1$, since it would need $x_1$ to be deleted, which $x_1$ will never consent to: in other terms, $F$ is immune to consenting CCDC. However, for CCDC there are positive and negative instances, and it is easy to see that $r$ is vulnerable to CCDC.

In the other direction, there is a generic polynomial reduction for several types of control, provided that the voting rule is polynomial-time computable.

**Proposition 17.** For any resolute rule $r$ with polynomial-time winner determination:

- vulnerability to CCAC implies vulnerability to consenting CCAC;

- vulnerability to CCAUC implies vulnerability to consenting CCAUC;

- vulnerability to consenting CCAC (resp. CCAUC) implies vulnerability to consenting DCDC (resp. DCAUC).

*Proof.* 1. Let $I = (V, X_1, X_2, k, c, \succ_X)$ be an instance of consenting CCAC. Let $w$ be the current winner and let $X_2^{c\succ w}$ be the set of candidates in $X$ who prefer $c$ to $w$. There is a consenting constructive control by adding candidates for $c$ if there is a standard constructive control by adding candidates for the instance $I' = (V, X_1, X_2^{c\succ w}, \min(k, |X_2^{c\succ w}|), c)$. Since $w$ can be determined in polynomial time, this is a polynomial reduction.

2. For consenting CCAUC, the reduction is similar, with $I = (V, X_1, X_2, c, \succ_X)$ and $I' = (V, X_1, X_2^{c\succ w}, c)$.

3. It is already known (footnote 4 in [26]) that for resolute voting rules, destructive control (of any type) can be polynomially reduced to constructive control (of the same type), because there is a destructive control against $c$ if there is a constructive control for some $x \neq c$. This, together with points 1 and 2 above, shows that vulnerability to CCAC and CCAUC implies vulnerability to consenting DCAC and DCAUC. $\square$

Propositions 16 and 17, together with the fact that immunity, resistance and vulnerability form a partition of all cases, imply that for any polynomial-time computable rule
(which is the case for all rules considered in Table 7.3 in [23]), the standard version and
the corresponding consenting version of CCAC (respectively, CCAUC) have the same
status (immunity, resistance of vulnerability). For DCAC and DCDC, we only know
that resistance to standard control implies resistance to consenting control.

For CCDC, we do not have any generic link between the standard and consenting versions. As we said above, there are rules which are immune to consenting CCDC while being vulnerable to standard CCDC, which precludes the existence of a reduction between consenting and standard control, in either direction, and which in turn implies that results should be obtained directly (which we leave for further research).

Figure 8.3 shows polynomial reductions between different forms of control (we omit the versions with adding an unlimited number of candidates for brevity). Plain arrows are valid for all voting rules, whereas dashed arrows are valid only for polynomial-time computable voting rules.

<figure><img src="image_9.png" /><figcaption>Fig. 3. Reductions between control problems</figcaption></figure>

9 Conclusion

Our work offers a first systematic analysis of strategic candidacy equilibria for a list of
most prominent voting rules, and proves several (non)-existence results (see Table 9).

A full characterization of classes of voting rules under which all strategic candidacy
games have genuine pure strategy Nash equilibria, at least for an odd number of voters,
is left for further research. We know that such equilibria are guaranteed to exist for
Copeland, as well as for the rule defined by the sophisticated successive elimination;
however, these two rules do not have much in common, which suggests that such a
characterization could be highly complex.

Following the work of Polukarov *et al.* [35], another important research direction is
the study of (stable) states that can be reached by some (e.g., best response) dynamics,
<table><caption>**Table 2.** PSNE existence guarantee for classes of strategic candidacy games. In brackets, we specify genuine PSNE existence</caption><thead><tr><th></th><th>3</th><th>4</th><th>5-6</th><th>≥ 7</th></tr></thead><tbody><tr><td>plurality</td><td>yes (no)</td><td>no (no)</td><td>no (no)</td><td>no (no)</td></tr><tr><td>veto</td><td>yes (no)</td><td>no (no)</td><td>no (no)</td><td>no (no)</td></tr><tr><td>pl. runoff</td><td>yes (yes*)</td><td>no (no)</td><td>no (no)</td><td>no (no)</td></tr><tr><td>STV</td><td>yes (yes*)</td><td>no (no)</td><td>no (no)</td><td>no (no)</td></tr><tr><td>Borda</td><td>yes (yes*)</td><td>yes (no)</td><td>no (no)</td><td>no (no)</td></tr><tr><td>maximin</td><td>yes (yes*)</td><td>yes* (no)</td><td>no (no)</td><td>no (no)</td></tr><tr><td>UC</td><td>yes (yes*)</td><td>yes* (no)</td><td>no (no)</td><td>no (no)</td></tr><tr><td>TC</td><td>yes (yes*)</td><td>yes* (no)</td><td>yes* (no)</td><td>no (no)</td></tr><tr><td>Copeland</td><td>yes (yes)</td><td>yes* (yes*)</td><td>yes* (yes*)</td><td>yes* (yes*)</td></tr></tbody></table>

By “yes*” we mean that the guarantee holds under the assumption that $n$ is odd, or more generally, that pairwise majority ties do not occur.

starting from the set or all potential candidates. In some cases, even when the existence of PSNE is guaranteed (e.g., for Copeland), we could already come up with examples where none is reachable by a sequence of best responses; however, other types of dynamics may also be studied. We are also interested in determining the computational complexity of deciding whether there is a PSNE or SE, and whether they are reachable by natural dynamic processes.

Finally, in this work we make the first steps into exploring the concept of consenting control, which as we show is closely related to strategic candidacy, and hope to see many exciting results in this direction in the future.

## Acknowledgements

We would like to thank Markus Brill, Edith Elkind, Michel Le Breton and Vincent Merlin for helpful discussions. This work was partly supported by the UK Research and Innovation (UKRI) Engineering and Physical Sciences Research Council (EPSRC) [grant numbers EP/X038351/1, EP/X038348/1]. This work was supported in part by project ANR-22-CE26-0019 “Citizens”, funded by the Agence Nationale de la Recherche.

## References

1. R. Aumann. Acceptable points in general cooperative n-person games. In *Contributions to the Theory of Games IV*, volume 40 of *Annals of Mathematics Study*, pages 287–324. 1959.

2. J. Bartholdi, C. Tovey, and M. Trick. How hard is it to control an election? *Social Choice and Welfare*, 16(8-9):27–40, 1992.

3. S. Bervoets and V. Merlin. On avoiding vote swapping. *Social Choice and Welfare*, 46(3):495–509, 2016.

4. C. Boutilier, J. Lang, J. Oren, and H. Palacios. Robust winners and winner determination policies under candidate uncertainty. In *Proceedings of the Twenty-Eighth AAAI Conference*
on Artificial Intelligence, July 27-31, 2014, Québec City, Québec, Canada., pages 1391-1397, 2014.

5. F. Brandt, A. Dau, and H. G. Seedig. Bounds on the disparity and separation of tournament solutions. *Discrete Applied Mathematics*, 187:41–49, 2015.

6. M. Brill and V. Conitzer. Strategic voting and strategic candidacy. In *Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI)*, pages 819–826, 2015.

7. A. Buchanan. Political districting. In *Encyclopedia of Optimization*, pages 1–13. Springer, 2023.

8. K. Cechlárová, J. Lesca, D. Trellová, M. Hancová, and J. Hanc. Hardness of candidate nomination. *Auton. Agents Multi Agent Syst.*, 37(2):37, 2023.

9. J. Chen, P. Faliszewski, R. Niedermeier, and N. Talmon. Elections with few voters: Candidate control can be easy. *J. Artif. Intell. Res.*, 60:937–1002, 2017.

10. Y. Chevaleyre, J. Lang, N. Maudet, J. Monnot, and L. Xia. New candidates welcome! possible winners with respect to the addition of new candidates. *Mathematical Social Sciences*, 64(1):74–88, 2012.

11. B. Debord. Caractérisation des matrices des préférences nettes et méthodes d'agrégation associées. *Mathématiques et Sciences Humaines*, 97:5–17, 1987.

12. P. Dey, N. Misra, S. Nath, and G. Shakya. A parameterized perspective on protecting elections. In *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019*, pages 238–244, 2019.

13. H. Dindar and J. Lainé. Vote swapping in irresolute two-tier voting procedures. *Social Choice and Welfare*, 61(2):221–262, 2023.

14. A. Downs. *An Economic Theory of Democracy*. Harper and Row, 1957.

15. B. Dutta, M. Le Breton, and M. O. Jackson. Strategic candidacy and voting procedures. *Econometrica*, 69:1013–1037, 2001.

16. B. Dutta, M. Le Breton, and M. O. Jackson. Voting by successive elimination and strategic candidacy in committees. *Journal of Economic Theory*, 103:190–218, 2002.

17. L. Ehlers and J. A. Weymark. Candidate stability and nonbinary social choice. *Economic Theory*, 22(2):233–243, 2003.

18. E. Elkind, P. Faliszewski, and A. M. Slinko. Cloning in elections: Finding the possible winners. *J. Artif. Intell. Res. (JAIR)*, 42:529–573, 2011.

19. H. Eraslan and A. McLennan. Strategic candidacy for multivalued voting procedures. *Journal of Economic Theory*, 117(1):29–54, 2004.

20. P. Faliszewski, L. Gourvès, J. Lang, J. Lesca, and J. Monnot. How hard is it for a party to nominate an election winner? In *IJCAI*, pages 257–263. IJCAI/AAAI Press, 2016.

21. P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra. Multimode control attacks on elections. *JAIR*, 40:305–351, 2011.

22. P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Llull and Copeland voting computationally resist bribery and constructive control. *J. Artif. Intell. Res. (JAIR)*, 35:275–341, 2009.

23. P. Faliszewski and J. Rothe. Control and bribery in voting. In *Handbook of Computational Social Choice*, pages 146–168. 2016.

24. N. Fraser. Ordinal preference representations. *Theory and Decision*, (36):45–67, 1994.

25. P. Harrenstein, G. Lisowski, R. Sridharan, and P. Turrini. A Hotelling-Downs framework for party nominees. In *AAMAS*, pages 593–601. ACM, 2021.

26. E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Anyone but him: The complexity of precluding an alternative. *Artificial Intelligence*, 171(5-6):255–285, 2007.

27. E. Hemaspaandra, L. A. Hemaspaandra, and J. Rothe. The complexity of controlling candidate-sequential elections. *Theoretical Computer Science*, 678:14–21, 2017.

28. H. Hotelling. Stability in competition. *Econ. J.*, (39):41–57, 1929.
29. J. Lang, N. Maudet, and M. Polukarov. New results on equilibria in strategic candidacy. In Proceedings of the 6th International Symposium on Algorithmic Game Theory (SAGT), pages 13–25, 2013.

30. T. Lu and C. Boutilier. The unavailable candidate model: a decision-theoretic view of social choice. In ACM Conference on Electronic Commerce 2010, pages 263–274, 2010.

31. J. Maass, V. Mousseau, and A. Wilczynski. A Hotelling-Downs game for strategic candidacy with binary issues. In Proceedings of the Twenty-Second Conference on Autonomous Agents and MultiAgent Systems (AAMAS-23), pages 2076–2084, London, UK, May-June 2023. International Foundation for Autonomous Agents and Multiagent Systems.

32. R. Meir, M. Polukarov, J. S. Rosenschein, and N. R. Jennings. Iterative voting and acyclic games. Artificial Intelligence, 252:100–122, 2017.

33. S. Obraztsova, E. Elkind, M. Polukarov, and Z. Rabinovich. Strategic candidacy games with lazy candidates. In Proceedings of IJCAI-15, pages 610–616, 2015.

34. S. Obraztsova, M. Polukarov, E. Elkind, and M. Grzesiuk. Multiwinner candidacy games. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pages 957–965, 2020.

35. M. Polukarov, S. Obraztsova, Z. Rabinovich, A. Kruglyi, and N. Jennings. Convergence to equilibria in strategic candidacy. In Proceedings of IJCAI-15, pages 624–630, 2015.

36. C. Rodriguez-Alvarez. Candidate stability and probabilistic voting procedures. Economic Theory, 27(3):657–677, 2006.

37. C. Rodriguez-Alvarez. Candidate stability and voting correspondences. Social Choice and Welfare, 27(3):545–570, 2006.

38. D. Saari. A dictionary of voting paradoxes. Journal of Economic Theory, 48, 1989.

39. D. Saari. Election results and a partial ordering for positional ordering. In N. J. Schofield, editor, Collective Decision-Making: Social Choice and Political Economy, pages 93–110. Kluwer, 1996.

40. I. Sabato, S. Obraztsova, Z. Rabinovich, and J. S. Rosenschein. Real candidacy games: A new model for strategic candidacy. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2017, São Paulo, Brazil, May 8-12, 2017, pages 867–875, 2017.

41. T. N. Tideman. Independence of clones as a criterion for voting rules. Social Choice and Welfare, 4(3):185–206, 1987.

## Appendix : Missing Proofs

**Proposition 1** Let $\Gamma = (X, V, r, C)$ be a candidacy game where $r$ is Condorcet-consistent. If $V$ has a Condorcet winner $c$ then for any $Y \subseteq X$,

$$Y \text{ is a SE} \Leftrightarrow Y \text{ is a PSNE} \Leftrightarrow Y \text{ is a genuine PSNE} \Leftrightarrow c \in Y.$$

*Proof.* Assume $c$ is a Condorcet winner for $V$ and let $Y \subseteq X$ such that $c \in Y$. Since $r$ is Condorcet-consistent, and since $c$ is a Condorcet winner for $V^{\downarrow Y}$, we have $r(V^{\downarrow Y}) = c$. Assume $Z = Z^+ \cup Z^-$ is a deviating coalition from $Y$, with $Z^+$ the candidates who join and $Z^-$ the candidates who leave the election. Clearly, $c \notin Z$, as $c \in Y$ and $c$ has no interest to leave. Therefore, $c$ is still a Condorcet winner in $V^{\downarrow(Y \setminus Z^-) \cup Z^+}$, which by the Condorcet-consistency of $r$ implies that $r(V^{\downarrow(Y \setminus Z^-) \cup Z^+}) = c$, which contradicts the assumption that $Z$ wants to deviate. We thus conclude that $Y$ is a SE, and a fortiori a PSNE (which is also genuine). Finally, let $Y \subseteq X$ such that $c \notin Y$. Then, $Y$ is not a PSNE (and a fortiori not a SE), because $c$ has an interest to join the election. $\square$
**Proposition 8** For maximin and the uncovered set, with $m = 5$ candidates, there are profiles without PSNE.

*Proof.* For maximin, a counterexample is the following weighted majority graph along with the candidates' preference profile. The tie-breaking priority is lexicographic.

<table><thead><tr><th></th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>a b c d e</th></tr></thead><tbody><tr><th>a</th><td>0</td><td>-3</td><td>3</td><td>-1</td><td>1</td><td>a b c d e</td></tr><tr><th>b</th><td>3</td><td>0</td><td>-3</td><td>3</td><td>1</td><td>c e d a b</td></tr><tr><th>c</th><td>-3</td><td>3</td><td>0</td><td>-1</td><td>-1</td><td>b c a c a</td></tr><tr><th>d</th><td>1</td><td>-3</td><td>1</td><td>0</td><td>-5</td><td>e a e b d</td></tr><tr><th>e</th><td>-1</td><td>-1</td><td>1</td><td>5</td><td>0</td><td>d d b e c</td></tr></tbody></table>

Below we give all 31 states, with the usual notation.

ab c+ abc e+
ac d+ abd c+
a b+ ad b+ abe c+
b c+ ae b+ acd b+ abcd e+
c a+ bc a+ ace b+ abc e a-
d b+ bd c+ ade b+ abde c+ abcde a-
e a+ be c+ bcd a+ acde b+
cd b+ bce b-
ce a+ bde c+
de a+ cde a+

Here is now a counterexample for the uncovered set rule. Here we represent the majority graph by its adjacency matrix. The tie-breaking rule is $a \triangleright b \triangleright d \triangleright c \triangleright e$.

<table><thead><tr><th></th><th>a b c d e</th><th>a b c d e</th></tr></thead><tbody><tr><th>a</th><td>0 0 0 1 0</td><td>a b c d e</td></tr><tr><th>b</th><td>1 0 1 0 0</td><td>e e e b b</td></tr><tr><th>c</th><td>1 0 0 1 0</td><td>c c d a a</td></tr><tr><th>d</th><td>0 1 0 0 1</td><td>b a a e c</td></tr><tr><th>e</th><td>1 1 1 0 0</td><td>d d b c d</td></tr></tbody></table>

ab e+ abc e+
ac b+ abd d-
a b+ ad c+ abe d+
b d+ ae d+ acd b+
c b+ bc e+ ace d+
d a+ bd a+ ade c+
e d+ be d+ bcd c-
cd b+ bce d+
ce d+ bde a+
de a+ cde e-

□

**Proposition 9** For the top cycle rule and $m = 7$ candidates, there are profiles without PSNE.

*Proof.* We give the majority graph, tie-breaking relation, and the (partially specified) candidates' preferences. The tie-breaking relation is $a \triangleright g \triangleright c \triangleright b \triangleright d \triangleright e \triangleright f$.
<figure><img src="image_10.png" /></figure>

a b c d e f g
a b c d e f g

c d c g
f b f d
g a g a
a f b b
d e e c
e g a f

abc f+ abcd f+

abd f+ abce b-

abe c+ abcf e+

abf e+ abcg f+

abg f+ abde d-

acd f+ abdf e+

ace g+ abdg f+

ab f+ acf e+ abef c+ abcde b-

ac f+ acg f+ abeg c+ abcdf e+

ad c+ ade c+ abfg e+ abcdg f+

ae d+ adf e+ acde g+ abcef b-

af e+ adg f+ acdf e+ abceg b-

ag e+ aef d+ acdg c- abcfg e+

bc a+ aeg d+ acef g+ abdef d-

a g+ bd a+ afg e+ aceg c- abdeg d- abcdef b-

b a+ be c+ bcd f+ acfg e+ abdfg e+ abcdeg b-

c f+ bf e+ bce g+ adef c+ abefg c+ abcdfg e+

d c+ bg f+ bcf e+ adeg b+ acdef g+ abcefg b- abcdef g-

e c+ cd g+ bcg f+ adfg e+ acdeg c- abdefg d-

f e+ ce g+ bde c+ aefg d+ acdfg e+ acdefg c-

g e+ cf e+ bdf e+ bcde e- acefg c- bcdefg c-

cg f+ bdg a+ bcdf e+ adefg b+

de c+ bef c+ bcdg a+ bcdef g+

df e+ beg d+ bcef g+ bcdeg c-

dg f+ bfg e+ bceg a+ bcdfg e+

ef c+ cde g+ bcfg e+ bcefg c-

eg d+ cdf e+ bdef a+ bdefg a+

fg e+ cdg c- bdeg a+ cdefg c-

cef g+ bdfg e+

ceg c- befg d+

cfg d+ cdef g+

def b+ cdeg c-

deg b+ cdfg e+

dfg e+ cefg c-

efg d+ defg b+

□
**Lemma 2.** For the veto rule $r$, if there exists $\Gamma = \langle X, V, r, C \rangle$ with no NE, then there exists $\Gamma' = \langle X', V', r, C' \rangle$ with no PSNE, where $|X'| = |X| + 1$.

*Proof.* Take $\Gamma$ with no PSNE, with $X = \{x_1, \dots, x_m\}$, and $n$ voters where $n$ is odd. Let $s(V, Y, x_i)$ denote the veto score of $x_i$ in $V^{\downarrow Y}$. Let $X' = X \cup \{x_{m+1}\}$, and $Q$ be the following $3n$-voter profile: for each vote $\succ_i$ in $V$ we have two identical votes $Q_i$, $Q_i'$ obtained from $\succ_i$ by adding $x_{m+1}$ in the bottom position, and one vote $Q_i''$ obtained from $\succ_i$ by adding $x_{m+1}$ in the top position. Finally, let $C'$ be the candidate profile obtained by adding $x_{m+1}$ at the bottom of every ranking of a candidate $x_i$, $i \le m$, and whatever ranking for $x_{m+1}$. Let $\Gamma' = \langle X', V', r, C' \rangle$

Let $Y \subseteq X$ and $Y' = Y \cup \{x_{m+1}\}$.

For all $x_i \in Y$, $s(Q, Y, x_i) = 3s(V, Y \setminus \{x_{m+1}\}, x_i)$; therefore, $r(Q^{\downarrow Y}) = r(V^{\downarrow Y})$. Because $Y$ is not a PSNE for $\Gamma$, some candidate $x_i \in X$ has a profitable deviation from $Y$ in $\Gamma$, thus $x_i$ has a profitable deviation from $Y$ in $\Gamma'$ too: $Y$ is not a PSNE in $\Gamma'$.

For all $x_i \in Y$, $s(Q, Y', x_i) = s(V, Y \setminus \{x_{m+1}\}, x_i) + 2n \ge 2n$, while $s(Q, Y', x_{m+1}) = n$; therefore, $r(Q^{\downarrow Y'}) = r(V^{\downarrow Y})$, and a profitable deviation from $Y$ in $\Gamma$ is also a profitable deviation from $Y'$ in $\Gamma'$: $Y'$ is not a PSNE in $\Gamma'$. $\square$