Universal Voting Protocol Tweaks to Make Manipulation Hard∗Vincent Conitzer and Tuomas SandholmCarnegie Mellon UniversityComputer Science Department5000 Forbes AvenuePittsburgh, PA 15213, USA{conitzer,sandholm}@cs.cmu.eduAbstractVoting is a general method for preference aggrega-tion in multiagent settings, but seminal results haveshown that all (nondictatorial) voting protocols aremanipulable. One could try to avoid manipula-tion by using voting protocols where determininga beneficial manipulation is hard computationally.A number of recent papers study the complexityof manipulating existing protocols. This paper isthe first work to take the next step of designingnew protocols that are especially hard to manip-ulate. Rather than designing these new protocolsfrom scratch, we instead show how to tweak ex-isting protocols to make manipulation hard, whileleaving much of the original nature of the protocolintact. The tweak studied consists of adding oneelimination preround to the election. Surprisingly,this extremely simple and universal tweak makestypical protocols hard to manipulate! The proto-cols become NP-hard, #P-hard, or PSPACE-hardto manipulate, depending on whether the sched-ule of the preround is determined before the votesare collected, after the votes are collected, or thescheduling and the vote collecting are interleaved,respectively. We prove general sufficient condi-tions on the protocols for this tweak to introducethe hardness, and show that the most common vot-ing protocols satisfy those conditions. These arethe first results in voting settings where manipula-tion is in a higher complexity class than NP (pre-suming PSPACE 6= NP).1 IntroductionOften, a group of agents has to make a common decision, yetthey have different preferences about which decision is made.Thus, it is of central importance to be able to aggregate thepreferences, that is, to make a socially desirable decision as towhich candidate is chosen from a set of candidates. Such can-didates could be potential presidents, joint plans, allocations∗The material in this paper is based upon work supported by theNational Science Foundation under CAREER Award IRI-9703122,Grant IIS-9800994, ITR IIS-0081246, and ITR IIS-0121678.of goods or resources, etc. Voting is the most general prefer-ence aggregation scheme, and has been used in several multi-agent decision making problems in AI, such as collaborativefiltering (e.g.[Pennock et al., 2000]) and planning among au-tomated agents (e.g.[Ephrati and Rosenschein, 1991; 1993]).A key problem voting mechanisms are confronted with isthat of manipulation by the voters. An agent is said to votestrategically when it does not rank the alternatives accord-ing to its true preferences, but differently so as to manipulatethe outcome to be more favorable to the agent. For exam-ple, if an agent prefers Nader to Gore to Bush, but knows thatNader has too few other supporters to win, while Gore andBush are close to each other, the agent would be better off bydeclaring Gore as its top candidate. Manipulation is an unde-sirable phenomenon. For one, because social choice schemesare tailored to aggregate preferences in a socially desirableway, and if the agents reveal their preferences insincerely, asocially undesirable candidate may be chosen.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[Gibbard,1973; Satterthwaite, 1975]. (A voting scheme is called dicta-torial if one of the voters dictates the social choice no matterhow the others vote). In automated group decision makingwhere the voters are software agents, the manipulability ofprotocols is even more problematic, for at least two reasons.First, the algorithms they use to decide how to vote must becoded explicitly. Given that the voting algorithm needs to bedesigned only once (by an expert), and can be copied to largenumbers of agents (even ones representing unsophisticatedhuman voters), it is likely that rational strategic voting will in-creasingly become an issue, unmuddied by irrationality, emo-tions, etc. Second, software agents have more computationalpower and are more likely to find effective manipulations.We take the following tack toward avoiding manipulation:ensuring that finding a beneficial manipulation is so hardcomputationally that it is unlikely that voters will be able tomanipulate. So, unlike in most of computer science, herehigh computational complexity is a desirable property. Theharder it is to manipulate, the better.Prior work on the complexity of manipulating electionshas focused on existing protocols[Bartholdi et al., 1989;Bartholdi and Orlin, 1991; Conitzer and Sandholm, 2002a].This paper is the first to take the next step of designingnew protocols that are especially hard to manipulate. Ratherthan designing these protocols from scratch, we show how totweak existing protocols to make manipulation computation-ally much more difficult, while leaving much of the originalnature of the protocol intact, for the following reasons:• Results on the computational complexity induced by atweak typically apply to a large family of protocols.• Many of the original protocol’s nice theoretical proper-ties are preserved by the tweak.• In practice, it will be much easier to replace a currentlyused protocol with a tweaked version of it, than with analtogether new protocol.The type of tweak we study in this paper is the follow-ing. All the candidates are paired in a preround; of each pairof candidates, only the winner of their pairwise election sur-vives. (The winner of the pairwise election between two can-didates is the candidate that is ranked above the other moreoften in the votes.) After the preround, the original protocolis executed on the remaining candidates. The schedule of thepreround (i.e., who faces who) can be determined before thevotes are collected; after the votes are collected; or while thevotes are collected (the processes are interleaved). We studythese three cases in Sections 4, 5, and 6, respectively.12 Definitions2.1 Elections and voting protocolsAn election consists of a set of candidates C; a set of votersV ; and a protocol for deciding on a winner w ∈ C given allthe voters’ votes. (Here, a vote is a total ordering of the candi-dates.) A deterministic protocol is a function from the set ofall combinations of