Chapter 10 Exercises
Chapter 10 Exercises
10.1 An Introduction to Manipulability
10.2 Majority Rule and Condorcet's Method
Question 10.31
1. Consider the voting system for two candidates ( and ) and three voters in which the candidate with the fewest first-place votes wins. Produce two elections that show this voting system is manipulable.
1.
One example of two such elections is the following:
| Election 1 | |||
| Rank | Number of voters (3) | ||
| First | |||
| Second | |||
| Election 2 | |||
| Rank | Number of voters (3) | ||
| First | |||
| Second | |||
Question 10.32
2. Consider the voting system for two candidates ( and ) and three voters in which the candidate receiving an odd number of first-place votes wins. Produce two elections that show this voting system is manipulable.
Question 10.33
3. Consider the voting system for two candidates ( and ) and three voters in which the candidate receiving an even number of first-place votes wins. Produce two elections that show this voting system is manipulable.
3.
One example of two such elections is the following:
| Election 1 | |||
| Rank | Number of voters (3) | ||
| First | |||
| Second | |||
| Election 2 | |||
| Rank | Number of voters (3) | ||
| First | |||
| Second | |||
Question 10.34
4. There are at least two voting systems for two candidates ( and ) and three voters that are nonmanipulable and that treat all voters the same (meaning that if two voters were to exchange ballots, then the election outcome would be unchanged).
- What does May's theorem tell us about such a voting system?
- In one sentence, give an example of such a voting system (i.e., produce the rule that determines which of the two candidates, or , wins an election).
- In one sentence, give another example that is different from the example you gave in part (b) in that it produces a different winner for at least one election.
Question 10.35
5. There are at least three voting systems for two candidates ( and ) and three voters that are nonmanipulable and that treat both candidates the same (meaning that if all three voters change their ballots, then the election outcome also changes).
- What does May's theorem tell us about such a voting system?
- In one sentence, give an example of such a voting system (i.e., produce the rule that determines which of the two candidates wins an election).
- In one sentence, give two other examples that are different from the example you gave in part (b) in that they produce a different winner for at least one election.
5.
(a) The voting system does not treat all voters the same.
(b) A dictatorship in which Voter 1 is the dictator.
(c) A dictatorship in which Voter 2 is the dictator and a dictatorship in which Voter 3 is the dictator.
457
10.3 The Manipulability of Other Voting Systems for Three or More Candidates
Question 10.36
6. Consider the following election with four candidates and two voters:
Show that if the Borda count is being used, the voter on the left can manipulate the outcome (assuming the above ballot represents his or her true preferences).
Question 10.37
7.Example 4 (page 447) showed that the Borda count is manipulable if there are five candidates and six voters. Mimic what was done there to construct an example with seven candidates and eight voters.
7.
One way is to alter the elections in Example 4 of the text by adding and to the bottom of each of the six ballots in both elections, and then adding the two rightmost columns as shown.
| Election 1 | ||||||||
| Rank | Number of voters (8) | |||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| First | ||||||||
| Second | ||||||||
| Third | ||||||||
| Fourth | ||||||||
| Fifth | ||||||||
| Sixth | ||||||||
| Seventh | ||||||||
has the highest Borda score and is the winner.
The voter on the far left prefers to . By casting a disingenuous ballot (still preferring to , though), the outcome of the election is altered.
| Election 2 | ||||||||
| Rank | Number of voters (8) | |||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| First | ||||||||
| Second | ||||||||
| Third | ||||||||
| Fourth | ||||||||
| Fifth | ||||||||
| Sixth | ||||||||
| Seventh | ||||||||
Now has the highest Borda score and is the winner.
Question 10.38
8. Use the following election to illustrate the manipulability of the Borda count with three voters and four candidates:
Question 10.39
9. Show that the Borda count is manipulable if there are four candidates and five voters. (Hint: Start with the ballots in the previous exercise, and then add two ballots that cancel each other out.)
9.
The desired ballots (obtained as suggested in the statement of the exercise) are as follows:
| Election 1 | |||||
| Rank | Number of voters (5) | ||||
| 1 | 1 | 1 | 1 | 1 | |
| First | |||||
| Second | |||||
| Third | |||||
| Fourth | |||||
has the highest Borda score and is the winner.
The voter on the far left prefers to . By casting a disingenuous ballot (still preferring to , though), the outcome of the election is altered.
| Election 2 | |||||
| Rank | Number of voters (5) | ||||
| 1 | 1 | 1 | 1 | 1 | |
| First | |||||
| Second | |||||
| Third | |||||
| Fourth | |||||
Now, has the highest Borda score and is the winner.
Question 10.40
10. Building on the idea in the previous exercise, show that the Borda count is manipulable if there are six candidates and nine voters.
Question 10.41
11. Assume the following ballots give the true preferences of the voters and that the Borda count is being used. Show that at least one of the voters can improve the election outcome from her point of view by a unilateral change in her ballot.
11.
| Election 1 | ||||
| Rank | Number of voters (5) | |||
| 1 | 1 | 1 | 1 | |
| First | ||||
| Second | ||||
| Third | ||||
| Fourth | ||||
has the highest Borda score and is the winner. But the winner becomes if the leftmost voter changes his or her ballot to , , , . Thus, has the highest Borda score and is declared the winner.
| Election 1 | |||||
| Rank | Number of voters (5) | ||||
| 1 | 1 | 1 | 1 | 1 | |
| First | |||||
| Second | |||||
| Third | |||||
| Fourth | |||||
, , and have the fewest first-place votes and are thus eliminated, leaving as the winner using the Hare system. But the winner becomes if the leftmost voter changes his or her ballot to , , , .
Question 10.42
12.Coombs's rule is the voting system that operates like the Hare system, except that instead of deleting candidates with the fewest first-place votes one after another, it deletes candidates with the most last-place votes one after another. Use the following ballots to show that Coombs's rule is manipulable:
Question 10.43
13. Use the following election to show that the Hare system is manipulable:
13.
| Election 1 | |||||
| Rank | Number of voters (5) | ||||
| 1 | 1 | 1 | 1 | 1 | |
| First | |||||
| Second | |||||
| Third | |||||
| Fourth | |||||
, , and have the fewest first-place votes and are thus eliminated, leaving as the winner using the Hare system. But the winner becomes if the leftmost voter changes his or her ballot to , , , .
Question 10.44
14.
Use the following election to show that the plurality runoff rule is manipulable:
Question 10.45
15. Use the following election to show that sequential pairwise voting is manipulable. (Assume that the agenda is , , and .)
15.
| Election 1 | |||
| Rank | Number of voters (3) | ||
| 1 | 1 | 1 | |
| First | |||
| Second | |||
| Third | |||
Thus, is the winner with sequential pairwise voting and the agenda , , . But the winner becomes if the leftmost voter changes his or her ballot to , , .
Question 10.46
16. Given the ballots below, mimic what was done in Example 7 (page 449) to find an agenda for which __________ is the winner using sequential pairwise voting.
Question 10.47
17.
Suppose we have an election in which there is a single winner, using the Hare system. In a couple of sentences, explain why we know for sure that there is at least one voter who cannot manipulate this election in the sense of making a unilateral change in his or her ballot that will yield a preferred outcome for that voter, assuming the original ballot represented his or her true preferences.
17.
A winner with the Hare system must be ranked at the top of at least one voter’s ballot, or else it would be eliminated in the first round. For such a voter, there is no outcome preferred to his or her top choice being the single winner.
458
Question 10.48
18. Suppose that we have a voting system that satisfies unanimity: If every voter ranks the same candidate first, then that candidate is the unique winner. In a few sentences, explain why it is that if the system fails to satisfy the Pareto condition, it can be manipulated by some group.
Question 10.49
19. Assume that the following ballots give the voters′ true preferences, and the Borda count is being used. Find a voter who can manipulate this election in the sense of making a unilateral change in his or her ballot that will yield a single winner that is preferred by that voter to the original winner. Explain your answer.
19.
Answers will vary.
Question 10.50
20. Assume that the following ballots give the voters′ true preferences, and the Borda count is being used. Find all voters who cannot manipulate this election in the sense of making a unilateral change in their individual ballots that will yield a single winner who is preferred by that voter to the original winner. Explain your answer.
Question 10.51
21. Alfonse D'Amato (D) won the 1980 U.S. Senate race in New York by defeating Elizabeth Holtzman (H) and Jacob Javits (J). Reasonable estimates (based largely on exit polls) suggest that voters ranked the candidates according to the following table:
| 22% | 23% | 15% | 29% | 7% | 4% |
|---|---|---|---|---|---|
Use these ballots to show that plurality voting is group-manipulable.
21.
| Election 1 | |||||
| 22% | 23% | 15% | 29% | 7% | 4% |
Since has the most first-place votes, Alfonse D’Amato (D) is the winner by plurality voting. The plurality rule is group manipulable if the voters in the 7% group all change their ballots.
| Election 2 | |||||
| 22% | 23% | 15% | 29% | 7% | 4% |
Since has the most first-place votes, Elizabeth Holtzman ( ) is the winner by plurality voting.
Question 10.52
22. Consider the voting rule in which an alternative is among the winners if it receives at least one first-place vote. In one sentence, explain why this voting system is not manipulable.
Question 10.53
23. Consider the voting system in which the winner is determined by the total number of first- and second- place votes, with ties broken (when possible) according to the number of first-place votes. Thus, a candidate with no first-place votes and three second-place votes would defeat a candidate with two first-place votes and no second-place votes, but a candidate with two first-place votes and three second-place votes would defeat a candidate with one first-place vote and four second-place votes. Given Election 1 below, find a change in Voter 1's ballot that shows that this voting system is manipulable.
| Election 1 | |||
|---|---|---|---|
| Rank | Number of Voters (3) | ||
| First choice | |||
| Second choice | |||
| Third choice | |||
| Fourth choice | |||
| Fifth choice | |||
23.
If the first voter changes his preference so that is in first place and is still in third, fourth, or fifth place, then Candidate will be the winner since the candidate has 2 first- or second-place votes and has a first-place vote, whereas Candidate does not.
| Example of Election 2 | |||
| Rank | Number of voters (3) | ||
| First | |||
| Second | |||
| Third | |||
| Fourth | |||
| Fifth | |||
10.4 Impossibility
Question 10.54
24. Complete the proof of the weak version of the Gibbard-Satterthwaite theorem by handling the case where the winner with the voting paradox ballots is
- .
- .
Question 10.55
25. The Gibbard-Satterthwaite theorem says that the following four properties of voting systems cannot be satisfied simultaneously:
- Elections always have unique winners.
- It satisfies the Pareto condition.
- It is nonmanipulable.
- It is not a dictatorship.
Which of the four properties are satisfied by a dictatorship?
25.
Properties 1, 2, and 3
Question 10.56
26. Which of the four properties in Exercise 25 are satisfied by an "antidictatorship," where the election winner is whichever candidate Voter 1 ranks last on his or her ballot?
Question 10.57
27. Which of the four properties in Exercise 25 are satisfied if we use the plurality rule, with Voter 1's ballot utilized to break any ties that occur?
27.
Properties 1, 2, and 4
459
10.5 The Chair's Paradox
For Exercises 28 and 29, consider the preference lists from the chair's paradox (reproduced here) and assume that everyone knows the administration will vote for the J-Plan, but that no one knows anything about how the faculty will vote.
| Administration | Students | Faculty | |
|---|---|---|---|
| First choice | J-Plan | Terms | Semesters |
| Second choice | Terms | Semesters | J-Plan |
| Third choice | Semesters | J-Plan | Terms |
Question 10.58
28. In a sentence or two, explain why the students′ strategy to vote for Terms does not weakly dominate their strategy to vote for Semesters.
Question 10.59
29. In a sentence or two, explain why the students′ strategy to vote for Semesters does not weakly dominate their strategy to vote for Terms.
29.
If the faculty votes for Terms, then the students will get their first choice—Terms—by voting for Terms, but they will get their third choice—the J-plan—by voting for Semesters.
A-27
Chapter Review
Question 10.60
30. With the ballots in Exercise 21, who would have won if Condorcet's method had been used instead of plurality?
Question 10.61
31. There is a modified version of Condorcet's method called the weak Condorcet rule: A candidate is among the winners precisely if he or she would defeat or tie every other candidate in a one-on-one contest. Notice that with an odd number of voters, the weak Condorcet rule is identical to Condorcet's method. Use the following ballots to show that the weak Condorcet rule is manipulable:
29.
If the faculty votes for Terms, then the students will get their first choice—Terms—by voting for Terms, but they will get their third choice—the J-plan—by voting for Semesters.
31. Consider what happens if the leftmost voter changes his or her ballot to , , , .
| Election 1 | ||||
| Rank | Number of voters (4) | |||
| 1 | 1 | 1 | 1 | |
| First | ||||
| Second | ||||
| Third | ||||
| Fourth | ||||
Because is the only candidate in the first election that either wins or ties each other candidate in a head-to-head match-up, by the weak Condorcet method, wins outright in the first election. However, the winner becomes if the voter on the left changes his or her ballot as follows:
| Election 2 | ||||
| Rank | Number of voters (4) | |||
| 1 | 1 | 1 | 1 | |
| First | ||||
| Second | ||||
| Third | ||||
| Fourth | ||||
wins, thus showing that the weak Condorcet method is manipulable.
Question 10.62
32.Copeland's rule is a voting system that, like Condorcet's method, looks at one-on-one contests. It, however, takes as the election winner the candidate with the best "win-loss record." Use the following ballots to show that Copeland's rule is manipulable:
Question 10.63
33. Suppose we have an election in which there is a single winner, using plurality voting. In a couple of sentences, explain why we know for sure that there is at least one voter who cannot manipulate this election in the sense of making a unilateral change in his or her ballot that will yield a preferred outcome for that voter, assuming the original ballot represented his or her true preferences.
33.
A winner in plurality voting must be ranked at the top of at least one voter’s ballot. For such a voter, there is no outcome preferred to his or her top choice being the single winner.
Question 10.64
34. Consider the voting rule in which an alternative is among the winners if it has at least two first-place votes.
- In one sentence, explain why this voting system is not manipulable.
- Explain why the following two elections don't contradict part (a).
Election 1 Rank Number of Voters (4) First choice Second choice Third choice Election 2 Rank Number of Voters (4) First choice Second choice Third choice - Intuitively, does it seem to you that Voter 1, on the left in part (b), has secured a better outcome by submitting a disingenuous ballot?