Discrete Math ch. 1

Discrete Math Review Ch. 1 DO NOT TRY TO DO THE WORK ON THIS SHEET. SHOW YOUR WORK ON SEPARATE PAPER! Use for questions 1 – 13. For an election with four candidates (A, B, C, and D) we have the following preference schedule: Number of Choices 6 3 5 8 1st Choice D D A C 2nd Choice B A C A 3rd Choice A B B B 4th Choice C C D D 1) Using the plurality method, which candidate wins the election? 2) Using the Borda count method, which candidate wins the election? 3) Using the plurality-with-elimination method, which candidate wins the election? 4) Using the method of pairwise comparisons, which candidate wins the election? 5) In this election, name the Condorcet candidate, if there is one. 6) The ranking of the candidates using the extended plurality method is: 7) The ranking of the candidates using the extended plurality-with-elimination method is: 8) The ranking of the candidates using the extended Borda count method is: 9) The ranking of the candidates using the extended pairwise comparisons method is: 10) Using the recursive plurality ranking method, which candidate comes in last? 11) Using the recursive Borda count method, which candidate comes in second? 12) Using the recursive plurality-with-elimination ranking method, which candidate comes in second? 13) Using the recursive pairwise comparisons ranking method, which candidate comes in second? Solve each problem. 14) In a round robin tennis tournament, every player plays against every other player. If 11 players are entered in a round robin tennis tournament, how many matches will be played? 15) "If choice X is a winner of an election and, in a reelection, the only changes in the ballots are changes that only favor X, then X should remain a winner of the election." This fairness criterion is called the: 16) "If there is a choice that has a majority of the first-place votes in an election, then that choice should be the winner of the election." This fairness criterion is called the: 17) "If there is a choice that in a head-to-head comparison is preferred by the voters over every other choice, then that choice should be the winner of the election." This fairness criterion is called the: 18) “If choice X is a winner of an election and one (or more) of the other choices is removed and the ballots recounted, then X should still be the winner of the election.” This fairness criterion is called the: 19) An election is held among four candidates (A, B, C, and D). Using a voting method we will call X, the winner of the election is candidate A. Due to an irregularity in the original vote count, a recount is required. Before the recount takes place, candidate B drops out of the race. In the recount, still using voting method X, candidate D wins the election. Based on this information, we can say that voting method X violates the: 20) An election is held among four candidates (A, B, C, and D). Using a voting method we will call X, the winner of the election is candidate A. Due to an irregularity in the original procedures, a new election is required. Before the new election takes place, one of the voters changes his mind and moves A from third choice to second choice on his ballot. All other voters vote the same way they did in the original election. In the new election, still using voting method X, candidate D wins the election. Based on this information, we can say that voting method X violates the: 21) An election is held among three candidates (A, B, and C) using the Borda count method. There are 20 voters. If candidate A received 37 points and candidate B received 39 points, how many points did candidate C receive? 22) An election is held among five candidates (A, B, C, D, and E). There are 37 voters. Using the method of pairwise comparisons, A, B, and C win one pairwise comparison each. D wins three pairwise comparisons, and E wins all the rest. In this election, which candidate is the Condorcet candidate? (if there is one) 23) An election involving 5 candidates and 30 voters is held, and the results of the election are determined using the Borda count method. The maximum number of points a candidate can receive is: 24) An election involving 5 candidates and 30 voters is held, and the results of the election are to be determined using the Borda count method. Assuming there isn't a five-way tie, the minimum number of points a winning candidate can receive is: ANSWER KEY: 1.) D 2.) A 3.) C 4.) A 5.) A 6.) D, C, A, B 7.) C, D, A, B 8.) A, C, B, D 9.) A, C, B, D 10.) B 11.) C 12.) A 13.) C 14.) 55 = (11*10)/2 15.) Monotonicity 16.) Majority 17.) Condorcet 18.) Independence of Irrelevant Alternatives (IIA) 19.) Independence of Irrelevant Alternatives (IIA) 20.) Monotonicity 21.) 44pts = 120pts – 37pts – 39pts 22.) E 23.) 150pts max = 5pts * 30votes 24.) 91pts min = 450pts / 5ch, round up. Note: Could be a tie for first with 91, but not a 5-way tie.