{'fraction_non_alphanumeric': 0.041289888648083105, 'fraction_numerical': 0.010630745086316418, 'mean_word_length': 4.2475, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 48, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 66, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Hybrid Elections Broaden Complexity-Theoretic Resistance to Control

Electoral control refers to attempts by an election's organizer ("the chair") to influence the outcome by adding/deleting/partitioning voters or candidates. The groundbreaking work of Bartholdi, Tovey, and Trick [BTT92] on (constructive) control proposes computational complexity as a means of resisting control attempts: Look for election systems where the chair's task in seeking control is itself computationally infeasible. We introduce and study a method of combining two or more candidate-anonymous election schemes in such a way that the combined scheme possesses all the resistances to control (i.e., all the NP-hardnesses of control) possessed by any of its constituents: It combines their strengths. From this and new resistance constructions, we prove for the first time that there exists an election scheme that is resistant to all twenty standard types of electoral control.


Introduction
Elections are a way of, from a collection of voters' (or agents') individual preferences over candidates (or alternatives), selecting a winner (or outcome). The importance of and study of elections is obviously central in political science, but also spans such fields as economics, mathematics, operations research, and computer science. Within computer science, the applications of elections are most prominent in distributed AI, most particularly in the study of multiagent systems. For example, voting has been concretely proposed as a computational mechanism for planning [3,4] and has also been suggested as an approach to collaborative filtering [5]. However, voting also has received attention within the study of systems. After all, many distributed algorithms must start by selecting a leader, and election techniques have also been proposed to attack the web page rank aggregation problem and the related issue of lessening the spam level of results from web searches [6,7]. Indeed, in these days of a massive internet with many pages, many surfers, and many robots, of intracorporate decision-making potentially involving electronic input from many units/individuals/warehouses/trucks/sources, and more generally of massive computational settings including many actors, it is easy to note any number of situations in which elections are natural and in which the number of candidates and/or voters might be massive. For example, suppose amazon.com were to select a "page of the week" via an election where the candidates were all its web pages and the voters were all visiting surfers (with preferences inferred from their page-viewing times or patterns); such an election would have an enormous number of candidates and voters. All these applications are exciting, but immediately bring to a theoretician's mind the worry of whether the complexity of implementing election systems is satisfyingly low and whether the complexity of distorting (controlling or manipulating) election systems is reassuringly high.
Along these lines, though in a time when the importance of large-scale elections was less crystal clear than it is today, a remarkable series of papers by Bartholdi, Orlin, Tovey, and Trick [8,9,10,2] pioneered the study of the complexity of the winner, control, and manipulation problems for election systems (see [11] for a related survey). Of these, the winner and manipulation problems have since been studied particularly intensely. It is known, for example, that even for some quite natural, simple-to-state election systemssuch as those of Lewis Carroll [12], Kemeny (see [13]), and Young [14,15]-checking whether a given candidate wins is complete for the "parallel access to NP" level of the polynomial hierarchy [16,17,18].
Since the complexity of elections is a topic whose importance has made itself clear, it is natural to ask whether the standard tools and techniques of complexity-theoretic study exist in the context of elections. One important technique in complexity is the combination of problems. For example, for sets in complexity theory, a standard approach to combination is the join (also known as the disjoint union and as the marked union): A ⊕ B = {0x | x ∈ A} ∪ {1y | y ∈ B}. Even this simple example is not as innocent as it seems. Though the join indeed has many nice properties regarding respecting simplicity (e.g., if A ∈ P and B ∈ P, then A ⊕ B ∈ P) and preserving hardness (e.g., if C ≤ p m A or C ≤ p m B, then C ≤ p m A ⊕ B), it is known that the join has the quite unexpected ability of lower complexity within the extended low hierarchy ( [19]; that result should probably best be taken as suggesting that the definition of the extended low hierarchy-back in 1986 [20]was itself somewhat unnatural, or at least left itself open to this unusual behavior).
In some sense, our work in this paper can be thought of as simply providing, for elections, an analog of the join. That is, we will propose a method of combining two (or more) elections in a way that will maintain desirable simplicity properties (e.g., if all of the constituent elections have polynomial-time winner algorithms then so will our combined election) while also inheriting quite aggressively desirable hardness properties (we will show that any resistance-to-control-in the sense that is standard [2] and that we will provide a definition of later-possessed by even one of the constituent elections will be possessed by the combined election). One cannot directly use a join to achieve this, because the join of two sets modeling elections is not itself an election. Rather, we must find a way of embedding into election specifications-lists of voter preferences over candidates-triggers that both allow us to embed and switch between all the underlying election systems and to not have such switching go uncontrollably haywire when faced with electoral distortions such as adding/deleting/partitioning voters/candidates, since we wish hardness with respect to control by such mechanisms to be preserved.
We above have phrased this paper's theme as the development of a way of combining multiple election systems-and in doing so, have desirable types of simplicity/complexity inheritance. However, this paper also has in mind a very specific application-both for its own interest and as a sounding board against which our election hybridization scheme can be tested. This application is the control of election systems.
In election control, we ask whether an election's organizer (the chair) can by some specific type of manipulation of the election's structure (adding/deleting/partitioning voters/candidates) cause a specified candidate to be the (unique) winner. As mentioned earlier, the complexity-theoretic study of control was proposed by Bartholdi, Tovey, and Trick in 1992 [2]. We will closely follow their model. In this model, the chair is assumed to have knowledge of the vote that will be cast by each voter, 1 and there are ten different types of control (candidate addition, candidate deletion, voter addition, voter deletion, partition of candidates, run-off partition of candidates, and partition of voters [2]-and for each of the three partition cases one can have subelection ties promote or can have subelection ties eliminate, see [21]). Though Bartholdi, Tovey, and Trick's control paper is lovely and powerful, very few subsequent papers have extended beyond their results. One particular one that has is a 1 [2], in this regard, takes the view that all voters vote sincerely, and makes the good point regarding the chair's global knowledge that such global knowledge is perhaps not a realistic assumption but rather is a "conservative" one-that they show that even in the face of an omniscient chair, the control problems for certain voting systems are intractable. We heartily agree with the latter point, but regarding the former point mention that one does not need to assume voter sincerity. Rather, their model simply assumes that the chair knows how each voter will vote, and it is irrelevant whether such votes are or are not sincere-at least if our model is that the votes are fixed before the chair makes his or her decisions regarding how to assert control. paper of Hemaspaandra, Hemaspaandra, and Rothe [21] that asks the same questions for destructive control, i.e., when the chair's goal is to preclude a given candidate from being the (unique) winner. (One might ask if such study is a waste of time, given that any sane chair would vastly prefer to choose the winner than to just keep some particular hated choice from being the winner. However, [21] shows that for some standard election systems and types of control the former problem is intractable yet the latter is in P. That is, spoiling a candidate's chances can be easier than outright controlling who wins.) Of course, the dream case would be to find an election system that has the desirable property of having a polynomial-time algorithm for evaluating who won, but that also has the property that for every single one of the twenty standard types of control (namely, the standard ten types, each for the constructive and destructive cases) it is computationally infeasible (NP-hard) to assert such control. Unfortunately, no system yet has been proven resistant to all twenty types of control. In fact, given that broad "impossibility" results exist for niceness of preference aggregation systems (e.g., Arrow's Theorem [22]) and for nonmanipulability of election systems (e.g., the Gibbard-Satterthwaite and Duggan-Schwartz Theorems ( [23,24,25], see also [26])), one might even momentarily wonder whether the "dream case" mentioned above can be proven impossible via proving a theorem of the following form: "For no election system whose winner complexity is in P are all twenty types of control NP-hard." However, such a claim is proven impossible by our work: Our hybrid system in fact will allow us to combine all the resistance types of the underlying elections. And while doing so, it will preserve the winner-evaluation simplicity of the underlying elections. Thus, in particular, we conclude that the "dream case" holds: There are election systems-for example, our hybridization of plurality, Condorcet, and an election system we call E not-all-one (which will be defined in Section 3.2)-that are resistant to all twenty types of control (Theorem 3.11).
This paper (in its conference version) was the first to prove any election system to be resistant to even the ten constructive control types. And it was only in 2008, in the work of [27], that it was shown that some natural system also had those ten constructive-control resistances. (The largest resistance count among the twenty standard control types that has yet been obtained by any work other than that of the present paper-which obtains all twenty resistances-was obtained by Erdélyi, Nowak, and Rothe [28], who proved that a variant of approval voting has seventeen of the twenty resistances. However, to do so that paper adopts a different model-one in which each voter's preference consists of both a strict ordering and an approval vector.) It remains an open issue whether any previously studied (i.e., "natural") system has all twenty resistances.
Our hybridization system takes multiple elections and maintains their simplicity while inheriting each resistance-to-control possessed by any one of its constituents. Thus, it in effect unions together all their resistances-thus the "broaden" of our title. 2 The work most closely related to that of this paper is the constructive control-defining work of Bartholdi, Tovey, and Trick [2], the destructive control-defining work of Hemaspaandra, Hemaspaandra, and Rothe [21], and the control studies of Erdélyi, Nowak, and Rothe [31,28], Faliszewski et al. [32,27], and Procaccia, Rosenschein, and Zohar [33]. Work on bribery is related to this paper, in the sense that bribery can be viewed as sharing aspects of both manipulation and control [34,35]. Of course, all the classical [8,9,10] and recent papers (of which we particularly point out, for its broad framework and generality, the work of Spakowski and Vogel [36]) on the complexity of election problems share this paper's goal of better understanding the relationship between complexity and elections.
This paper is organized as follows. Section 2 provides the needed definitions regarding elections and control, defines and discusses our hybridization system, and defines and discusses the notions of inheritance that we will use to measure whether or not hybridization maintains or destroys desirable properties. Section 3 discusses the behavior of our hybrid system with respect to inheriting resistance (NP-hardness) to control, and also discusses the related notion of inheritance of susceptibility. Then it discusses the inheritances and noninheritances of our hybrid system with respect to vulnerability (having P-time control algorithms), and also discusses the related notion of immunity. Appendix A presents some proofs deferred from Section 3.4.
2 Elections, Control, Hybridization, and Inheritance: Definitions and Discussion

Elections
An election system (or election rule or election scheme or voting system) E is simply a mapping from (finite though arbitrary-sized) sets (actually, mathematically, they are multisets) V of votes (each a preference order-strict, transitive, and complete-over a finite candidate the winner) [9], there has been some work by Conitzer and Sandholm [29] regarding making manipulation hard, even for systems where it is not hard, by changing the system by going to a two-stage election in which a single elimination pre-round is added, and Elkind and Lipmaa [30] have generalized this to a sequence of elimination rounds conducted under some system(s) followed by an election under some other system. Though the latter paper like this paper uses the term "hybrid," the domains differ sharply and the methods of election combination are nearly opposite: Our approach (in order to broaden resistance to control) embeds the election systems in parallel and theirs (in order to fight manipulation) strings them out in sequence.
set 3 ) to (possibly empty, possibly nonstrict) subsets of the candidates. 4 All votes in a given V are over the same candidate set, but different V 's of course can be over different (finite) candidate sets. Each candidate that for a given set of votes is in E's output is said to be a winner. If for a given input E outputs a set of cardinality one, that candidate is said to be the unique winner. Election control focuses on making candidates be unique winners and on precluding them from being unique winners. Throughout this paper, a voter's preference order will be exactly that: a tie-free linear order over the candidates. And we will discuss and hybridize only election systems based on preference orders. 5 Following a convention that dates at least back to the early 1980s, we often will refer to the elements of V as "voters" rather than "votes." We now define two common election systems, plurality voting and Condorcet voting. In plurality voting, the winners are the candidates who are ranked first the most. In Condorcet voting, the winners are all candidates (note: there can be at most one and there might be zero) who strictly beat each other candidate in head-on-head majority-rule elections (i.e., get strictly more than half the votes in each such election). For widely used systems such 3 A subtle point is that, to be very careful, we should mention that though we above speak of E as if its input was just the votes (over a candidate set), to be utterly formal we tacitly view the candidate set itself as being also an input. It might be natural to think that taking such a view is unneeded, since we can infer the candidate set from the votes. However, that reasoning fails-though this boundary case seems to have been overlooked in some earlier work-if the cardinality of the vote set is zero. For example, the election rule under which all candidates always win very fundamentally needs to, when there are zero voters, know what the candidate set is, so it can know what winner names to output. Nonetheless, we will be careful in defining our hybrid scheme not to take unfair advantage of the fact that C is part of our input, formally speaking.
In the context of subelections we will sometimes speak of elections (C, V ) where C is a strict subset of the candidates that occur in V . In such cases, we view the preference orders in V as being restricted to C. 4 As is typical in papers on the complexity of voting, we study the case not of elections (actually, fullblown social choice functions) that output a full preference order (except with ties allowed), but rather we study the bare-bones but in practice very central case of elections where the focus is purely on selecting the winners.
As a somewhat arcane side comment, we mention that though many earlier papers imply that the latter is a special case of the former, this is not strictly true unless one restricts oneself to election rules always having at least one winner. Without that restriction, the problem is that the trick of declaring the top equality group of an output "preference order except with ties allowed" to be the winners breaks down since it has no way to declare that there are no winners (note that having all be equal would make them all winners; of course, we could when there are three or more candidates use, for example, c > b > a to code both c > b > a and c > a > b, since they both have the same winner set, "{c}," and we would thus free up c > a > b to denote "special case: no one wins". . . but this is such an exceedingly unnatural approach that we would not want to say that it shows that winner/loser elections with three or more candidates are a "special case" of general social choice functions). 5 Thus we do not directly discuss systems such as approval voting that take very different inputs: lists tagging each candidate as approved or not approved. However, we mention in passing that our hybridization approach works perfectly well for such systems and for them yields-if one codes the input as candidate lists tagged with an approval/disapproval bit-the same main results: The hybrid inherits all the resistance types of its constituent systems and yet has a polynomial-time winner algorithm if they all do. Thus the only reason we throughout this paper fix our systems as having preference orders as inputs is that it wouldn't even be particularly meaningful to try to hybridize together systems with conflicting input types, and by focusing just on preference-order-based preferences we prevent that from ever happening.
as plurality voting, we will write plurality rather than E plurality .
We say that an election system E is candidate-anonymous if for every pair of sets of votes V and V ′ , V = V ′ , such that V ′ can be created from V by applying some one-toone mapping h from the candidate names in V onto new candidate names in V ′ (e.g., each instance of "George" in V is mapped by h to "John" in V ′ and each instance of "John" in V is mapped by h to "Hillary" in V ′ and each instance of "Ralph" in V is mapped by h to "Ralph" in V ′ ) it holds that Informally put, candidate-anonymity says that the strings we may use to name the candidates are all created equal. Note that most natural systems are candidate-anonymous. For example, both the election systems mentioned immediately above-plurality-rule elections and the election system of Condorcet-are candidate-anonymous.
We mention that everywhere in this paper where we use assumptions of candidateanonymity (namely, in most of our inheritance results), our results would even hold under the far weaker assumption of candidate-affine-invariance, defined as follows. 6 We say that an election system E is candidate-affine-invariant if for every pair of sets of votes V and V ′ such that V ′ can be created from V by applying some mapping h of the form h(c) = k 1 c+k 2 , Note that when we treat candidate names as natural numbers (both above, and also later in defining our hybrid scheme), we are implicitly using the standard bijection between strings from Σ * (potential candidate names) and natural numbers, namely the ith string in lexicographical order is associated with the natural number i−1. Though as just mentioned candidate-affine-invariance suffices for all our results, we nonetheless use candidate-anonymity in our definitions and statements as candidate-anonymity seems a more natural notion. To avoid any confusion, we stress that k 1 is limited to N + and k 2 is limited to N, and so we are using the term "affine" somewhat improperly.
Finally, we mention that though related in flavor, candidate-anonymity is not identical to the political science notion of (candidate-)neutrality (see [22]), which is defined by 6 One should be a bit careful here. In many such cases, our existing proof already handles the case of candidate-affine-invariance, since the existing proof uses a transform of the form used in defining (as we are about to do in the main text) candidate-affine-invariance: h(c) = k1c + k2, k1 ∈ N + , k2 ∈ N. However, in some cases, rethinking the result in terms of candidate-affine-invariance requires revising the proof, most typically to either explicitly invoke the type of mapping used in defining candidate-affineinvariance, or to change the words "candidate-anonymous"/"candidate-anonymity" to the words "candidateaffine-invariant"/"candidate-affine-invariance" in some places, or to keep in mind that when considering this change one also should view all the underlying definitions-such as inheritance-as being framed in terms of candidate-affine-invariance (though, of course, in any case candidate-anonymity implies candidate-affineinvariance, so the remapping of the definition of inheritance is not truly needed when the inheritance appears only in the hypothesis of a particular theorem). As a specific example, note that to make Theorem 3.12's proof work for the case of candidate-affine-invariance, one would have to create that proof's set D from that proof's set C not by just using any mapping that ensures that D and C are disjoint, but rather by choosing a mapping that achieves disjointness and that also has the form h(c) = k1c + k2, k1 ∈ N + , k2 ∈ N; this can easily be done, e.g., by taking k1 = 1 and k2 sufficiently large.
saying that permuting the names of an election's candidates does not affect the outcome. 7 Candidate-anonymity implies neutrality but the converse does not in general hold as shown by the following example. The election system that ignores all the votes and declares all candidates winners if all candidates' names viewed as strings are of the same length and otherwise declares no candidates winners is neutral but not candidate-anonymous ("Bob" and "Joy" both win in the two-candidate election with (irrelevant) vote set V but changing "Bob" to "Bobby" changes the outcome). Candidate-anonymity, with its view of names as being coded as arbitrary strings, is a more "computer science"-y notion-focusing on actual codings, since sets are defined via (and machines accept) actual coded input strings.

Our Hybridization Scheme: Definition and Discussion
We now define our basic hybridization scheme, hybrid. To avoid long discussions about what properties of what we will call the "default" election rule are not needed or not inherited, we will first define a more general scheme, hybrid-base, and then will in defining hybrid simply fix the "default" election rule to be the same as the last regular constituent election rule. By doing so, our results will be stated in slightly less general ways than what actually holds, but the theorem statements will be simpler and clearer.
. . , E k−1 , and E default be election rules that take as input voters' preference orders. We define hybrid-base(E 0 , E 1 , . . . , E k−1 , E default ) to be the election scheme that does the following: If there is at least one candidate and all candidate names 8 are congruent, modulo k, to i (for some i, 0 ≤ i ≤ k − 1) then use election rule E i . Otherwise use E default .
We define hybrid(E 0 , E 1 , . . . , E k−1 ) to be the system hybrid-base(E 0 , E 1 , . . . , E k−1 , E k−1 ). We say that E 0 , E 1 , . . . , E k−1 are the constituents of hybrid(E 0 , E 1 , . . . , E k−1 ). Having defined our system there is much to discuss. Why did we choose this system? What are its properties? What other approaches did we choose not to use, and why? What aspects of the input is our method for switching between election systems using, and what aspects is it choosing not to exploit, and what are the costs associated with our choices?
As to the properties of this system, Section 3 is devoted to that, but most crucially we will see that this system possesses every resistance-to-control property possessed by even one of its constituents. And this will hold essentially due to the fact that hybrid is a close analog of the effect of a join: It splices the constituents together in such a way that key 7 Arrow [22] cites the origin of this notion to a paper by Guilbaud [37] and defines the Condition of Neutrality as follows: "Let T (x) be a one-one transformation of the set of alternatives into itself which preserves all individual orderings. Let the environment S be transformed into S ′ by the transformation T . Then the social choice from S, C(S), is transformed by T into the social choice, C(S ′ ), from the environment S ′ ." 8 Viewed as natural numbers via the standard bijection between Σ * and N mentioned in the discussion of candidate-anonymity.
questions about the constituent systems can easily be many-one polynomial-time reduced (≤ p m -reduced or reduced, for short) to questions about their hybrid. 9 As to why we chose this particular system, note that hybrid "switches" between constituent systems via wildly redundant information. This will let us keep deletions/partitions of voters/candidates from causing a switch between the underlying systems (if the starting state routed us to a nondefault case). Note that some other approaches that one might take are more sensitive to deletions. For example, suppose we wanted to hybridize just two election systems and decided to do so by using the first election system exactly if the first voter's most disliked candidate's name is lexicographically less than the first voter's second-most-disliked candidate's name. Note that if, as part of our control problem, that voter is deleted, that might suddenly change the system to which the problem is routed. Or, as another example, if we use the modulo k value of the name of the lexicographically smallest candidate to control switching between the k election systems, then that hybridization approach would be very sensitive to jumping between systems if, as part of our control problem, that candidate is deleted. These examples give some idea of why we chose the approach we did, though admittedly even it can in some cases be nudged into jumping between systems-but at least this happens in very limited, very crisply delineated cases and in ways that we will generally be able to appropriately handle.
Finally, we come to what we allow ourselves to use to control the switching, what we choose not to use, and what price we pay for our choices. What we use (as is allowed in the [2] model) are the candidates' names and only the candidates' names. We use absolutely nothing else to control switching between elections. We do not use voters' names. Indeed, in the [2] model that we follow, voters (unlike candidates) do not even have names. But since the votes are input as a list, their ordering itself could be used to pass bits of informatione.g., we could look at whether the first vote in the list viewed as a string is lexicographically less than the last vote in the list viewed as a string. We in no way "cheat" by exploiting such input-order information, either for the votes or for the list of candidates (as per Footnote 3, and as per [2], formally the candidate set is passed in separately to cover a certain boundary case). Our "switch" is based purely on candidates' names and just candidates' names. This also points to the price we pay for this choice: Even when all its constituent elections are candidate-anonymous, hybrid may not possess candidate-anonymity.

Types of Constructive and Destructive Control
Constructive control problems ask whether a certain class of actions by the election's chair can make a specified candidate the election's unique winner. Constructive control was first defined and studied by Bartholdi, Tovey, and Trick [2]. Destructive control problems ask whether a certain class of actions by the election's chair can make a specified candidate fail to be a unique winner of the election. Destructive control was defined and studied by Hemaspaandra, Hemaspaandra, and Rothe [38,21], and in the different context of electoral 9 We mention in passing that this is one of the reasons we focus on hybrid rather than hybrid-base. It is possible to construct artificial systems for which even the winner problem for a system ED does not ≤ p m -reduce to hybrid-base(E0, E1, . . . , E k−1 , ED). manipulation destruction was introduced even earlier by Conitzer, Lang, and Sandholm [39,40,41]. Bartholdi, Tovey, and Trick's [2] groundbreaking paper defined seven types of electoral control. Among those seven, three are partition problems for which there are two different natural approaches to handling ties in subelections (see [21] which introduced these tiehandling models for this context): eliminating tied subelection winners (the "TE" model) or promoting tied subelection winners (the "TP" model). Thus, there are (7 − 3) + 2 · 3 = 10 different standard types of constructive control, and there are essentially the same ten types of destructive control.
Since it is exceedingly important to not use a slightly different problem statement than earlier work whose results we will be drawing on, we will state the seven standard constructive control types (which become ten with the three partition control types each having both "TE" and "TP" versions) and their destructive analogs using word-for-word definitions from [21,38,42], which themselves are based closely and often identically on [2] (see the discussion in [21]).
Though V , the set of votes, is conceptually a multiset as in the previous related work, we take the view that the votes are input as a list ("the ballots"), and in particular are not directly input as a multiset in which cardinalities are input in binary (though we will mention later that our main result about hybrid holds also in that quite different model).

Control by Adding Candidates
As is common, we state our decision problems as "Given" instances, and a related Yes/No question. The language in each case is the set of all instances for which the answer is Yes. (So we are studying the complexity of recognizing the set of instances on which control is possible.) Since in each control scenario, the "Given" instance is identical for the constructive and the destructive case, we state it just once and then state the corresponding two questions, one for constructive and one for destructive control.
Given: A set C of qualified candidates and a distinguished candidate c ∈ C, a set D of possible spoiler candidates, and a set V of voters with preferences over C ∪ D.

Question (constructive):
Is there a choice of candidates from D whose entry into the election would assure that c is the unique winner?
Question (destructive): Is there a choice of candidates from D whose entry into the election would assure that c is not the unique winner?
This problem captures whether adding candidates can make a candidate the victor or can block such. 10 10 The notion, as we have stated it, is the notion proposed by Bartholdi, Tovey, and Trick [2] as "Adding Candidates." However, [32,27] recently defined and highly commended an eleventh control type-adding a number of candidates for the "limited" case where a bound on the maximum number of candidates that can be legally added is itself part of the input. We mention that the techniques of the current paper apply

Control by Deleting Candidates
Given: A set C of candidates, a distinguished candidate c ∈ C, a set V of voters, and a positive integer k < C .
Question (constructive): Is there a set of k or fewer candidates in C whose disqualification would assure that c is the unique winner?
Question (destructive): Is there a set of k or fewer candidates in C − {c} whose disqualification would assure that c is not the unique winner?
This problem models vote suppression. (The choice to have a k for candidate deletion and voter addition/deletion but not for candidate addition is somewhat arbitrary, but was a decision made explicitly by Bartholdi, Tovey, and Trick [2], and for consistency and comparison purposes, we follow their choice.) Note that deleting the distinguished candidate c in the destructive case, which would trivialize the problem, is not allowed.

Control by Partition of Candidates
Given: A set C of candidates, a distinguished candidate c ∈ C, and a set V of voters.
Question (constructive): Is there a partition of C into C 1 and C 2 such that c is the unique winner in the sequential two-stage election in which the winners in the subelection (C 1 , V ) who survive the tie-handling rule move forward to face the candidates in C 2 (with voter set V )?
Question (destructive): Is there a partition of C into C 1 and C 2 such that c is not the unique winner in the sequential two-stage election in which the winners in the subelection (C 1 , V ) who survive the tie-handling rule move forward to face the candidates in C 2 (with voter set V )?

Control by Run-off Partition of Candidates
Given: A set C of candidates, a distinguished candidate c ∈ C, and a set V of voters.
Question (constructive): Is there a partition of C into C 1 and C 2 such that c is the unique winner of the election in which those candidates surviving (with respect to the tie-handling rule) subelections (C 1 , V ) and (C 2 , V ) have a run-off with voter set V ?
perfectly well to that case too, and so in particular the techniques of the present paper easily yield that there is a hybrid election system that is resistant to all twenty-two control types (the twenty standard ones plus the constructive and destructive limited-candidate-addition cases). The reason we can make this comment is that there are systems resistant to constructive limited-candidate-addition and there are systems resistant to destructive limited-candidate-addition; for example, plurality has both these properties (see the discussion in the caption of Table 1 of [43]).

Question (destructive):
Is there a partition of C into C 1 and C 2 such that c is not the unique winner of the election in which those candidates surviving (with respect to the tie-handling rule) subelections (C 1 , V ) and (C 2 , V ) have a run-off with voter set V ? These two problems model two natural ways of conducting partitioned elections: either via an elimination pre-round involving some candidates or as a run-off structure (3-node tree).

Control by Adding Voters
Given: A set of candidates C and a distinguished candidate c ∈ C, a set V of registered voters, an additional set W of yet unregistered voters (both V and W have preferences over C), and a positive integer k ≤ W .

Question (constructive):
Is there a set of k or fewer voters from W whose registration would assure that c is the unique winner?
Question (destructive): Is there a set of k or fewer voters from W whose registration would assure that c is not the unique winner?

Control by Deleting Voters
Given: A set of candidates C, a distinguished candidate c ∈ C, a set V of voters, and a positive integer k ≤ V .

Question (constructive):
Is there a set of k or fewer voters in V whose disenfranchisement would assure that c is the unique winner?
Question (destructive): Is there a set of k or fewer voters in V whose disenfranchisement would assure that c is not the unique winner?

Control by Partition of Voters
Given: A set of candidates C, a distinguished candidate c ∈ C, and a set V of voters.

Question (constructive):
Is there a partition of V into V 1 and V 2 such that c is the unique winner in the hierarchical two-stage election in which the survivors of (C, V 1 ) and (C, V 2 ) run against each other with voter set V ?
Question (destructive): Is there a partition of V into V 1 and V 2 such that c is not the unique winner in the hierarchical two-stage election in which the survivors of (C, V 1 ) and (C, V 2 ) run against each other with voter set V ? These three problems model control by addition, deletion, and partition of voters.

Immunity, Susceptibility, Vulnerability, and Resistance
Again, to allow consistency with earlier papers and their results, we take this definition from [21,38,42], with the important exception regarding resistance discussed below Definition 2.2. It is worth noting that immunity and susceptibility both are "directional" (can we change this?) but that vulnerability and resistance are, in contrast, outcome-oriented (can we end up with this happening?) and complexity-focused.

Definition 2.2
We say that a voting system is immune to control in a given model of control (e.g., "destructive control via adding candidates") if the model regards constructive control and it is never possible for the chair to by using his/her allowed model of control change a given candidate from being not a unique winner to being the unique winner, or the model regards destructive control and it is never possible for the chair to by using his/her allowed model of control change a given candidate from being the unique winner to not being a unique winner. If a system is not immune to a type of control, it is said to be susceptible to that type of control.
A voting system is said to be (computationally) vulnerable to control if it is susceptible to control and the corresponding language problem is computationally easy (i.e., solvable in polynomial time).
A voting system is said to be resistant to control if it is susceptible to control but the corresponding language problem is computationally hard (i.e., NP-hard).
We have diverged from all previous papers by defining resistance as meaning NPhardness (i.e., NP-≤ p m -hardness) rather than NP-completeness (i.e., NP-≤ p m -completeness). Though revising existing notions always holds the danger of sowing confusion, in this particular case the redefinition is compelling. Under the [2] "NP-complete" definition, a problem whose control issue is NP-complete is resistant but a problem whose control issue is NEEEEcomplete-or even undecidable-would actually be provably not resistant. This is totally at odds with the intent of the notion of being resistant to control. In [2], all their problems happened to be not just NP-hard but also NP-complete, but that certainly is not a reason to define a "difficulty level" concept in terms of a notion-NP-completeness-that encapsulates both a difficulty notion (NP-hardness) and a simplicity notion (membership in NP).
Thus we redefine resistance to mean NP-hardness. This redefinition was already praised, though not adopted, in [21,Footnote 9]. Note that all existing resistance results (under the old definition) imply resistance under the new definition-which should lessen the potential for confusion.
As a final comment on this redefinition, we above casually mentioned that control problems might in difficulty exceed NP-completeness. But can that really occur in truly natural systems? The answer is yes. In particular, note that the unique winner problem for any election system (with preference orders) reduces to its constructive control by adding candidates problem (by setting the spoiler candidate set D to ∅), to its constructive control by deleting candidates problem (by setting the deletion limit k to 0), to its constructive control by adding voters problem (by setting the addition bound k to 0), and to its constructive control by deleting voters problem (by setting the deletion limit k to 0). Thus every system with a hard winner problem has four control problems that are at least as hard. Note that Dodgson [12], Kemeny [13], and Young [14,15] elections are much-studied natural systems whose winner problem (but defined in terms of "winner," not "unique winner") is known-respectively due to [16], [18], and [17]-to be complete for the Θ p 2 level [44,45] of the polynomial hierarchy (a level that contains NP, coNP, and the boolean hierarchy [46], so if even one Θ p 2 -hard set is NP-complete then the polynomial hierarchy collapses to NP). From this and the above comments, it follows that the four mentioned control problems are Θ p 2 -hard for each of Dodgson, Kemeny, and Young elections when the control problems are altered to speak of "winner" rather than "unique winner" (this alteration is not the model of this paper or any previous paper on control). However, we observe by close inspection that in all of [16,18,17], the proofs that establish Θ p 2 -hardness for the Dodgson, Kemeny, and Young election winner problems can be modified to show that their unique winner problems are also Θ p 2 -hard. 11 Thus, we may state the following. 11 As mentioned above, the winner problems for Dodgson [12], Kemeny [13], and Young [14,15] elections are known-respectively due to [16], [18], and [17]-to be complete for Θ p 2 , the complexity class capturing "parallel access to NP." In this footnote, we show the analogous results for the unique winner problems. (See the above papers and [8] for the definitions of these three election systems and of Dodgson score.) The unique winner problem for Dodgson elections is Θ p 2 -complete. The unique winner problem for Kemeny elections is Θ p 2 -complete. The unique winner problem for Young elections is Θ p 2 -complete.
Proof. Θ p 2 -completeness of the winner problem for Dodgson elections was shown in [16]. The Θ p 2 upper bound is easy to show, and the same argument can be used to show a Θ p 2 upper bound for the unique winner problem. It remains to show that the unique winner problem for Dodgson elections is Θ p 2 -hard. Θ p 2 -hardness of the winner problem for Dodgson elections was shown by a reduction from the Θ p 2 -hard problem Two-Election Ranking (2ER, for short) [16]: Given two Dodgson triples (C, c, V ) and (D, d, W ), where both V and W are odd and c = d, is the Dodgson score of c in (C, V ) less than or equal to the Dodgson score of d in (D, W )? A Dodgson triple (C, c, V ) is an election (C, V ) with a designated candidate c ∈ C.
The reduction from 2ER to the winner problem for Dodgson elections [16] has the property that if an . Thus the complement of the unique winner problem for Dodgson elections is Θ p 2 -hard. Since Θ p 2 is closed under complement, the unique winner problem for Dodgson elections is also Θ p 2 -hard. Θ p 2 -completeness of the winner problem for Kemeny elections was shown in [18]. The Θ p 2 upper bound is easy to show, and the same argument can be used to show a Θ p 2 upper bound for the unique winner problem. It remains to show that the unique winner problem for Kemeny elections is Θ p 2 -hard. Θ p 2 -hardness of the winner problem for Kemeny elections was shown by a reduction from the Θ p 2 -hard problem Feedback Arc Set Member [18]: Given an irreflexive and antisymmetric digraph G and a vertex c of G, does there exist a minimum-size feedback arc set of G that contains all arcs entering c? A feedback arc set of G is a set of arcs that contains at least one arc from every cycle in G.
The reduction from Feedback Arc Set Member to the winner problem for Kemeny elections [18, Lemma 4.2] works as follows. There is a polynomial-time computable function g such that for all irreflexive and antisymmetric digraphs G, g(G) is an election whose candidates are the vertices of G and such that for all vertices c of G, (G, c) is in Feedback Arc Set Member if and only if c is a Kemeny winner of election g(G). An anonymous referee commented that even polynomial-time algorithms can be expensive to run on sufficiently large inputs. We mention that though the comment is correct, almost any would-be controller would probably much prefer that challenge, solving a P problem on large inputs, to the challenge our results give him/her, namely, solving an NPcomplete problem on large inputs. We also mention that since the hybrid scheme is designed so as to inherit resistances from the underlying schemes, if a hybrid requires extreme ratios between the number of candidates and the number of voters to display asymptotic hardness, that is purely due to inheriting that from the underlying systems. Indeed, if anything the hybrid is less likely to show that behavior since, informally put, if even one of the underlying systems achieves asymptotic hardness even away from extreme ratios between the number of candidates and the number of voters, then their hybrid will also.

Inheritance
We will be centrally concerned with the extent to which hybrid(E 0 , E 1 , . . . , E k−1 ) inherits the properties of its constituents. To do so, we formally define our notions of inheritance G, c) is in Feedback Arc Set Member, we have obtained a polynomial-time reduction from Feedback Arc Set Member to the complement of the unique winner problem for Kemeny elections. Since Θ p 2 is closed under complement, this proves that the unique winner problem for Kemeny elections is Θ p 2 -hard. Θ p 2 -completeness of the winner problem for Young elections was shown in [17]. The Θ p 2 upper bound is easy to show, and the same argument can be used to show a Θ p 2 upper bound for the unique winner problem. Θ p 2 -hardness of the winner problem for Young elections was shown as Theorem 2.5 in [17] via a reduction from the Θ p 2 -complete problem Maximum Set Packing Compare (MSPC, for short) [17]: Given two sets, B1 and B2, and two collections of sets, S1 and S2, where each S ∈ Si is a nonempty, finite subset of Bi, is it the case that κ(S1) ≥ κ(S2)? Here, κ(Si) denotes the maximum number of pairwise disjoint sets in Si.
The proofs of Theorems 2.3 and 2.5 in [17] show how to construct from a given MSPC instance I = (B1, B2, S1, S2) an election (C, V ) with two designated candidates, c and d, such that (a) if κ(S1) ≥ κ(S2) then c and d are Young winners of (C, V ), and (b) if κ(S2) > κ(S1) then d is the unique Young winner of (C, V ). It follows that I is in MSPC if and only if d is not the unique Young winner of (C, V ). Thus the complement of the unique winner problem for Young elections is Θ p 2 -hard. Since Θ p 2 is closed under complement, this proves that the unique winner problem for Young elections is Θ p 2 -hard. u (if all the constituents have a property then so does their hybrid) and of strong inheritance (if even one of the constituents has a property then so does the hybrid).
Definition 2. 5 We say that a property Γ is strongly inherited (respectively, inherited) by hybrid if the following holds: Let k ∈ N + . Let E 0 , E 1 , . . . , E k−1 be candidate-anonymous election systems (each taking as input (C, V ), with V a list of preference orders). It holds that hybrid(E 0 , E 1 , . . . , E k−1 ) has property Γ if at least one of its constituents has (respectively, all its constituents have) property Γ.
Definition 2.5 builds in the assumption that all constituents are candidate-anonymous. This assumption isn't overly onerous since as mentioned earlier candidate-anonymity is very common-but will be used in many of our proofs. In effect, it is the price we pay for our choice of "switching between systems" rule within hybrid. One might naturally worry that as hybrid is not itself candidate-anonymous, inheritance results might be difficult to prove for a hybrid of hybrids. That is true, but before reaching such an impasse one would typically avoid it, namely, instead of trying to study . Though there of course are issues regarding default handling, in most settings this will not have problems, and in fact we will do precisely this later (in the proof of Theorem 3.11).
Though we will build candidate-anonymity into the assumptions underlying inheritance, we will often try to let interested readers know when that assumption is not needed. In particular, when we say "inherited (and flexibly so)" or "strongly inherited (and flexibly so)," the "(and flexibly so)" indicates that the claim holds even if in Definition 2.5 the words "candidate-anonymous" are deleted. For example, the following easy but quite important claim follows easily from the definition of hybrid. Proposition 2.6 "Winner problem membership in P" and "unique winner problem membership in P" are inherited (and flexibly so) by hybrid.
That is, if E 0 , E 1 , . . . , E k−1 are election rules (all, as we assume globally, based on input preference orders) for which testing whether a given candidate is the winner is in P (i.e., {(C, V, c) | c is a winner in the election specified by (C, V )} ∈ P), then the winner problem for hybrid(E 0 , E 1 , . . . , E k−1 ) is also in P. We similarly have that the following claim follows easily from the definition of hybrid. Proposition 2.7 "Winner problem membership in NP" and "unique winner problem membership in NP" are inherited (and flexibly so) by hybrid.
(In fact, it is easy to see that when the constituent systems are candidate-anonymous then, for each k ≥ 0, it holds that the winner problem (respectively, unique winner problem) of hybrid is in Σ p k if and only if all the constituent winner problems (respectively, unique winner problems) are in Σ p k , where Σ p k as is standard denotes the kth level of the polynomial hierarchy.) On the other hand, sometimes we will want to focus just on elections having a certain property Φ, and for those we use the following definition.
Definition 2. 8 We say that a property Γ is strongly inherited (respectively, inherited) by hybrid on election systems having property Φ if the following holds: Let k ∈ N + . Let E 0 , E 1 , . . . , E k−1 be candidate-anonymous election systems (each taking as input (C, V ), with V a list of preference orders) each having property Φ. It holds that hybrid(E 0 , E 1 , . . . , E k−1 ) has property Γ if at least one of its constituents has (respectively, all its constituents have) property Γ.

Discussion of Some Concrete Objections
It is important when presenting an election system to make clear what the purpose of defining it is and how it is intended to be used. This was already discussed in part in Sections 1 and 2.2. However, we now have defined for the reader our hybridization scheme and key notions such as control and inheritance, and so we are in a better position to be able to address potential worries. So, as a way both of recapping some of the points of Sections 1 and 2.2 and of making some additional important points about the nature of our hybridization system, we will now state and discuss some interesting issues that one might wonder about.
One natural issue is that our model is about worst-case hardness and so may not speak to typical (frequent) hardness. One anonymous referee observed that since the vast majority of the inputs will have mismatches in the moduli of the names (i.e., will have mismatches in what the input names are congruent to modulo k) and so will map to the default system, the election systems other than the default one "do not really matter." This actually raises a number of issues. We will try to now address them briefly but clearly.
First, and most importantly, the core purpose of the hybrid scheme is not to be a system that is used directly as a practical, real-world election system, but rather is, as discussed in the introduction, to show that the impossibility result: "For no election system whose winner complexity is in P are all twenty types of control NP-hard." outright does not hold. And by showing that we can combine control resistances while not boosting the complexity of the winner problem beyond P, our hybrid scheme in fact breaks all hope of such an impossibility result, via showing that there is an election system whose winner complexity is in P yet for which all twenty types of control are NP-hard (Theorem 3.11).
Second, the hybrid scheme's point is to in effect "join" its underlying systems. It provides a one-stop system that allows one (by appropriately renaming the candidates) to get the effect of any one of the underlying systems (assuming candidate-anonymity holds for those).
As to the referee's comment that the vast majority of the inputs will have mismatches in the moduli of the names and so will map to the default system, and so the election systems other than the default one "do not really matter," the comment works best if one views the entire hybrid as a stand-alone system intended for direct, natural use, and if one further feels that such use should be with respect to a uniform distribution of inputs directly to hybrid. But as argued in the previous paragraph, the hybrid scheme is not intended as a system for direct, natural, real-world use; it is built to give insight into inheritance of control resistance and most critically into (non)existence of impossibility results. Further, even if one did want to look at the system relative to a uniform notion of inputs, given that the system (as mentioned at the start of the present paragraph) is intended to combine k systems, the natural notion of a uniform input draw would be to randomly choose one of the k systems, randomly generate an instance there, and then mod-encode the names to place that instance into the hybrid scheme. Note that in this approach/distribution, the frequency of having inputs route to the default system due to name moduli mismatches would not be very frequent but would be "absolutely never." (As a very loose and admittedly imperfect analogue, if one types random keystrokes, one is very unlikely to get a Boolean formula that is syntactically well-formed. And so relative to an utterly uniform distribution of that sort, SAT becomes trivial in the vast majority of cases. For us, agreement of name moduli is a form of syntactic filter used to discipline the input, and inputs lacking agreement are swept to the default system.) Third, let us make clear that there is a very real, important issue in the concrete objection being discussed. Namely, what about frequency of hardness, or even about average-case hardness? Clearly, the hypothetical impossibility theorem above itself includes the notion of NP-completeness, which is a worst-case theory, rather than one focused on either averagecase NP-hardness or frequency of hardness. It is indeed very natural to hope to achieve average-case NP-hardness or frequency of hardness results. We fully agree that this is a very interesting, important long-term issue. But we briefly mention some cautions and limitations. Regarding average-case NP-hardness, a well-known theory developed by Levin [47], the theory is lovely, but only a handful of problems have been shown to be average-case NP-hard, and not a single one of those in any way involves elections. Regarding frequency of hardness, there have been a number of recent results showing that certain NP-hard election issues can be frequently simple, but to the best of our knowledge, none of those papers obtains such results for any control problem. 12 Briefly summarized, issues of average-case NP-hardness and of frequency of correctness are clearly very interesting, are rightly gaining attention, and we highly commend them to the reader while also mentioning that the field's understanding of such results and ability to obtain them is still very limited and currently doesn't exist at all for the case of control problems (except see the comment of the next paragraph, which in a sense says that our work at least preserves good behavior in this regard).
Still continuing on this third point, however, namely of frequency of hardness, in the particular case of the present paper's work we do have a case where-in a certain rigorous sense that is theoretically crisp although practically quite unsatisfying-inheritance of hardness does hold. In particularly, it is clear, directly from our definitions, that hardness inherits under our scheme-indeed, that hardness strongly inherits under our scheme. In particular, if even just one of the constituent systems (all required to be candidate anonymous) is 12 All such work that we know of regards winner and manipulation problems, not control problems, and even for the winner and control cases such results typically require one to choose the distribution very carefully. For example, the work of [48,49] and [50] succeeds in the uniform distribution, but is not known to hold under other distributions, and anyway is about winner problems and not about control or manipulation. And in the interesting work of [51], which is about manipulation (not about control), the frequency of being able to manipulate is conditioned inside the set of cases that are manipulable at all. For the one concrete distribution family on which that paper does experiments, it is easy to see that except for the special case of the uniform distribution, "p = 0.5" in their notation, asymptotically the portion of cases that are manipulable is extraordinarily small (because whomever is at the top of what they call the "correct" ranking will as the number of voters grows, win by a large amount when p = 0.5). So what one should take away is not that the election systems are almost always easily manipulable, but rather that the election system they studied are, for that distribution, almost never manipulable (but nonetheless that, and this is that paper's remarkable insight, conditioning within the extraordinarily low probability-weight of instances in which they are manipulable, one can with high probability easily find a manipulation, again with this all framed within that distribution). Without trying to here list all the other interesting papers addressing issues of frequency of correctness, as there are many and all of them are not about the present paper's focus (namely, control), we mention as particularly interesting (and provocative) the work of Procaccia and Rosenschein on juntas and manipulation [52], the Procaccia and Rosenschein fraction-of-manipulators work [53], the work of Friedgut, Kalai, and Nisan on random manipulations [54], and the Zuckerman, Procaccia, and Rosenschein work on coalition manipulation [55]. exponentially often exponentially hard, then so is the hybridization of those systems. The catch here is that it is a "small" exponential regarding the frequency of hardness, namely 2 Ω(n) , and so it ensures an exponentially rich core of hard instances, but it still could be the case that the overwhelming majority of instances are easy. 13 However, we should not allow ourselves to be overly sidetracked. The main points here are simply that our hybrid system is primarily designed to show that control can be strongly inherited, and it does so and thus completely rules out the natural, potential impossibility result. And that issues of frequency of hardness are indeed interesting, although difficult and typically very distribution-based, and deserve (and are getting) further investigation. Regarding the first of these points, one might ask whether one really needs an artificial system to preclude the impossibility result. The authors and P. Faliszewski have, motivated by the present paper, looked hard at this issue. As mentioned earlier, they have very recently shown (in [32] give or take one's view on a technical fine point, and in [27] regardless of one's view on the technical fine point) that there is a natural system-one of the versions of Copeland voting-that has a P winner problem yet is immune to all ten types of constructive control. However, that system is vulnerable to most types of destructive control. And so their work gives an alternate path to precluding a ten-constructive-case impossibility result, but unlike the present paper does not preclude the main goal-a twenty-case overall impossibility result-or even preclude a ten-destructive-case impossibility result.
This completes our discussion regarding whether systems other than the default really matter in hybrid, and of issues of average-case NP-hardness and frequency of hardness. We now turn to a second concrete worry one might have.
One anonymous referee proposed a different hybrid scheme than ours based on, on each input, randomly choosing a system to route the question to. Unfortunately, that approach to a hybrid scheme is not a valid election rule, as it uses probability not just to compute 13 For completeness, let us be specific as to what is being claimed. Let us say a problem A is exponentially often exponentially hard if there is an ǫ > 0 such that, for each Turing machine M accepting A, there are an infinite number of lengths n at which M runs for at least 2 ǫn steps on at least 2 ǫn of the strings of that length. Our theorem is this: Being exponentially often exponentially hard is strongly inherited (in the sense of Definition 2.5) by hybrid. This is true simply because the process of taking an instance from one of the constituent elections and recoding the names in the natural way to recast the instance into our hybrid scheme increases the instance's length at most linearly.
Our framing of this claim just said "there are an infinite number of lengths" at which the hardness holds, but note that, again due to the fact that we can achieve at-most-linear instance-length-stretching, whatever the original density of hard lengths is of the hard constituent system, the density of hard lengths in hybrid will be no more than linearly less. Informally put, we don't lose too much density of hard lengths.
We mention in passing that the above claim remains true if each 2 Ω(n) above is changed to 2 n Ω(1) , a different, even smaller notion of having exponentially many elements. Although 2 Ω(n) and 2 n Ω(1) are not practically very satisfyingly large when compared (regarding frequency) with 2 n , we mention that in theoretical computer science this type of density is very natural and typical in such settings. This is due to the fact that for each ǫ > 0, every NP-hard set A is, by standard padding arguments, known to be polynomial-time many-one equivalent to sets (e.g., {0 |x| k #x | x ∈ A}, where k is chosen to satisfy k > 1/ǫ) that for each n are trivial on all but 2 n ǫ of their length n strings. Indeed, for almost precisely this reason, Levin's theory of average-case NP-hardness [47] allows some sets that are trivial on all but at most 2 n ǫ of their length n strings to be average-case NP-hard.
something, but also its output itself is probabilistic. That is, if one were to repeatedly run the exact same set of completed ballots through that "rule," one would get different winners on different such runs. That isn't an election rule in the standard sense universally used to study control, and the reduction framework (that we ourselves exploit to prove hardness) does not apply to this. In addition, the present paper proves results for its system.
We now turn to a third concrete worry. Our paper's key tool is a hybrid scheme. We then apply it using certain building blocks (constituent election systems to be hybridized together). Let us say a voting system is voiced (see [21]) if (whenever there is at least one candidate) there will be at least one winner. Although nonvoiced systems have been allowed in the study of control in every paper we know of on control, one might dislike the fact that in some places in this paper we use building blocks that are not voiced (may sometimes have no winner). The two building blocks we use that are not voiced are Condorcet elections and an artificial election system we call E not-all-one . However, we point out that one can just as easily toss out those two building blocks and use instead any other existing system(s) that have the resistance properties that the discarded blocks were being used for and that in addition are voiced. Such systems have been proven (although just recently) to exist. Combined with the easy-to-see claim that voiced-ness inherits under our hybrid scheme, one can, if one dislikes nonvoiced systems, establish the theorems in question via a voiced hybrid of voiced systems. 14

Inheritance and Hybrid Elections: Susceptibility, Resistance, Immunity, and Vulnerability
In this section we will discuss the inheritance properties of hybrid with respect to susceptibility, resistance, immunity, and vulnerability. Tables 1 and 2 summarize our results for the cases of, respectively, constructive control and destructive control. (These tables do not discuss/include the issue of when "(and flexibly so)" holds, i.e., when the candidate-anonymity assumption is not needed, but rather focus on our basic inheritance definition.)

Susceptibility
We first note that susceptibility strongly inherits. In fact, we prove something slightly stronger, as for only the susceptible constituent do we need to assume candidate-anonymity (also, as noted in the introduction, candidate-affine-invariance would actually suffice). We remind the reader that throughout this paper, when we speak of an election system, we always implicitly mean an election system that takes as input (C, V ) (see Footnote 3) with V a list of preference orders over C.
14 To be utterly concrete about this, Condorcet voting is used in this paper for its resistance to constructive control by adding, deleting and partitioning of voters, and E not-all-one is used in this paper for its resistance to destructive control by adding, deleting and partitioning of voters (in the TE model). However, very recent work [32] has proven that the natural, voiced election system of Llull (and also the natural, voiced election system of Copeland and many variants [32,27]) itself has all of these resistance properties, and so one can, if one requires voiced systems, employ Llull elections here in place of both Condorcet and E not-all-one .
Proof. Take an example showing that E i is susceptible to Φ and rename each candidate c in it to now be named kc + i. This transformed example will, due to E i 's candidateanonymity, be an example showing hybrid(E 0 , E 1 , . . . , E k−1 )'s susceptibility to Φ. u We note in passing that there is nothing particularly limiting the above theorem to the standard twenty types of control. The embedding would work equally well on almost any natural control type one might imagine. Theorem 3.1 immediately yields the following corollary.
Corollary 3.2 hybrid strongly inherits susceptibility to each of the standard twenty types of control.

Resistance
We now come to the most important inheritance case, namely, that of resistance. Since our hope is that hybrid elections will broaden resistance, the ideal case would be to show that resistance is strongly inherited. And we will indeed show that, and from it will conclude that there exist election systems that are resistant to all twenty standard types of control. We first prove the key result, which uses the fact that hybrid can embed its constituents to allow us to ≤ p m -reduce from control problems about its constituents to control problems about hybrid. Theorem 3.3 Let k ∈ N + and let E 0 , E 1 , . . . , E k−1 be election systems. Let Φ be one of the standard twenty types of (constructive and destructive) control. If for at least one i, 0 ≤ i ≤ k − 1, E i is candidate-anonymous and resistant to Φ, then hybrid(E 0 , E 1 , . . . , E k−1 ) is resistant to Φ. 15

Proof.
Let Φ and i and E 0 , E 1 , . . . , E k−1 satisfy the conditions of the theorem. By Theorem 3.1, hybrid(E 0 , E 1 , . . . , E k−1 ) is susceptible to Φ, since E i 's resistance ensures that E i is susceptible. And since E i is resistant to Φ, the control problem for E i is NP-hard. Now, note that the control problem for E i with respect to Φ itself many-one polynomialtime reduces to the control problem for hybrid(E 0 , E 1 , . . . , E k−1 ) with respect to Φ, via the 15 A referee presented a "counterexample" that, though incorrect, is worth refuting so that no other reader need have the same worry. Briefly put, the referee noticed that if E0 and E1 are candidate-anonymous election systems such that E0 is resistant to control type Φ and E1 is not, then hybrid(E0, E1) will be routed to E1 unless all candidate names are even, and then said that since it will not always be the case that all candidate names are even, this showed that the hybrid was not resistant. The error in this reasoning is the incorrect implicit claim that NP-hard problems cannot have subcases-sometimes even quite broad ones-in P. They in fact can, e.g., 2CNF-SAT is in P. reduction that replaces each candidate name c with the name kc + i. So the control problem for hybrid(E 0 , E 1 , . . . , E k−1 ) with respect to Φ is itself NP-hard. u We note in passing that there is nothing particularly limiting the above theorem to the standard twenty types of control. The proof's many-one reduction would work equally well on almost any natural control type one might imagine. Theorem 3.3 immediately yields the following corollary.

Corollary 3.4 hybrid strongly inherits resistance to each of the standard twenty types of control.
Before we turn to applying this corollary, let us note that Theorem 3.3 and Corollary 3.4 are both, as is this entire paper, within the most natural, most typical model: Votes are input as a list ("nonsuccinct" input) and each vote counts equally ("unweighted" votes). We mention that for each of the other three cases-"succinct, weighted," "succinct, unweighted," and "nonsuccinct, weighted"-Theorem 3.3 and Corollary 3.4 both still hold (by the same proofs as above).
Let us apply Corollary 3.4 to obtain election systems that are broadly resistant to control. (We mention that since this paper first appeared, [27] (see also [32]) has created a very attractive alternate way of seeing that systems exist that resist the ten standard types of constructive control, namely, by proving that Copeland's election system resists the ten standard constructive control types. Unfortunately, the just-cited papers also show that Copeland elections do not resist some of the ten standard destructive control types.) Corollary 3.5 There exist election systems-for example, hybrid(plurality, Condorcet)that are resistant to all the standard ten types of constructive control.
Proof. By the work of Bartholdi, Tovey, and Trick ( [2], see also [21] regarding the tiehandling rules), for each of the standard ten types of constructive control, at least one of plurality and Condorcet is resistant. So by Corollary 3.4 and the candidate-anonymity of plurality and Condorcet, we are done. u To make the same claim for destructive control, we first construct an (artificial) system, E not-all-one (we define this system shortly), having the missing three resistance properties. (As mentioned earlier, an alternate approach would be to rely on work done after this paper, stating that the system "Copeland 0.5 " has these three resistances [27], and then to use that system as a component and hybridize using it.) Lemma 3.6 There exists a candidate-anonymous election system, E not-all-one , that is resistant to 1. destructive control by deleting voters,

destructive control by adding voters, and 3. destructive control by partition of voters in the TE model.
Proof. Our proof constructs reductions from Exact Cover by Three-Sets (X3C, for short), which is one of the standard NP-complete problems (see Garey and Johnson [56]) and is defined as follows: Exact Cover by Three-Sets (X3C) Given: A set B, and a family S = {S 1 , S 2 , . . . , S n } of subsets S i of B with S i = 3 for each i.
Question: Does S have an exact cover for B? That is, is there a subfamily S ′ ⊆ S such that every element of B occurs in exactly one set in S ′ ?
The system E not-all-one works as follows: The first four candidates in each vote get one point each. A candidate c is a winner if and only if c is the most preferred candidate of a strict majority of the voters and it is not the case that all candidates other than c have one point. Note that if c is a winner, then c is the unique winner. It is immediate that E not-all-one is candidate-anonymous and it is easy to see that E not-all-one is susceptible to destructive control by deleting voters, adding voters, and partition of voters in the TE model. NP-hardness of the destructive control problem follows in all three cases from a reduction from the problem X3C. Let (B, S) be an instance of X3C with B = m, S = {S 1 , S 2 , . . . , S n }, S i ⊆ B, and S i = 3 for each i. Without loss of generality, we assume that m is divisible by 3 and m/3 ≥ 1. Construct an instance of Destructive Control by Deleting Voters as follows. The candidate set is defined as C = B ∪ {d}, where d is the distinguished candidate. The set V of voters consists of n preference orders corresponding to the sets in S: For each i, V contains voter d > S i > · · · , where "S i " denotes the elements of S i in some arbitrary order, and "· · · " means that the remaining candidates follow in some arbitrary order.
For the converse, let V ′ ⊆ V be such that V ′ ≤ n−m/3 and d is not the unique winner of (C, V − V ′ ). Since d is the most preferred candidate for every voter in V and V − V ′ is not empty (since m/3 ≥ 1), it follows that all other candidates score one point in V − V ′ . This implies that the voters in V − V ′ correspond to an exact cover of S. u Claim 3.7 Claim 3.7 establishes Case 1 of Lemma 3.6.
We will use a similar construction to reduce X3C to Destructive Control by Adding Voters. The candidate set is now defined as C = B ∪ {d, c 1 , c 2 , c 3 }. The set V of registered voters consists of one voter d > c 1 > c 2 > c 3 > · · · and the set W of unregistered voters consists of n preference orders corresponding to the sets in S: For each i, W contains voter d > S i > · · · , where "S i " denotes the elements of S i in some arbitrary order, and "· · · " means that the remaining candidates follow in some arbitrary order. Proof of Claim 3.8. Suppose that (B, S) is in X3C. Let W ′ consist of m/3 voters from W that correspond to an exact cover. Then each candidate c ∈ C, c = d, scores one point in V ∪ W ′ . So, d is not the unique winner of (C, V ∪ W ′ ).
For the converse, let W ′ ⊆ W be such that W ′ ≤ m/3 and d is not the unique winner of (C, V ∪ W ′ ). Since d is the most preferred candidate for every voter in V ∪W ′ and V ∪W ′ is not empty, it follows that all other candidates score one point in V ∪ W ′ . This implies that the voters in W ′ correspond to an exact cover of S.
u Claim 3.8 Claim 3.8 establishes Case 2 of Lemma 3.6. We will use a similar construction to reduce X3C to Destructive Control by Partition of Voters in the TE model. As in the previous case, the candidate set is defined as C = B ∪ {d, c 1 , c 2 , c 3 }. The set V of voters consists of one voter of the form d > c 1 > c 2 > c 3 > · · · , n voters of the form c 1 > · · · , and n preference orders corresponding to the sets in S: For each i, V contains voter d > S i > · · · , where "S i " denotes the elements of S i in some arbitrary order, and "· · · " means that the remaining candidates follow in some arbitrary order.

Claim 3.9 (B, S) is in X3C if and only if d can be made to be not the unique winner of this election by partition of voters in the TE model. 16
Proof of Claim 3.9. Suppose that (B, S) is in X3C. Let the first subelection consist of voter d > c 1 > c 2 > c 3 > · · · and m/3 voters of the form d > S i > · · · that correspond to an exact cover. Then d does not win the first subelection. d also does not win the second subelection, since most voters in the second subelection prefer c 1 . Since d wins neither subelection, d is not an overall winner of the election.
For the converse, suppose that d is not the unique winner of the election. Since d is the unique winner of every subelection that involves d and at most one other candidate, it follows that d is the unique winner of the final run-off if d participates in the final runoff. Since d is not the unique winner of the election, d cannot participate in the final run-off, and should thus lose both subelections. In at least one of the subelections, d is the most preferred candidate for a strict majority of the voters. Since d does not win this subelection, the voters in this subelection of the form d > S i > · · · correspond to an exact cover.
u Claim 3.9 Claim 3.9 establishes Case 3 of Lemma 3.6. u Lemma 3.6 Corollary 3.10 There exist election systems that are resistant to all ten standard types of destructive control.
Proof. By Lemma 3.6 and the work of Hemaspaandra, Hemaspaandra, and Rothe [21], for each of the standard ten types of destructive control, at least one of plurality and E not-all-one is resistant. So by Corollary 3.4 and the candidate-anonymity of plurality and E not-all-one , we are done. u We cannot apply Theorem 3.3 directly to rehybridize the systems of Corollaries 3.5 and 3.10, because hybrid itself is not in general candidate-anonymous. However, we can get the same conclusion by directly hybridizing all the constituents underlying Corollaries 3.5 and 3.10.

Theorem 3.11 There exist election systems that are resistant to all twenty standard types of control.
The proof simply is to consider hybrid(plurality, Condorcet, E not-all-one ).

Immunity
We now turn to inheritance of immunity. Here, for each of constructive and destructive control, five cases inherit and five cases provably fail to inherit.
However, let is first pause a moment to define the artificial, candidate-anonymous election system E null , in which all candidates always lose. Note that E null is immune to all twenty standard types of control-trivially, since no one ever wins. This type of result shows why it is natural to focus, as this paper does, on achieving broad resistance rather than on achieving broad immunity: Resistance is less trivializable than immunity. In fact, we will now turn to showing that immunity to constructive control by deleting candidates is inherited by hybrid (Theorem 3.14), and our proof of that will be based on a trivialization of immunity. In that proof, we will employ the following somewhat interesting triviality result. Theorem 3.12 Any candidate-anonymous election system that is immune to constructive control by deleting candidates can never have a unique winner.
Proof. Let E be any candidate-anonymous election system that is immune to constructive control by deleting candidates. Suppose there is an election (C, V ) in which some candidate, say c ∈ C, is the unique winner, and let V consist of the voters v 1 , v 2 , . . . , v k . By candidateanonymity of E, there is a candidate set D with D ∩ C = ∅ that simply renames all candidates in C, and a voter set W consisting of voters w 1 , w 2 , . . . , w k that simply renames all candidates occurring in V from their C names to their D names such that d ∈ D is the unique winner of (D, W ). Now, consider the election with candidate set C ∪ D and voter set X consisting of the k preference orders where 1 ≤ i ≤ k and the ith voter in, respectively, V and W has preference If c is not a unique winner of the election (C ∪ D, X), then E is not immune to constructive control by deleting candidates, as by deleting D, c becomes the unique winner. Similarly, if d is not a unique winner of the election (C ∪ D, X), then E is not immune to constructive control by deleting candidates, as by deleting C, d becomes the unique winner. However, since E is immune to constructive control by deleting candidates and since (C ∪ D, X) cannot have both c and d be unique winners, our supposition that E can have a unique winner is contradicted. u The following lemma follows immediately from the definition of hybrid.

Lemma 3.13 "Never having a unique winner" is inherited by hybrid.
We now can prove our claim.
Theorem 3.14 Immunity to constructive control by deleting candidates is inherited by hybrid.
Proof. If E 0 , E 1 , . . . , E k−1 are candidate-anonymous election systems that are immune to constructive control by deleting candidates, then by Theorem 3.12 each never has a unique winner. So by Lemma 3.13, hybrid(E 0 , E 1 , . . . , E k−1 ) never has a unique winner. This proves that hybrid(E 0 , E 1 , . . . , E k−1 ) is immune to every type of control. u By applying a duality result of Hemaspaandra, Hemaspaandra, and Rothe k times, we can retarget this to a type of destructive control.

A voting system is susceptible to constructive control by adding candidates if and only
if it is susceptible to destructive control by deleting candidates.

A voting system is susceptible to constructive control by deleting candidates if and only if it is susceptible to destructive control by adding candidates.
Corollary 3.16 Immunity to destructive control by adding candidates is inherited by hybrid.
Proof. The proof follows immediately from Theorem 3.14 plus 1 + (k − 1) applications of Proposition 3.15.2. u hybrid's immunity to all voter-related types of control is immediate. Proof. Since none of this theorem's four operations changes the candidate set, hybrid routes all election evaluations related to a given input to the same election system E i , and so by that system's immunity the theorem holds. u For the ten remaining cases, inheritance does not hold.

constructive control by partition and run-off partition of candidates (both in model TE and TP), and 4. destructive control by partition and run-off partition of candidates (both in model TE and TP).
Proof. For each of these ten control problems, we provide a counterexample showing that immunity is not inherited by hybrid. We will use the artificial, candidate-anonymous election systems E first and E last , which are defined as follows. A candidate c wins an E first election if and only if there is one voter and this voter ranks c first. A candidate c wins an E last election if and only if there is one voter and this voter ranks c last. It is immediate that E first and E last are candidate-anonymous.
1. It is immediate that E first and E last are both immune to constructive control by adding candidates. However, hybrid(E first , E last ) is susceptible to constructive control by adding candidates. To see that, consider the election with set C = {0, 2} of qualified candidates, set D = {1} of possible spoiler candidates, and voter set V consisting of one voter with preference order 2 > 1 > 0. Candidate 0 loses in hybrid(E first , E last ) in election (C, V ): All candidate names in C are congruent to 0 mod 2, so hybrid routes its input to E first . However, if the spoiler candidate 1 is added to C and so the election (C ∪ D, V ) is input to hybrid(E first , E last ), this switches hybrid to now implement E last , and so candidate 0 now is the unique winner of this election. Thus, hybrid(E first , E last ) is not immune to constructive control by adding candidates.
2. This claim follows immediately from Part 1 and Proposition 3.15.1.
3. It is easy to see that E first and E last are immune to constructive control by partition and run-off partition of candidates in models TE and TP: No matter how we partition the candidates, there can only be winners if there is exactly one voter. And in an election with one voter, the first-ranked (respectively, last-ranked) candidate is the unique winner of the election for all partitions of candidates in all partitioning models.
However, hybrid(E first , E last ) is susceptible to constructive control by partition and runoff partition of candidates in models TE and TP. To see that, consider the election with candidate set C = {0, 1, 2}, distinguished candidate 2, and voter set V consisting of one voter with preference order 2 > 1 > 0. On input (C, V ), hybrid(E first , E last ) routes the election to E last , so 0 is the unique winner of the election. Now consider the candidate partition C 1 = {0, 1} and C 2 = {2}. Then 0 is the unique winner of (C 1 , V ) and 2 is the unique winner of (C 2 , V ). So, in both partition and run-off partition of candidates in models TE and TP, the final round of the election is ({0, 2}, V ). Since all candidate names are congruent to 0 mod 2, hybrid routes its input to E first , so 2 is the unique winner. Since 2 has been turned from a nonwinner into a unique winner, it follows that hybrid(E first , E last ) is susceptible to constructive control by partition and run-off partition of candidates in models TE and TP.
4. The argument given at the start of Part 3 of this proof also shows that E first and E last are immune to destructive control by partition and run-off partition of candidates in models TE and TP. To show that hybrid(E first , E last ) is susceptible to destructive control by partition and run-off partition of candidates in models TE and TP, it suffices to note that the candidate partition of Part 3 of this proof turns candidate 0 from a unique winner into a nonwinner.

Vulnerability
hybrid strongly inherited resistance, which is precisely what one wants, since that is both the aesthetically pleasing case and broadens resistance to control. However, for vulnerability it is less clear what outcome to root for. Inheritance would be the mathematically more beautiful outcome. But on the other hand, what inheritance would inherit is vulnerability, and vulnerability to control is in general a bad thing-so maybe one should hope for "Not I(nherits)" entries for our tables in this column. In fact, our results here are mixed. In particular, we for ten cases prove that inheritance holds unconditionally and for ten cases prove that inheritance holds (though in some cases we have to limit ourselves to election systems with winner/unique winner problems that fall into the polynomial hierarchy) if and only if P = NP. Since any practically useful election system should have winner/unique winner problems in P, this is not an onerous limitation. Indeed, even such "difficult" election systems as those of Dodgson, Kemeny, and Young have winner/unique winner problems in the polynomial hierarchy. We start with two vulnerability results that can be established by direct algorithmic attacks.

Theorem 3.19 hybrid inherits vulnerability to both constructive and destructive control by adding candidates.
Proof. We start with the constructive case. Let k ∈ N + and let E 0 , E 1 , . . . , E k−1 be candidate-anonymous election systems each vulnerable to constructive control by adding candidates. Let A i , 0 ≤ i ≤ k − 1, be the polynomial-time algorithms showing that E i is vulnerable to constructive control by adding candidates.
Since E 0 is vulnerable to constructive control by adding candidates, E 0 is susceptible to constructive control by adding candidates, and it follows from Theorem 3.1 that hybrid(E 0 , E 1 , . . . , E k−1 ) is susceptible to constructive control by adding candidates.
To complete our proof of vulnerability, we turn to seeking a polynomial-time algorithm for this control problem. Given an instance of Constructive Control by Adding Candidates, let Q be the set of qualified candidates with c ∈ Q being the distinguished candidate, let S be the set of spoiler candidates, and let V be the voter set with preferences over Q ∪ S. We distinguish the following three cases.
Case 1: Not all candidates in Q have the same value modulo k. Then, regardless of whether none, some, or all candidates from S are added, the initial and final election will be routed by hybrid(E 0 , E 1 , . . . , E k−1 ) to E default = E k−1 . Thus, we can simply invoke algorithm A k−1 .
Case 2: All candidates in Q have the same value modulo k, call it q, and all candidates in S also have values congruent to q mod k. Then we simply invoke algorithm A q .
Case 3: All candidates in Q have the same value modulo k, call it q, and at least one candidate in S has a value not congruent to q mod k. Then we do the following: Step 1: Invoke A q to see if victory (i.e., being the unique winner) for c is possible in E q with Q as the set of qualified candidates, S q as the set of spoiler candidates, where S q contains all members of S whose values are congruent to q mod k, and with voter set V (restricted to the participating candidates). If algorithm A q says YES, then output YES and halt; otherwise go to Step 2.
Step 2: For each d ∈ S ∩ {i | i ≡ q mod k}, invoke A k−1 to see if victory for c is possible in E default = E k−1 with Q ∪ {d} as the set of qualified candidates, S ′ = S −{d} as the set of of spoiler candidates, and with voter set V . If algorithm A k−1 says YES, then output YES and halt; otherwise go to the next iteration of this for-each loop.
Step 3: If we reach this step (i.e., the for-each loop in Step 2 was not successful in any of its iterations), then output "victory for c is impossible" and halt.
Note that the reason we in Case 3 had to include the "try each non-mod-q as being forced in" flourish is that only when at least one non-mod-q candidate is in the candidate set will we switch from E q to E default , so we must be very careful to only use E default regarding cases that will be routed to it. We cannot in any obvious way replace the loop with a single test, as a single vulnerability test does not let us address "Is there some subset of the spoiler set that includes at least one marked spoiler and that makes c win?" as that is a different problem, though the algorithm in effect does that via a polynomial number of ordinary vulnerability tests.
As to the destructive case, it follows from Theorem 3.1 that hybrid(E 0 , E 1 , . . . , E k−1 ) is susceptible to destructive control by adding candidates. To show that vulnerability inherits, exactly the same algorithm as above works, except with each time "victory" occurs replaced with "not being a unique winner," and of course when we now call the underlying polynomial-time algorithms for E i , they will be for the case of destructive control by adding candidates. u We now state eight trivial inheritance cases. Proof. None of these operations changes the candidate set, so whatever system hybrid routes the input to (E 0 or E 1 or . . . or E k−1 or E default = E k−1 ) will handle all the election evaluations related to the given input, and so we can directly use its polynomial-time algorithm showing vulnerability to the given type of control. Susceptibility follows from Theorem 3.1. u We are down to ten cases-deleting candidates and the four candidate-based partition cases, with each of those five cases appearing in constructive control and destructive control versions. For these ten cases, we will prove that inheritance holds (though in some cases we have to limit ourselves to election systems whose winner/unique winner problems are in the polynomial hierarchy) if and only if P = NP.
Theorem 3.21 Let Φ be one of the following two control types: 1. constructive control by deleting candidates, 2. destructive control by deleting candidates, let k ∈ N + , and let E 0 , E 1 , . . . , E k−1 be election systems whose Φ-control problems are in the polynomial hierarchy and such that for at least one i, 0 ≤ i ≤ k − 1, E i is candidateanonymous and susceptible to Φ. If P = NP then hybrid Proof. It follows immediately from Theorem 3.1 that hybrid(E 0 , E 1 , . . . , E k−1 ) is susceptible to Φ. To show vulnerability, note that for constructive control by deleting candidates the unique winner problem ≤ p m -reduces (via the trick mentioned in Section 2.4: asking about deleting zero candidates) to the control problem. And for destructive control by deleting candidates, by the same trick, we have that the unique winner problem ≤ p m -reduces to the complement of the control problem. So in both cases, since P = NP is assumed and the control problems are assumed to be in the polynomial hierarchy, we do have a polynomial-time algorithm for hybrid(E 0 , E 1 , . . . , E k−1 )'s unique winner problem by Proposition 2.6. Now, guess every possible way of legally deleting candidates and using the polynomial-time algorithm for hybrid(E 0 , E 1 , . . . , E k−1 ) see if under some such way our goal (making a specified candidate the unique winner or precluding a specified candidate from being a unique winner) can be achieved. This is an NP algorithm but since P = NP it proves vulnerability to Φ. u

Corollary 3.22 If P = NP then hybrid inherits vulnerability to constructive and destructive control by deleting candidates.
On the other hand, we have the following result. Since the reader has earlier in this paper seen many examples of our resistance proofs and has just seen some vulnerabilityrelated constructions, for the rest of this section we defer the proofs to Appendix A.
Theorem 3.23 There exist candidate-anonymous election systems E 0 and E 1 that are vulnerable to constructive control by deleting candidates but such that hybrid(E 0 , E 1 ) is resistant to constructive control by deleting candidates.
From Corollary 3.22, Theorem 3.23, and the fact that if P = NP then resistance implies nonvulnerability, we have our characterization.

Corollary 3.24 P = NP if and only if hybrid inherits vulnerability to constructive control by deleting candidates.
The corresponding characterization for the case of destructive control by deleting candidates will be established later as Corollary 3.37. We note that the proof of Theorem 3.23 also immediately establishes the following, by taking E 0 = E null , the election system in which all candidates always lose.
Corollary 3.25 There exist candidate-anonymous election systems E 0 and E 1 such that E 0 is immune to constructive control by deleting candidates and E 1 is vulnerable to constructive control by deleting candidates but such that hybrid(E 0 , E 1 ) is resistant to constructive control by deleting candidates.
Unfortunately, the analogs of Theorem 3.21 for candidate-related partitions are less clean. Regarding the strengths in the hypotheses in the following theorem, we mention that when a winner problem is in the polynomial hierarchy, that clearly implies that the corresponding unique winner problem is in the polynomial hierarchy. (c) P = NP.
We note that the proof (in Appendix A) of Theorem 3.28 also immediately establishes the following, by taking E 0 = E null , the election system in which all candidates always lose.
Corollary 3.31 There exist candidate-anonymous election systems E 0 and E 1 such that E 0 is immune to constructive control by run-off partition of candidates (in models TE and TP) and E 1 is vulnerable to constructive control by run-off partition of candidates (in models TE and TP) but such that hybrid(E 0 , E 1 ) is resistant to constructive control by run-off partition of candidates (in models TE and TP).
We now turn to the analogs of Theorem 3.28 and Corollaries 3.29, 3.30, and 3.31 for constructive control by partition of candidates. (c) P = NP.
We note that the proof (in Appendix A) of Theorem 3.32 also immediately establishes the following, by taking E 0 = E null , the election system in which all candidates always lose. Corollary 3.35 There exist candidate-anonymous election systems E 0 and E 1 such that E 0 is immune to constructive control by partition of candidates (in models TE and TP) and E 1 is vulnerable to constructive control by partition of candidates (in models TE and TP) but such that hybrid(E 0 , E 1 ) is resistant to constructive control by partition of candidates (in models TE and TP).
We now turn to the destructive control cases. (c) P = NP.
We note that the proof (in Appendix A) of Theorem 3.36 also immediately establishes the following, by taking E 0 to be the election system where c wins if and only if c is first in the first voter.
Corollary 3.40 There exist candidate-anonymous election systems E 0 and E 1 such that E 0 is immune to destructive control by deleting candidates, partition of candidates (in models TE and TP), and run-off partition of candidates (in models TE and TP), (in models TE and TP) and E 1 is vulnerable to to destructive control by deleting candidates, partition of candidates (in models TE and TP), and run-off partition of candidates (in models TE and TP), but such that hybrid(E 0 , E 1 ) is resistant to destructive control by deleting candidates, partition of candidates (in models TE and TP), and run-off partition of candidates (in models TE and TP).

Conclusions
Tables 1 and 2 summarize our inheritance results. The main contribution of this paper is the hybrid system, the fact that hybrid strongly inherits resistance, and the consequence that there is an election system that resists all twenty standard types of electoral control. A very natural direction for future research is to broadly explore the control behavior of standard election systems, and in particular to see if any exhibit broad resistance to control. candidates, and it is a polynomial-time task to decide when control can be asserted, so E 0 is vulnerable to this type of control.
Election system E 1 is defined as follows. For each candidate c ∈ C, c wins election (C, V ) if and only if V ≥ 2, c is ranked first by the first voter in V (recall that V is input as a list, and so it is meaningful to speak of the first voter), and (c is ranked first by the second voter in V or c is ranked first or second by all voters). It is immediate that E 1 is candidate-anonymous and susceptible to constructive control by deleting candidates. The following polynomial-time algorithm shows that E 1 is vulnerable to constructive control by deleting candidates: Step 1: Given an instance (C, c, V, k) of Constructive Control by Deleting Candidates, if V < 2, then reject and halt. Otherwise, let C 1 be the set of all candidates preferred to c by the first voter of V and let C 2 be the set of all candidates preferred to c by the second voter of V .
Step 2: If C 1 ∪ C 2 ≤ k then accept and halt (c can be made the unique winner by deleting C 1 ∪ C 2 ).
Step 3: If C 1 ∪ C 2 > k + 1 then reject and halt (to ensure that c is the unique winner, it is necessary (but not sufficient) to delete all candidates in C 1 and all but one of the candidates in C 2 ).
Step 4: If C 1 ∪ C 2 = k + 1 then for each d ∈ C 2 , consider the election with candidates (C − (C 1 ∪ C 2 )) ∪ {d} and voters V . If c wins this election (i.e., is in first or second position for each voter), then accept and halt.
Step 5: If none of the iterations of the for-each loop in Step 4 was successful, then reject and halt.
It remains to prove that hybrid(E 0 , E 1 ) is resistant to constructive control by deleting candidates. Susceptibility follows from Theorem 3.1. To show NP-hardness, we provide a ≤ p m -reduction from the standard NP-complete problem Vertex Cover (see Garey and Johnson [56]), which is defined as follows:

Vertex Cover
Given: An undirected, simple graph G and a positive integer k.
Question: Does G have a vertex cover of size at most k, i.e., does there exist a subset V ′ of G's vertex set such that V ′ ≤ k and V ′ contains at least one vertex of each edge in G?
Given an instance (G, k) of Vertex Cover, create an instance (C, 0, V, k) of Constructive Control by Deleting Candidates for election system hybrid(E 0 , E 1 ) as follows. Let G have n vertices and m edges. Without loss of generality, let the vertices of G be 2, 4, . . . , 2n. The candidate set is defined by C = {0, 1, 2, 4, 6, . . . , 2n}, where 0 is the distinguished candidate, 1 is the candidate whose presence determines whether hybrid routes its input to E 0 or E 1 , and 2, 4, 6, . . . , 2n are candidates corresponding to the vertices of G. The voters in V are defined as follows: 1. The first voter has preference 0 > · · · , 2. the second voter has preference 1 > 0 > · · · , and 3. there are m additional voters, corresponding to the edges of G: For every edge {i, j} in G with i < j, we add a voter with preference i > j > 0 > · · · .
In all the above preferences, the remaining candidates follow in some arbitrary order. Clearly, this transformation is polynomial-time computable. To show that Vertex Cover ≤ p m -reduces to Constructive Control by Deleting Candidates for hybrid(E 0 , E 1 ), we prove the following claim.
Claim A.1 G has a vertex cover of size ≤ k (k ≤ n) if and only if candidate 0 can be made the unique winner of election (C, V ) with respect to system hybrid(E 0 , E 1 ) by deleting at most k candidates.
Proof of Claim A.1. From left to right: Delete the candidates corresponding to a vertex cover of G. Since candidate 1 has not been deleted, hybrid(E 0 , E 1 ) routes its input to the system E default = E 1 . Thus, candidate 0 is the unique winner.
From right to left: If candidate 0 is the unique winner after at most k candidates have been deleted, candidate 1 cannot be among the deleted candidates. (Note that otherwise hybrid(E 0 , E 1 ) would have routed its input to the system E 0 , and since after deleting at most k ≤ n candidates at least two candidates remain, no one would have won in E 0 .) Since candidate 1 is ranked first by the second voter, it follows that candidate 0 must be ranked first or second by all voters. This means that the set of deleted candidates corresponds to a vertex cover of G having size at most k.
u Claim A.1 This completes the proof. u Theorem 3.23 Proof of Theorem 3.26. The proof is similar to the proof of Theorem 3.21. In all eight cases, it follows immediately from Theorem 3.1 that hybrid(E 0 , E 1 , . . . , E k−1 ) is susceptible to Φ. Since P = NP and the winner problem in each of Case 1a through 1d and the unique winner problem in each of Case 2a through 2d for hybrid(E 0 , E 1 , . . . , E k−1 ) is in the polynomial hierarchy, we have a polynomial-time algorithm for hybrid(E 0 , E 1 , . . . , E k−1 )'s winner problem in each of Case 1a through 1d and a polynomial-time algorithm for hybrid(E 0 , E 1 , . . . , E k−1 )'s unique winner problem in each of Case 2a through 2d.
To prove vulnerability to the given control type Φ, nondeterministically guess every possible way of partitioning the candidate set and use the polynomial-time algorithm for hybrid(E 0 , E 1 , . . . , E k−1 )'s winner problem if ties in subelections are handled by TP and use the polynomial-time algorithm for hybrid(E 0 , E 1 , . . . , E k−1 )'s unique winner problem if ties in subelections are handled by TE to determine which candidates participate in the final round of the election. Then use a polynomial-time algorithm for the unique winner problem (note that when a winner problem is in P, that clearly implies that the corresponding unique winner problem is in P) to determine if the distinguished candidate is the unique winner of the (final round of the) election for constructive control cases, and if the distinguished candidate is not a unique winner of the (final round of the) election for destructive control cases.
u Theorem 3.26 Proof of Theorem 3.28. Let E 0 be the election system in which each candidate c is a winner if and only if c is the only candidate and there is only one voter. This artificial election system is clearly vulnerable to constructive control by run-off partition of candidates.
To define E 1 , we modify election system E 1 from the proof of Theorem 3.23. Here, we define E 1 to be the following artificial election system: For each candidate c ∈ C, c wins election (C, V ) if and only if in C 1 . Since both subelections have unique winners, it follows that C 1 = C 2 = (n+3)/2. Since 0 is the unique winner of (C 1 , V ), the vertex candidates that are not in C 1 (i.e., that are in C 2 ) form a vertex cover of G. C 2 contains exactly (n + 3)/2 − 1 = (n + 1)/2 vertex candidates. So, G has a vertex cover of size (n + 1)/2. u Claim A.2 This completes the proof. u Theorem 3.28 Proof of Theorem 3.32. As in the proof of Theorem 3.28, let E 0 be the election system in which each candidate c is a winner if and only if c is the only candidate and there is only one voter. This artificial election system is clearly vulnerable to constructive control by partition of candidates. To define E 1 , we modify election system E 1 from the proof of Theorem 3.28. Here, we define E 1 to be the following artificial election system: For each candidate c ∈ C, c wins election (C, V ) if and only if Proof of Theorem 3. 36. In E 0 , each candidate c wins if and only if there is at least one voter and c is ranked first by the first voter and (there are at least two voters or there are at least two candidates). This artificial system is clearly candidate-anonymous and it is easy to see that E 0 is susceptible to destructive control by deleting candidates, partition of candidates (in models TE and TP), and run-off partition of candidates (in models TE and TP): Consider an election with two candidates, c and d, and one voter, c > d. Then c is the unique winner of the election, but deleting d or partitioning {c, d} into {c} and {d} will ensure that c does not win. To show vulnerability, note that distinguished candidate c can be made not a unique winner of (C, V ) if and only if V = 0 or c is not ranked first by the first voter or V = 1 (in the latter case by deleting all candidates other than c, or by partitioning the set of candidates C into C 1 = {c} and C 2 = C − {c}).
In E 1 , for each candidate c ∈ C, c wins election (C, V ) if and only if V > 0 and c is ranked second by the first voter and ( V = 4 C 2 or some voter ranks c worse than second).
It is immediate that E 1 is candidate-anonymous. Note that tie-handling issues do not apply, since E 0 and E 1 never have ties. It is easy to see that E 1 is susceptible to destructive control by deleting candidates, partition of candidates, and run-off partition of candidates. To show vulnerability, it suffices to show that we can decide in polynomial time whether these types of control can be asserted.
Given an instance (C, c, V, k) of Destructive Control by Deleting Candidates, control can be asserted if and only if winner of all subelections that don't involve 1: such elections are routed to E 0 , V ≥ 2, and the first voter ranks 0 first of the candidates in C − {1}.
So, 0 is not a winner of (C ′ , V ) for some C ′ such that {0, 1} ⊆ C ′ ⊆ C. Since (C ′ , V ) is routed to E 1 and 0 is ranked second by the first voter in (C ′ , V ), it follows that V = 4 C ′ 2 and that 0 is ranked first or second by all voters. The latter condition implies that the set of candidates not involved in the subelection, i.e., the candidates in C − C ′ , form a vertex cover of G. Since V = 4(n/2 + 2) 2 and V = 4 C ′ 2 , it follows that C ′ = n/2 + 2, and thus the vertex cover of G, C − C ′ , has size n/2. u Claim A.4 This completes the proof. u Theorem 3.36