Barriers to manipulation in voting

Introduction In many situations, voters may vote strategically. That is, they may declare preferences that are not their true ones, with the aim of obtaining a better outcome for themselves. The following example illustrates this. Example 6.1. Consider an election with three alternatives, a, b, and c, and three voters, 1, 2, and 3. Suppose the rule used is plurality-an alternative gets a point each time it is ranked first by a voter, and the alternative with the most points wins-with ties broken toward alternatives earlier in the alphabet. Suppose voter 3 knows (or strongly suspects) that voter 1 will rank a first in her vote, and that voter 2 will rank b first. Voter 3‘s true preferences are c ≻ b ≻ a. If she votes truthfully, this will result in a three-way tie, broken in favor of a which is 3‘s least preferred alternative. If, instead, voter 3 ranks b first, then b will win instead. Hence, voter 3 has an incentive to cast a vote that does not reflect her true preferences. This is often referred to as manipulation or strategic voting; we will use “manipulation” throughout. Voting rules that are never manipulable are also referred to as strategyproof. We start by reviewing the Gibbard-Satterthwaite impossibility result (discussed also in Chapter 2), which states that with unrestricted preferences over three or more alternatives, only very unnatural rules are strategyproof. The main focus of the chapter is on exploring whether computational complexity can be an effective barrier to manipulation. That is, we may not be concerned about manipulation of a voting rule if it is computationally hard to discover how to manipulate it. Gibbard-Satterthwaite and Its Implications An important axiomatic result about the properties of voting rules is the Gibbard- Satterthwaite Theorem: Theorem 6.2 (Gibbard, 1973; Satterthwaite, 1975). Consider a (resolute)votingrule that is defined for some number m of alternatives with m ≥ 3, with no restrictionson the preference domain. Then, this rule must be at least one of the following: dictatorial: there exists a single fixed voter whose most-preferred alternative is chosenfor every profile; imposing: there is at least one alternative that does not win under any profile; manipulable (i.e., not strategyproof).

Duke Scholars

Author Vincent Conitzer Computer Science