C-Link: A Hierarchical Clustering Approach to Large-scale Near-optimal Coalition Formation

1 Introduction

Elections are an important tool in reaching decisions, in both human and online settings. With the increasing importance of the online world and multiagent systems, the use of elections in computer-based settings will but increase. Unfortunately, given the relentless growth in the power of computers, it is natural to worry that computers will also be increasingly brought to bear in planning manipulative attacks on elections.

The two most computationally studied types of attacks on elections are known as "control" and "manipulation." Both were introduced by Bartholdi, Tovey, and Trick [1989; 1992]. In control, an agent, usually referred to as "the chair," tries to make a given candidate win by adding/deleting/partitioning voters or candidates. In manipulation, some nonmanipulative voters and a coalition of manipulative voters vote under some election system, and the manipulative voters seek to make a given candidate win. There is a broad literature on the com-

Lane A. Hemaspaandra

Dept. of Computer Science University of Rochester Rochester, NY 14627 USA

putational complexity of control, and on the computational complexity of manipulation.

This paper considers control attacks against elections that contain manipulators. We consider both the cooperative and the competitive cases.

In the cooperative case, the chair is allied with the manipulative coalition. For example, perhaps during a CS department's hiring, the department chair, who happens to also be the senior member of the systems group, is mounting a control by partition of voters attack (in which he or she is dividing the faculty into two subcommittees, one to decide which candidates are strong enough teachers to merit further consideration, and one to decide which candidates are strong enough researchers to merit further consideration), and also is able to directly control the votes of every one of his or her fellowmembers of the department's systems faculty. The chair's goal is to make some particular candidate, perhaps Dr. I. M. Systems, be the one chosen for hiring.

In the competitive case, which can be thought of in a certain sense as control versus manipulation, we'll assume that the manipulative coalition's goal is to keep the chair from achieving the chair's goal. For the competitive case, we'll look at the case where the chair acts before the manipulators, and at the case where the manipulators act before the chair. For control attacks by so-called partition, in which there is a two-round election, we'll consider the case where the manipulators can change their votes in the second round, and the case where the manipulators cannot change their votes in the second round.

Our main contributions are as follows.

Building on the existing notions of control and manipulation, we give natural definitions that capture our cooperative and competitive notions as problems whose computational complexity can be studied. We note how existing hardness results for control and manipulation are, or are not, inherited by our problems. We prove upper bounds on our problems. For the competitive case, some of these are as high as NPNP, coNPNP, and coNPNPNP .

Those are very high levels of complexity. Yet they are tight: We show that there are election systems (having ptime winner problems) for which most of those high bounds have matching lower bounds, yielding completeness for those classes.

The fact that the upper bounds are tight does not mean that those high complexity levels hold for every election system having a p-time winner problem. Indeed, we show that that is not the case. In particular, for the important election systems approval and plurality, we show that the complexity of control in the presence of manipulators, whether cooperative or competitive, falls far below those upper bounds, even falling as low as polynomial time.

We also obtain cases, for veto (Theorem 4.4) and Borda (Theorem 4.5) elections, where competitive control-plusmanipulation is variously easier or harder than one might expect from the separate control and manipulation cases.

2 RelatedWork

The idea of enhancing control with manipulative voters has been mentioned in the literature, namely, in a paragraph of [Faliszewski et al., 2011]. That paper cooperatively integrated with control, to a certain extent, a different attack type known as bribery [Faliszewski et al., 2009a]. In that paper's conclusions and open directions, there is a paragraph suggesting that manipulation could and should also be integrated into that paper's "multiprong setting," and commending such future study to interested readers. That paragraph was certainly influential in our choice of this direction. However, it is speaking just of the cooperative case, and provides no results on this since it is suggesting a direction for study.

The lovely line of work about "possible winners" [Konczak and Lang, 2005] in the context of adding candidates might at first seem to be merging manipulation and control. We refer to the line of work explored in [Chevaleyre et al., 2010; Baumeister et al., 2011; Xia et al., 2011; Chevaleyre et al., 2012]. That work considers an election with an initial set of candidates, over which all the voters have complete preferences, and a set of additional candidates over which the voters initially have no preferences, and asks whether, if the entire set of additional candidates is added, there is some way of extending the initial linear orders to now be over all the candidates, in such a way that a particular initial candidate becomes a winner of the election. Although on its surface this might feel like a cross between manipulation and control by adding candidates, in fact, in this interesting problem there is no actual choice regarding the addition of candidates; all are simply added. Thus this problem is a generalization of manipulation (as the papers note), that happens to be done in a setting that involves adding candidates. It is not a generalization of control by adding, or even so-called unlimited adding, of candidates, as in those the chair must choose what collection of candidates to add. In short, unlike control and unlike this paper, there is no existentially quantified action by a chair. (An interesting recent paper of Baumeister et al. [2012] uses the term possible winner in a new, different way, to speak of weights rather than preferences initially being partially unset. That particular paper's question, as that paper notes, can be seen as a generalization of control by adding and deleting voters. However, their notion is not a generalization of manipulation.)

The present paper does combine control and manipulation, with both those playing active-and sometimes opposingroles. Manipulation alone has been extensively studied in a huge number of papers, starting with the seminal paper of [Bartholdi et al., 1989] (see also [Bartholdi and Orlin, 1991]), which covered the constructive case. The destructive cases (i.e., those where the goal is to keep a particular candidate from winning) are due to [Conitzer et al., 2007]. Control alone has been extensively studied in many papers, with the seminal paper being [Bartholdi et al., 1992], which covered the constructive case. The destructive cases were first studied in [Hemaspaandra et al., 2007]. There has been quite a bit of work on finding systems for which conducting various types of manipulation is hard, or for which conducting most types of control attacks is hard, see, e.g., [Erd´elyi and Rothe, 2010; Erd´elyi et al., 2011; Erd´elyi et al., 2009; Faliszewski et al., 2009b; Hemaspaandra et al., 2009; Menton, to appear; Menton and Singh, 2013; Parkes and Xia, 2012] or the surveys [Faliszewski et al., 2009c; 2010].

In the present paper, we'll see that who goes first, the chair or the manipulators, is important in determining what complexity upper bounds apply. Order has also been seen to be important in the study of so-called online control attacks [Hemaspaandra et al., 2012b; 2012a], and of online manipulation attacks [Hemaspaandra et al., 2013]. However, the papers just mentioned are separately about control, and about manipulation. In contrast we are mostly interested in when both are occurring, and especially when the two attacks are in conflict with each other.

The present paper also looks at how revoting affects the complexity of elections that involve both control and manipulation. It is important to mention that, for the case of just manipulation, [Narodytska and Walsh, 2012] has recently discussed revoting, and gives an example that shows that revoting can sometimes be a valuable tool for the manipulator.

3 Preliminaries

An election (a.k.a. a social choice correspondence) maps from a finite candidate set C and a finite vote collection V to a set, W ⊆ C, called the winner(s) [Shoham and LeytonBrown, 2009]. Voters come without names, and the votes are input as a list, i.e., as ballots. For approval elections, each ballot is a length-‖C‖ 0-1 vector indicating whether each candidate is disapproved or approved. The candidate getting the most approvals is the winner (or winners if candidates tie for most). For all other systems we discuss, each ballot is a tiefree linear ordering of the candidates. For plurality elections, each voter gives one point to his or her top choice and zero to the rest. For veto elections, each voter gives zero points to his or her bottom choice and one to the rest. For Borda elections, each voter gives zero points to his or her bottom choice, one point to his or her next to bottom choice, and so on through giving ‖C‖ - 1 points to his or her top choice. In the three systems just mentioned, the winner is the candidate(s) who receives the most points. In a Condorcet election-[Bartholdi et al., 1992] recast the notion of a Condorcet winner [Condorcet, 1785] into an election system of sorts, in this way, and used it as one of their focus cases in their seminal control study-a candidate p is a winner exactly if for each other candidate b it holds that strictly more than half the votes cast prefer p to b. Unlike the systems from earlier in this paragraph, Condorcet elections on some inputs may have no winners.

An election system E is said to have a p-time winner problem if there is a polynomial-time algorithm that on input C, V , and p ∈ C, determines whether p is a winner under E of the election over C with the votes being V .

We assume the reader is aware of the NP, coNPNP, NPNP, and coNPNPNP levels of the polynomial hierarchy (the "exponentiation" notation denotes oracle class, informally put, having unit-cost access to a set of one's choice from the given class) [Meyer and Stockmeyer, 1972; Stockmeyer, 1976] and with many-one reductions (which here always means manyone polynomial-time reductions). As is standard, we use ≤pm to denote many-one reductions. There are far fewer completeness results for levels of the hierarchy beyond NP, such as the abovementioned ones, than there are for NP; a collection of and discussion of such results can be found in [Schaefer and Umans, 2002a; 2002b]. Completeness and hardness here are always with respect to many-one reductions.

Our hardness results are worst-case results. However, it is known that if there exists even one set that is hard for NP (and note that all sets hard for coNPNP, NPNP, or coNPNPNP are hard for NP) and has a (deterministic) heuristic algorithm whose asymptotic error rate is subexponential, then the polynomial hierarchy collapses. See [Hemaspaandra and Williams, 2012] for a discussion of that, and an attempt to reconcile that with the fact that in practice heuristics often do seem to do well, including for some cases related to elections, see, e.g., [Walsh, 2009].

For a complete description of all the many control types touched on in this paper, we refer the reader to the detailed definitions given in [Faliszewski et al., 2009b]. But we briefly define here the underlying control types we use in our sample proofs. Given as input an election, (C, V ), a distinguished candidate p ∈ C, and an integer k ≥ 0, the constructive (respectively, destructive) control by deleting voters-for short CCDV (respectively, DCDV)-problem for an election system E asks whether there is some choice of at most k votes such that if they are removed, p is a winner (respectively, is not a winner) of the given election under E. We are in the so-called nonunique-winner model, and so we ask about making p "a winner" rather than "the one and only winner," which is the so-called unique-winner model. 1 Each of those problems has an adding voters (AV) analogue, in which one has a collection of registered votes that definitely are cast, and has a collection of "unregistered" votes, and the question is whether there is some choice of at most k unregistered votes such that if they are added, the goal is met. These types of control are motivated by issues ranging from voter suppression to targeted phone calls to get-out-the-vote drives. There are the natural analogous types for adding and deleting candidates, AC and DC (note: in the destructive control by deleting candidates case-DCDC-deleting p is not allowed [Bartholdi et al., 1992]). The partition types are called runoff partition of candidates (RPC), partition of candidates (PC), and partition of voters (PV). In PV, the input is just C, V , and p, and the constructive (destructive) question is whether there exists a partition of the voters into V1 and V2 such that if the candidates who survive at least one of the elections (C, V1) and (C, V2) move on to a final election among just them with the vote set V , p is (is not) a winner. Here, there are two models for what "survive" means. In the ties eliminate (TE) model, to move forward one must uniquely win a first-round election; in the ties promote (TP) model, it suffices to be a winner of a first-round election. One of our sample proofs will be about CCPV-TE.

1 Many of our results also hold in the other model, but the nonunique-winner model is probably the better, more natural model on which to focus in general.

As to manipulation, the constructive (destructive) unweighted coalitional manipulation CUCM (DUCM) problem under election system E has as input C, p ∈ C, a collection of nonmanipulative voters each specified by his or her vote (linear order or approval vector, as appropriate), and a collection of manipulator voters (coming in as blank slates, e.g., input as a string 1j to indicate there are j of them), and the question is whether there is some way of setting the votes of the manipulative coalition so that p is (is not) a winner of the resulting election under system E with those votes and the nonmanipulative votes both being cast.

Our model of allowing control in the presence of manipulators varies the standard control definitions to allow some of the voters to be manipulators, and thus to come in as blank slates. We mention that for AV, it is legal to have manipulators among the registered and/or the unregistered votes. For the cooperative cases, the question is whether the chair can choose preferences for the manipulators such that, along with using his or her legal control-decision ability for that control type, p can be made (precluded from being) a winner. We denote these types by adding in an "M+," e.g., pluralityM+CCAV. For the competitive cases, we can look at the case where the manipulative coalition sets its votes and then the chair chooses a control action, and we call that MF for "manipulators first." Or we can have the chair control first and then the manipulators set their votes, which we call CF for "chair first." Since the manipulators seek to thwart the chair, the case Borda-CCAV-MF, for example, asks whether under Borda, no matter how the manipulative voters, moving first, set their votes, there will exist some choice of at most k unregistered voters that the chair can add so that p is a winner. For partition cases, we add the string "-revoting" to indicate that after the first-round elections occur, the manipulators can change their votes in the final election.

Finally, to allow many things to be spoken of compactly, we use "stacked" notation to indicate every possible string one gets by reading across and taking one choice from each bracket one encounters on one's path across the expression.

3 × 2) = 20 control types.

4 Results

4.1 Inheritance

Each control type many-one reduces to each of its cooperative and to each of its competitive control-plus-manipulation variants, because for those variants the zero-manipulator cases degenerate to the pure control case. For example, E-CCDV ≤pm E-M+CCDV and E-CCDV ≤pm E-CCDV-MF. In particular, NP-hardness results for control inherit upward to each related cooperative and competitive case.

For manipulation, the inheritance behavior is not as broad, since partition control cannot necessarily be "canceled out" by setting a parameter to zero, as partition doesn't even have a numerical parameter. Nonpartition control types do display inheritance, but for the competitive cases there is some "flipping" of the type of control and the set involved. For each constructive (respectively, destructive) control type regarding adding or deleting candidates or voters, destructive (respectively, constructive) manipulation many-one reduces to the complement of the set capturing the competitive case of the constructive (respectively, destructive) control type combined with manipulation. For example, E-CUCM ≤pm E-DCAC-CF and E-DUCM ≤pm E-CCDV-MF. For the cooperative cases there is no "flipping." For each constructive or destructive control type regarding adding or deleting candidates or voters, manipulation many-one reduces to the cooperative case of that control type combined with manipulation. For example, E-CUCM ≤pm E-M+CCAC and EDUCM ≤pm E-M+DCAC.

4.2 General Upper Bounds andMatching Lower Bounds

For elections systems with p-time winner problems, all the cooperative cases clearly have NP upper bounds. But the upper bounds for the competitive cases are far higher, falling in the second and third levels of the polynomial hierarchy, as described by the following theorem.

Theorem 4.1 For each election system E having a p-time winner problem, the bounds of Table 1 hold. 2

Although the table's upper bounds clearly follow from the structure of the problems, the bounds are very high. Can they be improved by some cleverer approach? Or are there systems with p-time winner problems that show the bounds to be tight? The following result establishes that the latter holds; each of the cells in the table is tight for at least some cases.

• Theorem 4.2 1. For each of the eight problems on the top line of Table 1, and each of the columns on that line, there exists an election system E, which has a p-time winner problem, for which the named problem is complete for the named complexity class.
• For each of CCPV-TP and CCPV-TE, and each of the CF, CF-revoting, and MF columns of Table 1, and each of the columns on that line, there exists an election system E, which has a p-time winner problem, for which the named problem is complete for the named complexity class.

2 Where the table says N/A-not applicable-the nonrevoting bounds just to the left of the box technically still hold; we say N/A simply to be clear that revoting cannot even take place in nonpartition cases, since there is no second round.

1. There exists an election system E, which has a p-time winner problem, for which CCPV-TP-MF-revoting is coNPNPNP -complete.

The above result says that the upper bounds are not needlessly high. They are truly needed, at least for some systems. However, the constructions proving the lower bounds are artificial and the construction involving the third level of the polynomial hierarchy is lengthy and difficult. 3 In particular, this leaves completely open the possibility that for particular, important real-world systems, even the competitive cases may be far simpler than those bounds suggest. In the coming section, we will see that indeed for some of most important real-world systems, even in the presence of manipulators, the control problem is just as computationally easy as when there are no manipulators.

4.3 Specific Systems

Plurality is certainly the most important of election systems, and approval is also an important system. For plurality, approval, and Condorcet elections, we note that all the "M+," "CF," and "MF" cases whose control type is classified as P (i.e., as a "V" or "I" in the notation of that the 2007 table we're about to mention) in the with-no-manipulators table of complexities for that election system in [Hemaspaandra et al., 2007] are in P for all our cooperative and competitive cases.

Theorem 4.3 Each problem contained in

whose corresponding control type is in P in Table 1 of page 258 of [Hemaspaandra et al., 2007], 4 is in P.

3 The third-level case has to overcome the specific, and as far as we know new, worry that in the second round, the first-round vote of the manipulators is not longer available. Yet in a "∀∃∀" context (which is the quantifier structure that models coNPNPNP ), a particular existential choice has to handle only a particular value of the first ∀. So to make the construction work, we need to in some sense have the first-round votes, which are no longer available, still cast a clear and usable shadow forward into the second round, at least in certain cases in the image of the reduction. We achieve this, in particular by shaping the election system itself carefully to help realize this unusual effect. Otherwise, we would not be capturing the right quantifier structure.

4 This claim holds despite the fact that that table is focused on the unique-winner case, and despite the fact that the "AC" line of that table refers to so-called unlimited adding and in this paper (as is now standard) we use "AC" to refer to (limited) adding. The reason we have looked at only the P cases of the 2007 table is that due to our inheritance results, for the NP cases getting a P result will be impossible, at least if the unique-winner results of the table carry over to our nonunique-winner setting-which typically is the case As an illustration, we include a proof of plurality-M+CCPV-TE ∈ P.

Proof. Note that it is not the case that the manipulators can always simply vote for p, no matter what the chair does. For example, if the chair partitions the voters such that one of the subelections contains a voter voting p > a > b, and the other subelection contains 100 voters voting a > b > p, 101 voters voting b > a > p, and one manipulator, the manipulator should vote for a, so that a and b are tied in the second subelection and neither goes through to the second round. Still, we will show that if there is a partition of the voters and a manipulation of the manipulators such that p wins the election, then there exists a way for p to win when all manipulators vote for p. It follows that we can check if p can be made a winner by first having all manipulators vote for p and then running the polynomial-time algorithm for plurality-CCPV-TE from [Hemaspaandra et al., 2007].

So, suppose that there exists a manipulation and a partition (V1, V2) such that p is a winner of the election. Without loss of generality, suppose p is the unique winner of (C, V1). Then p is also the unique winner of (C, V1) if all manipulators in V1 vote for p. If (C, V2) has a unique winner c that does not beat p in the run-off, then having all manipulators in V2 vote for p leads to one of the following three situations: c is still the unique winner, c is tied with p for first place (and so there is no unique winner), or p is the unique winner. In all three cases, p wins the runoff. The only interesting case is therefore the case where (C, V2) has no unique winner. As explained above, simply changing the manipulators' votes to p could have bad effects. Instead, we do the following. For each manipulator in V2, if the manipulator votes for a ̸= p, we change the manipulator's vote to p, move this manipulator to V1 and for each candidate b ̸= a, we move a voter who votes for b (if one exists) from V2 to V1. (If this voter is a manipulator, we also change its vote to p.) Since we added a vote for p to V1, p will still be the unique winner in (C, V1). Since we keep the relative scores of the candidates with positive scores constant, we keep the same set of winners in (C, V2) until V2 becomes empty, in which case all candidates are winners. In both cases, no candidate proceeds to the runoff from the second subelection. q

We now give results for veto and Borda, including, for the latter, an interesting increase in complexity.

CWCM and DWCM are the same as CUCM and DUCM, except in such weighted cases every voter has a positive integer weight, and a voter with weight w counts as w voters. Consider the case of 3-candidate weighted veto elections. The known results on this are that CWCM is NP-complete, DWCM is in P, and CCAV and CCDV are both in P. The following results, whose second part may be surprising, shows that for this system CC[ AD ]V-[ CF MF ] are all in P-not NPcomplete.

and has been checked for many, but not all, cases in the table. We will cover this issue in more detail in the full version of this paper.

Theorem 4.4 For 3-candidate weighted veto elections, the following hold.

Proof. The first case follows directly from the fact that constructive manipulation is NP-complete [Conitzer et al., 2007] and the inheritance observations from Section 4.1 (as the relevant result there holds even for the weighted case).

For the competitive cases, note that the only action that makes sense for the manipulators is to veto p. This holds regardless of whether the manipulators or the chair goes first. So, we let the manipulators veto p and then run the polynomial-time algorithm for CCAV and CCDV. q

3-candidate weighted Borda elections show a true increase in complexity. The underlying CWCM, DWCM, CCAV, and CCDV complexities are known to be respectively NPcomplete, P, NP-complete, and NP-complete, and thus all are in NP. Yet we show that CCAV-MF is coNP-hard, and so cannot be in NP unless the polynomial hierarchy collapses to NP ∩ coNP.

Theorem 4.5 For 3-candidate weighted Borda elections, the following hold.

1. CCAV-MF is NP-hard and coNP-hard.

Proof. The first case follows directly from the fact that manipulation is NP-complete [Conitzer et al., 2007] and the inheritance observations from Section 4.1.

The remaining NP-hardness results follow from the NPcompleteness of CCAV and CCDV and the inheritance observations from Section 4.1.

To show that CCAV-CF is in NP, guess a set of voters to add, and then check that the manipulators can't make p not win. We do this by setting all manipulators to a > b > p, checking that p is a winner, and then setting all manipulators to b > a > p, and checking that p is a winner. A similar argument shows that CCDV-CF is in NP.

It remains to show that CCAV-MF is coNP-hard, i.e., that the complement of CCAV-MF is NP-hard. We will reduce from Partition. Given a nonempty sequence of positive integers k1, . . . , kt that sums to 2K, we will construct an election such that there is a partition (i.e., a subsequence of k1, . . . , kt that sums to K) if and only if the manipulators can vote in such a way that the chair won't be able to make p a winner.

We construct the following election: We have manipulators with weights k1, . . . , kt. The manipulators are registered voters. We have two unregistered voters, both with weight 3K - 1. One of these voters votes p > a > b and one votes p > b > a. We have addition limit one, i.e., the chair can add at most one voter.

If there is a partition, then the manipulators vote so that a total of K vote weight casts the vote a > b > p and a total of K vote weight casts the vote b > a > p. So, the scores of p, a, and b are 0, 3K, and 3K. There is no way for the chair to make p a winner by adding at most one voter. If the chair adds the weight 3K - 1 voter voting p > a > b, the score of p is 6K - 2 and the score of a is 3K + (3K - 1) = 6K - 1 and so p is not a winner. Adding the other voter gives a score of 6K-2 for p and a score of 6K-1 for b and again p is not a winner.

Now consider the case that there is no partition. Look at the scores of the candidates after the manipulators have voted. Without loss of generality, assume that score(a) ≤ score(b). Then score(a) ≤ 3K - 1 (since there is no partition) and score(b) ≤ 4K. Now the chair adds the weight 3K - 1 voter voting p > a > b. After adding that voter, p's score is 6K-2, a's score is at most (3K - 1) + (3K - 2) and b's score is at most 4K. It follows that p is a winner. q

5 Conclusions and Open Directions

We have established general inheritance results and complexity upper bounds for control in the presence of manipulators, for both cooperative and competitive settings. We for the upper bounds provided matching lower bounds, but also showed that for many natural systems the complexity is far lower than the general upper bounds.

Many open directions remain. For example, regarding 3-candidate weighted Borda elections, we have shown that CCAV-MF is NP-hard and coNP-hard, and although our upper-bound theorem is not explicitly about weighted cases, clearly this problem, for exactly the same reason as in our upper-bound theorem, is in coNPNP. But precisely where within that range does it fall? Also, what happens for realworld election systems that themselves are complex to manipulate and/or control, such as Llull, Copeland, fallback, sincere-preference approval, and Schulze elections? Do some of these systems themselves provide natural systems that might for our competitive cases be complete for some of the high complexity classes given in Table 1?

Acknowledgments

Supported in part by NSF grants CCF-0915792, CCF1101452, and CCF-1101479. We thank the anonymous IJCAI referees for helpful comments.