Complexity of Manipulating Elections with Few CandidatesVincent Conitzer and Tuomas SandholmComputer Science DepartmentCarnegie Mellon University5000 Forbes AvenuePittsburgh, PA 15213{conitzer, sandholm}@cs.cmu.eduAbstractIn multiagent settings where the agents have different pref-erences, preference aggregation is a central issue. Voting isa general method for preference aggregation, but seminal re-sults have shown that all general voting protocols are manip-ulable. One could try to avoid manipulation by using pro-tocols where determining a beneficial manipulation is hard.Especially among computational agents, it is reasonable tomeasure this hardness by computational complexity. Someearlier work has been done in this area, but it was assumedthat the number of voters and candidates is unbounded. Wederive hardness results for the more common setting wherethe number of candidates is small but the number of voterscan be large. We show that with complete information aboutthe others’ votes, individual manipulation is easy, and coali-tional manipulation is easy with unweighted voters. However,constructive coalitional manipulation with weighted voters isintractable for all of the voting protocols under study, exceptin the Cup protocol. Destructive manipulation tends to be eas-ier, except in the Single Transferable Vote protocol. Random-izing over instantiations of the protocols (such as schedulesof a Cup) can be used to make manipulation hard. Finally,we show that under weak assumptions, if weighted coali-tional manipulation with complete information about the oth-ers’ votes is hard in some voting protocol, then individual andunweighted manipulation is hard when there is uncertaintyabout the others’ votes.1. IntroductionIn multiagent settings, agents generally have different pref-erences, and it is of central importance to be able to aggre-gate these, i.e. to pick a socially desirable candidate froma set of candidates. Candidates could be potential presi-dents, joint plans, allocations of goods or resources, etc.Voting is the most general preference aggregation scheme,and voting mechanisms have been applied to software agents(e.g. (Ephrati & Rosenschein 1991; 1993)).One key problem voting schemes are confronted with isthat of manipulation by the voters. An agent is said to votestrategically when it does not rank the alternatives accordingto its true preferences, but rather so as to make the eventualoutcome most favorable to itself. For example, if an agentprefers Nader to Gore to Bush, but knows that Nader hasCopyrightc 2002, American Association for Artificial Intelli-gence (www.aaai.org). All rights reserved.too few other supporters to win, while Gore and Bush areclose to each other, the agent would be better off by declar-ing Gore as its top candidate. Manipulation is an undesirablephenomenon because social choice schemes are tailored toaggregate preferences in a socially desirable way, and if theagents reveal their preferences insincerely, a socially unde-sirable candidate may be chosen.The issue of strategic voting has been studied extensively.A seminal negative result, the Gibbard-Satterthwaite theo-rem, shows that if there are three or more candidates, then inany nondictatorial voting scheme, there are preferences un-der which an agent is better off voting strategically (Gibbard1973; Satterthwaite 1975). (A voting scheme is called dicta-torial if one of the voters dictates the social choice no matterhow the others vote.)When the voters are software agents, the algorithms theyuse to decide how to vote must be coded explicitly. Giventhat the voting algorithm needs to be designed only once (byan expert), and can be copied to large numbers of agents(even ones representing unsophisticated human voters), it islikely that rational strategic voting will increasingly becomean issue, unmuddied by irrationality, emotions, etc.Especially in the context of software agents, it makessense to ask how complex it is to compute a beneficial ma-nipulation. Such complexity can be used as a desirable prop-erty because it can make manipulation infeasible to the vot-ers. Designing voting protocols where manipulation is com-plex promises to be an avenue for circumventing the funda-mental impossibility results regarding the existence of non-manipulable voting protocols.The computational complexity of manipulation has al-ready received some attention (Bartholdi, Tovey, & Trick1989a; Bartholdi & Orlin 1991). However, the results todate that do show high complexity rely on both the numberof candidates and the number of voters being unbounded.In sharp contrast to those results, in this paper we showhigh complexity results for the more common setting wherethe number of candidates is a small constant (the number ofvoters may be large). Furthermore, we show low complexityin certain settings where both the number of candidates andvoters are unbounded.Restricting the number of candidates to a constant reducesthe number of possible votes for a single voter to a constant.If the voters all have equal weight in the election, the numberof de facto possible combinations of votes that even a coali-tion can submit is polynomial in the number of voters in thecoalition (since the voters have equal weight, it does not mat-ter which agent in the coalition submitted which vote; onlythe multiplicities of the votes from the coalition matter). Weget the following straightforward result.Proposition 1 Let there be a constant number of candi-dates, and suppose that evaluating the result of a particularcombination of votes by a coalition is in P. If there is onlyone voter in the coalition, or if the voters are unweighted, themanipulation problem is in P. (This holds for all the differ-ent variants of the manipulation problem, discussed later.)Proof. The manipulators (an individual agent or a coalition)can simply enumerate and evaluate all possibilities (there isa polynomial number of them).In particular, in the complete-information manipulationproblem in which the votes of the non-colluders are known,evaluating the result of a (coalitional) vote is as easy as de-termining the winner of an election, which must be in Pfor practical voting mechanisms.1This leaves open two av-enues for deriving high complexity results with few candi-dates. First, we may investigate the complete-informationcoalitional manipulation problem when voters have differ-ent weights. While many human elections are unweighted,the introduction of weights