maths.free › Discrete Math & Logic › 11. Voting and Apportionment › Voting Methods

Voting Methods

Apply plurality voting to determine a winner.

Learning Objectives

After completing this section, you should be able to:

  1. Apply plurality voting to determine a winner.
  2. Apply runoff voting to determine a winner.
  3. Apply ranked-choice voting to determine a winner.
  4. Apply Borda count voting to determine a winner.
  5. Apply pairwise comparison and Condorcet voting to determine a winner.
  6. Apply approval voting to determine a winner.
  7. Compare and contrast voting methods to identify flaws.

Majority versus Plurality Voting

When an election involves only two options, a simple majority is a reasonable way to determine a winner. A majority is a number equaling more than half, or greater than 50 percent of the total.

Let’s take a look at the outcomes of U.S. presidential elections to understand more. displays the results of the 2000 U.S. presidential election. Like most presidential elections, this election involved more than two options. If that is the case, is it possible that no single candidate will receive more than half of the votes cast?

Candidate (Party Label)Popular Vote Total
Al Gore (Democrat)50,999,897
George W. Bush (Republican)50,456,002
Ralph Nader (Green)2,882,955
Patrick J. Buchanan (Reform/Independent)448,895
Harry Browne (Libertarian)384,431
Howard Phillips (Constitution)98,020
Other134,900
Total:105,405,100
Majority of Popular Vote in the 2000 U.S. Presidential Election

Try it.

Refer back to . Did any single candidate secure the majority of popular votes?

Solution

Step 1: Calculate 50 percent of 105,405,100 by multiplying the decimal form of 50 percent, which is 0.50, by 158,394,605: \(0.50(105,405,100)=52,702,550\)

Step 2: Determine the minimum number of votes needed to have a majority. The minimum number of votes required is the lowest counting number that is larger than 50 percent of the votes. To have a majority, an individual candidate must have more than 52,702,550; so, a majority candidate must have 52,702,551 votes or more.

Step 3: Compare the number of votes each candidate received to 52,702,551. According to the data in , none of the candidates secured a majority.

Unlike in the 2000 U.S. presidential election, a candidate won the majority of votes in the 2020 election (see ). It is a common occurrence for no single candidate to receive a majority of the votes in an election with more than two candidates. When this occurs, the candidate with the largest portion of the votes is said to have a plurality.

Plurality of Popular Vote in the 2000 U.S. Presidential Election

Try it.

Refer again to . In the 2000 U.S. presidential election, which candidate had a plurality of popular votes?

Solution

Al Gore secured 50,999,897 votes which was more than any other single candidate. Therefore, he had a plurality of the popular votes.

Your plans for Imaginarian elections will likely include primary elections, or preliminary elections to select candidates for a principal or general election. displays the results of the 2018 U.S. Senate Republican primary for Maryland.

Condensed — the full section is in OpenStax Contemporary Mathematics.

Runoff Voting

Has your family ever debated what to have for dinner? Suppose your family is deciding on a restaurant and exactly half of you want to have pizza but the other half want hamburgers. How do you decide when the result is a tie? You need a tiebreaker!

Will the new democracy of Imaginaria need tiebreakers? When no candidate satisfies the requirements to win the election, a runoff election, or second election, is held to determine a winner.

How would runoff voting work in Imaginaria? There are many types of runoff voting systems, which are voting systems that utilize a runoff election when the first round does not result in a winner. The method for implementing a runoff election can vary widely, particularly in the criteria used to determine whether a candidate will be on the ballot in the second election. For example, a two-round system is a runoff voting system in which only the top candidates advance to the runoff election. In some two-round systems, only the top two candidates are on the second ballot, or it may be any candidate who secures a certain percentage of the vote will advance. The Hare Method is another runoff voting system in which only the candidate(s) with the very least votes are eliminated. This can potentially result in several rounds of runoff elections.

Runoff Election for Condominium Association President

Try it.

A condominium association elects a new president every two years by a two-round system of voting. If none of the candidates receive a majority, the association charter states that the top two candidates will be eligible to participate in a runoff election. In a particular year, five residents were nominated. The results of the first round are given in the table below.

CandidateVotes in First Round
Abou18
Baiocchi10
Campana5
Dali11
Eugene4
  1. Is there a winner based on the first round? Why or why not?
  2. If there is a winner, who won? If there should be a runoff, who will advance to the second round?
Solution
  1. A majority of 48 total votes is required to win. Begin by finding 50 percent of 48, which is calculated as follows: \(0.50(48)=24\). A majority is 25 or more. No candidate has a majority, so there is no winner based on the first round.
  2. Abou and Dali advance to the second round.

Steps to Determine Winner by Plurality or Majority Election with Runoff

To determine the winner by plurality or when a majority election with runoff occurs, we take these three steps:

Step 1: If a majority is required to win the election, determine the number of votes needed to achieve a majority. This is the least whole number greater than 50 percent of the total votes. If a majority is not required, move to Step 2.

Step 2: Count the number of votes for each candidate in the current round of voting. If a single candidate has enough votes to win a plurality, or a majority as appropriate, then you are done! Otherwise, eliminate a predetermined number of candidates based on the rules of the election. Elimination conditions may vary. For example, the rules may state that the candidate(s) with the fewest votes will be eliminated (as in the Hare method), or that only the candidates meeting a certain threshold will move on (as in a two-round system). Once the appropriate candidates are eliminated, move on to Step 3.

Step 3: Hold a runoff election. If the runoff is simulated using a list of voter’s preferences, renumber the preferences to reflect the remaining number of options in such a way that the original order of preference is retained. Then repeat Step 2.

Note: The second and third steps may be repeated as many times as necessary for voting procedures that allow multiple runoffs.

Condensed — the full section is in OpenStax Contemporary Mathematics.

Ranked-Choice Voting

In and Your Turn 11.4, you were given a list that ordered each voter’s preferences. This ordering is called a preference ranking. A ballot in which a voter is required to give an ordering of their preferences is a ranked ballot, and any voting system in which a voter uses a ranked ballot is referred to as ranked voting.

The vote for the Academy Awards uses a ranked ballot. The table below provides an example of a ranked ballot for the 2020 Academy Award nominees for Best Director.

Candidate for Best DirectorRank top choice as 1, next choice as 2, and so on.
Martin Scorsese, The Irishman12345
Todd Phillips, Joker12345
Sam Mendes, 191712345
Quentin Tarantino, Once Upon a Time in Hollywood12345
Bong Joon-ho, Parasite12345

As you decide on the voting methods that will be used in your new democracy, budget must be a consideration. You might consider a particular type of ranked voting called ranked-choice voting (RCV), which simulates a series of runoff elections without the usual time and expense involved when voters must repeatedly return to the polls, like we did in .

The method of ranked-choice voting (RCV), also called instant runoff voting (IRV), is a version of the Hare Method, using preference ranking so that, if no single candidate receives a majority, the least popular selections can be eliminated and the results can be recounted, without the need for more elections.

As we explore examples of ranked voting, we will summarize the voters’ preference rankings using a table in which the top row shows the number of ballots that ranked the options in the same order. Let’s practice interpreting the information in this type of table.

Now that we’ve covered how to read a summary of preference rankings, let’s practice using the ranked-choice method to determine the winner of an election. Recall that ranked-choice voting is still the Hare Method where the candidate with the very least number of votes is eliminated each round until a majority is attained. The difference here is that the voters have completed a ranked ballot, so they don't have to visit the polls multiple times. Here are the steps for ranked-choice voting.

Condensed — the full section is in OpenStax Contemporary Mathematics.

Steps to Determine Winner by Ranked-Choice Voting

To determine the winner when ranked-choice voting occurs, we take these three steps:

Step 1: Determine the number of votes needed to achieve a majority. This is the least whole number greater than 50 percent of the total votes.

Step 2: Count the number of first place votes for each candidate. If a candidate has a majority, that candidate wins the election and we are done! Otherwise, eliminate the candidate(s) with the fewest votes and complete Step 3.

Step 3: Reallocate the votes to the remaining candidates, and repeat Step 2.

Condensed — the full section is in OpenStax Contemporary Mathematics.

Borda Count Voting

Ranked-choice voting is one type of ranked voting that simulates multiple runoffs based on ranked ballots. Another type of ranked voting is the Borda count method, which uses ranked ballots that award candidates points corresponding to the number of candidates ranked lower on each ballot.

To understand how this works, let’s review the favorite colors of our kindergarten class from the table below. Let’s focus on the votes represented by the first column of the preference summary.

Number of Ballots4647
Red2625
Blue1214
Green6552
Yellow5463
Purple4341
Pink3136

Each student had six options. This first column tells us that four students ranked blue as their first choice, red as their second choice, pink as their third choice, purple as their fourth choice, yellow as their fifth choice, and green as their sixth choice. Blue was ranked higher than \(6-1=5\) other colors. For each of the four students who completed their ballot in this way, blue would receive five points. Since there were four ballots with this ordering, blue would receive \(5(4)=20\) points from the first column. To determine the total points for each candidate, we have to find the sum of the points they received in each column.

To determine the winner of a contest using the Borda count method, we must compare total number of points earned by each candidate. The candidate with the most points is the winner. Each row of the preference summary corresponds to a single candidate. To find the number of points received by a particular candidate in the preference summary, or their Borda score, we will need to focus on the row in which that candidate appears.

Before we practice determining the winner of a Borda count election, let’s examine how to find the Borda score for a single candidate.

Now let’s determine the winner of an election by comparing the Borda scores for each of the candidates.

Condensed — the full section is in OpenStax Contemporary Mathematics.

Pairwise Comparison and Condorcet Voting

We have discussed two kinds of ranked voting methods so far: ranked-choice and Borda count. A third type of ranked voting is the pairwise comparison method, in which the candidates receive a point for each candidate they would beat in a one-on-one election and half a point for each candidate they would tie. If one candidate earns more points than the others, then that candidate wins. This method is one of several Condorcet voting methods, which are methods in which candidates are ranked and then compared pairwise to each other, a candidate having to beat all others in order to win. These methods vary in the way candidates are scored, and there is not always a clear winner. A candidate who wins each possible pairing is known as a Condorcet candidate. These terms are named after the Marquis de Condorcet, a French philosopher and mathematician who preferred the pairwise comparison method to the Hare method and made public arguments in its favor.

If you include a Condorcet voting method in the constitution of Imaginaria, the election supervisors may want to use a pairwise comparison matrix like the one in . It’s a tool used to list the number of wins associated with each pairing of two candidates. Each candidate will receive a point for each win and a half a point for each tie. Each pairing is listed twice, once for the number of wins of a candidate over a particular challenger and once for the number of wins of the challenger over that candidate.

Steps to Determine a Winner by Pairwise Comparison Method Using a Matrix

To determine the winner when the pairwise comparison method is used, we take these three steps:

Step 1: On the matrix, indicate a losing matchup by crossing out a box, \(\times\), and tie match ups by drawing a slash through the box, \(\\).

Step 2: Award each candidate 1 point for a win, half a point for a tie, and 0 points for a loss.

Step 3: Identify the winner, which is the candidate with the most points.

Before you decide on the pairwise comparison method for Imaginaria, review what’s involved in constructing a pairwise comparison matrix from a summary of ranked ballots. Then we can use the matrix to determine the winner of the election. Does the winner using the Borda method still win?

Construct and Use a Pairwise Comparison Matrix

Try it.

Consider the summary of ranked ballots shown in the table below. Determine the winner of an election using the pairwise comparison method.

Number of Ballots9590110115
Option A4411
Option B2222
Option C3134
Option D1343
  1. Construct a pairwise comparison matrix for the sample summary of ranked ballots in the table above.
  2. Use the pairwise comparison method to determine a winner.
  3. Recall that in , Candidate A won by the ranked-ballot method, and Candidate B won by the Hare method. Did the same candidate win using the pairwise comparison method?
  4. Is the winner a Condorcet candidate?
Solution

There are four candidates on the ballots. We will need a row and a column for each candidate in addition to the headings, so we will draw a five by five matrix.

  1. Step 1: Refer to to determine the values that belong in each cell.
    • A over B: A is preferred to B in columns 3 and 4. So, A scores \(110+115=225\) points.
    • A over C: A is preferred to C in columns 3 and 4. So, A scores 225 points again.
    • A over D: Similarly, A scores 225 points.
    • B over A: B is preferred to A in columns 1 and 2. So, B scores \(95+90=185\) points.

    Step 2: Continuing in this way, we complete the pairwise comparison matrix, as shown in .

  2. Step 1: Losing pairings are crossed off with an \(\times\). In the event of a tie, we will draw a slash, \(\text{\}\).

    Step 2: Determine the number of points for each candidate by analyzing their row of wins. Each win is 1 point, each loss, \(\times\), is 0 points, and each tie, \(\text{\}\), is half a point. Construct an additional column for each candidate’s points.


    Step 3: The winner by the pairwise comparison method is Option A with 3 points.
  3. Option A was not the winner by the Hare method.
  4. The winner, Option A, is a Condorcet candidate because Option A won each pairwise comparison.

Condensed — the full section is in OpenStax Contemporary Mathematics.

Three Key Questions

Before you decide if you want to use the pairwise comparison method for Imaginarian elections, let’s consider three questions that might affect your decision.

  1. Is there always a winner?
  2. If there is a winner, is the winner always a Condorcet candidate?
  3. If there is a Condorcet candidate, does that candidate always win?

Let’s think about why these questions might be important to you if you chose the pairwise comparison method. First, if no candidate meets the criteria to win an election, you will need a backup plan such as a runoff election. Second, if the winner is not a Condorcet candidate, then there is at least one candidate who beat the winner in a pairwise matchup and the supporters of that candidate might question the validity of the election. Finally, if there is a Condorcet candidate who beat every other candidate in a pairwise matchup, it is reasonable to conclude that it would be unfair for anyone else to win. The rest of the examples in this section should illustrate these key concepts.

Rock, Paper, Scissors by Pairwise Comparison

Try it.

Suppose that three people are playing the game Rock, Paper, Scissors. On the count of three, each person shows a hand signal for rock, paper, or scissors. Each hand signal beats another hand signal. The group keeps having a tie because Person A always picks rock, Person B always picks paper which beats rock, and Person C always picks scissors which beats paper, and is beaten by rock! This leads to a disagreement about which choice is best. They decide to use the pairwise comparison method determine the winner. Their preference rankings are given in the following table.

VotersABC
Rock (R)132
Paper (P)213
Scissors (S)321
Solution

Construct the comparison matrix:

There is a tie! There is no winner.

illustrates the answer to the first key question. The pairwise comparison method does not always result in a winner. For example, much like the game of Rock, Paper, Scissors, it is possible for a cyclic pattern to emerge in which each candidate beats the next until the last candidate who beats the first.

Now, you have the answer to the second key question. The pairwise comparison matrix in YOUR TURN 11.10 is an example of a scenario where a winner is not a Condorcet candidate.

Condensed — the full section is in OpenStax Contemporary Mathematics.

Approval Voting

The last type of voting system you will consider for your budding democracy is an approval voting system. In this system, each voter may approve any number of candidates without rank or preference for one over another (among the approved candidates), and the candidate approved by the most voters wins. This voting system has aspects in common with plurality voting and Condorcet voting methods, but it has characteristics that distinguish it from both. An approval voting ballot lists the candidates and provides the option to approve or not approve each candidate.

The term “approval voting” was not used until the 1970s Brams, Steven J.; Fishburn, Peter C. (2007), Approval Voting, Springer-Verlag, p. xv, ISBN 978-0-387-49895-9, although its use has been documented as early as the 13th century (Brams, Steven J. (April 1, 2006). The Normative Turn in Public Choice (PDF) (Speech). Presidential Address to Public Choice Society. New Orleans, Louisiana.) Approval voting has the appeal of being simpler than ranked voting methods. It also allows an individual voter to support more than one candidate equally. This has appeal for those who do not want a split vote among a few mainstream candidates to lead to the election of a fringe candidate. It also has appeal for those who want an underdog to have a chance of success because voters will not worry about wasting their vote on a candidate who is not believed likely to win.

Rock, Paper, Scissors, Lizard, Spock

Try it.

Suppose that Person A/B/C were just about to give up on their game of Rock, Paper, Scissors when they were joined by Person D who reminded them that their updated version, Rock, Paper, Scissors, Lizard, Spock was a far superior game with the added rules that Lizard eats Paper, Paper disproves Spock, Spock vaporizes Rock, Rock crushes Lizard, Lizard poisons Spock, Spock smashes Scissors, and Scissors decapitates Lizard.

Person D encourages their friends to hold a new election. This time, for the sake of simplicity, the group decides to use approval voting to determine the best move in the game. The summary of approval ballots for Rock, Paper, Scissors, Lizard, Spock is given in the table below.

VotersABCD
RockYesNoNoNo
PaperNoYesNoNo
ScissorsNoNoYesNo
LizardNoNoNoYes
SpockYesYesYesYes
Solution

Count the number of approval votes for each candidate by counting the number of “Yes” votes in each row of the table.

  • Rock: 1
  • Paper: 1
  • Scissors: 1
  • Lizard: 1
  • Spock: 4

Spock is the winning candidate, approved by four voters!

Condensed — the full section is in OpenStax Contemporary Mathematics.

Compare and Contrast Voting Methods to Identify Flaws

Wow! We have covered a lot of options for the voting methods. Now, you need to decide which one is best for Imaginaria. Imaginarians might consider characteristics of certain voting systems desirable and others undesirable. In some cases, voters may consider these undesirable traits to be flaws in a voting system that are significant enough to motivate them to reject that system. If you are feeling a bit overwhelmed by this decision, maybe it would help to read about the experiences of others who have faced similar questions.

Consider the 2000 U.S. presidential election in which Green Party candidate Ralph Nader and Reform Party candidate Pat Buchanan were on the ballet running against the mainstream candidates, Democrat Al Gore and Republican George W. Bush. The voting results for Florida are given in .

CandidatePartyVotesPercentage
(G) George W. BushRepublican2,912,79048.85%
(A) Al GoreDemocrat2,912,25348.84%
(R) Ralph NaderGreen97,4881.63%
(P) Pat BuchananReform17,4840.29%
(H) Harry BrownLibertarian16,4150.28%
(O) 7 Other CandidatesOther6,6800.11%
Total5,963,110

In more than one state, Buchanan was able to split the Republican vote enough to allow Gore to win that state. Nader split the Democrat vote in Florida and New Hampshire by enough votes to prevent Gore from winning those states. Had Gore won either state, he would have had enough electoral votes to win the election. Instead, Bush won. This is an example of a flaw in the plurality system of voting: the spoiler.

A spoiler is a less popular candidate who takes votes from a more popular candidate with similar positions, swinging the race to another candidate with vastly different views that they would not support. This encourages voters not to vote for the candidate that they perceive to be the best, but instead for the candidate they can live with who they perceive to have a better chance of winning. Some voters may prefer a method such as approval voting, which does not have this trait in common with plurality voting.

The results in and Your Turn 11.14 highlight one of the characteristics of approval voting. Ralph Nader moved up from a distant third place finish to a close second place finish when Al Gore’s supporters approved him on their ballots. In this way, fringe candidates have a better chance of winning, which some voters consider a flaw but others consider a benefit.

Condensed — the full section is in OpenStax Contemporary Mathematics.

Key Concepts

  • In plurality voting, the candidate with the most votes wins.
  • When a voting method does not result in a winner, runoff voting can be used to do so.
  • Ranked-choice voting, also known as instant runoff voting, is one type of ranked voting system.
  • The Borda count method is a type of ranked voting system in which each candidate is given a Borda score based on the number of candidates ranked lower than them on each ballot.
  • When pairwise comparison is used, the winner will be the Condorcet candidate if one exists.
  • Approval voting allows voters to give equally weighted votes to multiple candidates.
  • When a voter finds a characteristic of a particular voting method unappealing, they may consider that characteristic a flaw in the voting method and look for an alternative method that does not have that characteristic.

Videos

  • How Does Ranked-Choice Voting Work?
  • Determine Winner of Election by Ranked-Choice Method (aka Instant Runoff)
  • Determine Winner of Election by Borda Count Method
  • Determine Winner of Election by Pairwise Comparison Method

Practice (15)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. Refer back to . Did any single candidate secure the majority of popular votes?

    كشفت الإجابة

    Step 1: Calculate 50 percent of 105,405,100 by multiplying the decimal form of 50 percent, which is 0.50, by 158,394,605: \(0.50(105,405,100)=52,702,550\)

    Step 2: Determine the minimum number of votes needed to have a majority. The minimum number of votes required is the lowest counting number that is larger than 50 percent of the votes. To have a majority, an individual candidate must have more than 52,702,550; so, a majority candidate must have 52,702,551 votes or more.

    Step 3: Compare the number of votes each candidate received to 52,702,551. According to the data in , none of the candidates secured a majority.

  2. Refer again to . In the 2000 U.S. presidential election, which candidate had a plurality of popular votes?

    كشفت الإجابة

    Al Gore secured 50,999,897 votes which was more than any other single candidate. Therefore, he had a plurality of the popular votes.

  3. A condominium association elects a new president every two years by a two-round system of voting. If none of the candidates receive a majority, the association charter states that the top two candidates will be eligible to participate in a runoff election. In a particular year, five residents were nominated. The results of the first round are given in the table below.

    CandidateVotes in First Round
    Abou18
    Baiocchi10
    Campana5
    Dali11
    Eugene4
    1. Is there a winner based on the first round? Why or why not?
    2. If there is a winner, who won? If there should be a runoff, who will advance to the second round?
    كشفت الإجابة
    1. A majority of 48 total votes is required to win. Begin by finding 50 percent of 48, which is calculated as follows: \(0.50(48)=24\). A majority is 25 or more. No candidate has a majority, so there is no winner based on the first round.
    2. Abou and Dali advance to the second round.

  4. The five members of the Chionilis family—Annette, Rene, Seema, Titus, and Galen—have decided to get takeout for dinner. They are trying to decide on a restaurant. The options are Rainbow China, Dough Boys Pizza, Taco City, or Caribbean Flavor. They will use majority election with runoffs where the restaurant with the fewest votes is eliminated in each round. The preferences of each family member are listed by first initial in the table below. An entry of 1 represents the person’s first choice; 2, their second; and so on. For example, Annette’s second choice is Dough Boys Pizza.

    OptionsARSTG
    Rainbow China13313
    Dough Boys Pizza22121
    Taco City34242
    Caribbean Flavor41434

    Use the information in the table to answer the following questions.

    1. Which common type of runoff voting method is this?
    2. List the results of each round of voting based on this information and determine which restaurant was ultimately chosen.
    كشفت الإجابة
    1. the Hare Method
    2. Step 1: Determine the number of votes necessary to have a majority. There are five family members, so 50 percent of 5 is \(0.50(5)=2.5\). A majority is three or more votes.
      Step 2: Count the number of votes for each restaurant in the first election. In a list of voter preferences, the 1s represent the top choice of each voter, which corresponds to their vote in the first round.
      Results of Round 1:
      • Rainbow China — 2 votes
      • Dough Boys — 2 votes
      • Taco City — 0 votes
      • Caribbean Flavor — 1 vote

      No restaurant received a majority. Eliminate Taco City, which has the fewest first place votes:
      OptionsARSTG
      Rainbow China13313
      Dough Boys Pizza22121
      Caribbean Flavor41434

      Step 3: Hold a runoff election. In other words, hold a second round. Since we have a list of the voters’ preferences with the eliminated option removed, we will renumber the preferences as first, second, and third so that we keep the original order of preference. The result is that we will count the second-place vote of any voter whose first choice was eliminated.
      OptionsARSTG
      Rainbow China13212
      Dough Boys Pizza22121
      Caribbean Flavor31333

      Step 4: Repeat the process from Step 2. Count the number votes for each restaurant in the first-round election. Since we are using a list of preferences, we need to count the number of 1s received by each restaurant.
      Results of Round 2:
      • Rainbow China — 2 votes
      • Dough Boys — 2 votes
      • Caribbean Flavor — 1 vote

      No single restaurant has three votes. Eliminate Caribbean Flavor, which has the fewest first place votes.
      OPTIONSARSTG
      Rainbow China13212
      Dough Boys Pizza22121

      Step 5: Repeat the process from Step 3. Hold another runoff election. This will be Round 3. Renumber the voters' preferences as first and second this time.
      OptionsARSTG
      Rainbow China12212
      Dough Boys Pizza21121

      Step 6: Repeat the process from Step 2 one last time. Count the number of first place votes for each remaining restaurant.

      Results of Round 3:

      • Rainbow China — 2 votes
      • Dough Boys — 3 votes

      Determine whether any one choice has a majority. Yes! Dough Boys has three votes, so it is the winner!

  5. Refer to the table below containing voters’ preference rankings to answer the following questions.

    Number of Ballots10020015075
    Option A1434
    Option B2342
    Option C4211
    Option D3123
    1. How many voters ranked the options in the following order: Option A in fourth place, Option B in second place, Option C in first place, and Option D in third place?
    2. How many ballots in total were collected?
    3. How many voters indicated that Option C was their first choice?
    كشفت الإجابة

    1. The column farthest to the right displays this ordering. The top entry in this column is 75; so, there were 75 voters who ranked the options in this way.
    2. The sum of the top row gives the total number of ballots collected: \(100+200+150+75=525\). So, there were 525 ballots collected.
    3. In the Option C row, there are two entries of 1 which indicate a first choice for that option. These occur in the last two columns. The sum of the top entries in these columns is \(150+75=225\). So, 225 voters indicated Option C as their first choice.

  6. Let’s review the kindergarten class color preferences again, and this time determine which color would be selected based on these results using the ranked-choice method.

    Number of Ballots4647
    Red2625
    Blue1214
    Green6552
    Yellow5463
    Purple4341
    Pink3136
    كشفت الإجابة

    Step 1: Determine whether any candidate received a majority. There were 21 ballots. Fifty percent of 21 is \(0.50(21)=10.5\). A majority is 11.

    Step 2: Count the number of first place votes for each candidate. If a candidate has a majority, that candidate wins the election. Otherwise, eliminate the candidate(s) with the fewest votes.

    • Red: 0
    • Blue: \(4+4=8\)
    • Green: 0
    • Yellow: 0
    • Purple: 7
    • Pink: 6

    Notice that \(8+7+6=21\), which is the total number of ballots. Confirming this helps to catch any arithmetic or counting errors. No candidate has a majority with 11 or more votes. We must eliminate red, green, and yellow which had the fewest votes with 0 each. The remaining votes that must be counted for Round 2 are given in the table below.

    Number of Ballots4647
    Blue1214
    Purple4341
    Pink3136

    Step 3: Reallocate the votes to the remaining candidates. We can do this by numbering the choices as 1, 2, and 3 in such a way that the order of preference is retained as seen in the table below:

    Number of Ballots4647
    Blue1212
    Purple3331
    Pink2123

    Step 4: Repeat the process from Step 2. Count the number of first place votes for each candidate. If a candidate has a majority, that candidate wins the election. Otherwise, eliminate the candidate(s) with the fewest votes.

    • Blue: \(4+4=8\)
    • Purple: 7
    • Pink: 6

    Confirm that \(8+7+6=21\). Great! No candidate has 11 or more votes. We must eliminate pink which had the fewest votes with 6. The remaining votes that must be counted for Round 2 are shown in the table below.

    Number of Ballots4647
    Blue1212
    Purple3331

    Step 5: Repeat the process from Step 3. Reallocate the votes to the remaining candidates. We can do this by numbering the choices as 1 and 2;

    Number of Ballots4647
    Blue1112
    Purple2221

    Step 6: Repeat the process from Step 2 one last time. Count the number of first place votes for each candidate. If a candidate has a majority, that candidate wins the election. Otherwise, eliminate the candidate(s) with the fewest votes.

    • Blue: \(4+6+4=14\)
    • Purple: 7

    Blue has a majority and wins the election!

  7. Let’s review the ballots from the kindergarten class again, as shown in the table below. This time, let’s determine the Borda score received by the color purple.

    Number of Ballots4647
    Red2625
    Blue1214
    Green6552
    Yellow5463
    Purple4341
    Pink3136
    كشفت الإجابة

    Step 1: Find the number of points received by the candidate in each column.

    Column 1: \(4\times (6-4)=4\times 2=8\)

    Column 2: \(6\times (6-3)=6\times 3=18\)

    Column 3: \(4\times (6-4)=4\times 2=8\)

    Column 4: \(7\times (6-1)=7\times 5=35\)

    Step 2: Find the sum of the points received in each column. This is the total number of points received by this candidate: \(8+18+8+35=69\)

    This process can also be combined into one step as shown here.

    \(\begin{array}{l}4\times (6-4)+6\times (6-3)+4\times (6-4)+7\times (6-1) \\ =4\times 2+6\times 3+4\times 2+7\times 5 \\ =8+18+8+35 \\ =69\end{array}\)

    Purple received 69 points in this election.

  8. Use the table below, which displays a sample preference summary, to answer the questions that follow.

    Number of Ballots9590110115
    Option A4411
    Option B2222
    Option C3134
    Option D1343
    1. Use the ranked-choice voting method to determine the winner of the election.
    2. Use the Borda count method to determine the winner of the election.
    كشفت الإجابة

    1. Step 1: Determine the number of votes needed to achieve a majority. The number of ballots is \(95+90+110+115=410\). Fifty percent of 410 is \(0.50(410)=205\). So, 206 votes or more is a majority.

      Step 2: Count the number of first place votes for each candidate.

      • Option A has \(110+115=225\)
      • Option B has 0
      • Option C has 90
      • Option D has 95
      Since Option A has a majority, Option A is the winner by the ranked-choice method.

    2. The Borda scores would be:
      • Option A: \(95(4-4)+90(4-4)+110(4-1)+115(4-1)=675\)
      • Option B: \(95(4-2)+90(4-2)+110(4-2)+115(4-2)=820\)
      • Option C: \(95(4-3)+90(4-1)+110(4-3)+115(4-4)=475\)
      • Option D: \(95(4-1)+90(4-3)+110(4-4)+115(4-3)=490\)

      Since Option B has a Borda score of 820 points, Option B is the winner by the Borda count method.

  9. Consider the summary of ranked ballots shown in the table below. Determine the winner of an election using the pairwise comparison method.

    Number of Ballots9590110115
    Option A4411
    Option B2222
    Option C3134
    Option D1343
    1. Construct a pairwise comparison matrix for the sample summary of ranked ballots in the table above.
    2. Use the pairwise comparison method to determine a winner.
    3. Recall that in , Candidate A won by the ranked-ballot method, and Candidate B won by the Hare method. Did the same candidate win using the pairwise comparison method?
    4. Is the winner a Condorcet candidate?
    كشفت الإجابة

    There are four candidates on the ballots. We will need a row and a column for each candidate in addition to the headings, so we will draw a five by five matrix.

    1. Step 1: Refer to to determine the values that belong in each cell.
      • A over B: A is preferred to B in columns 3 and 4. So, A scores \(110+115=225\) points.
      • A over C: A is preferred to C in columns 3 and 4. So, A scores 225 points again.
      • A over D: Similarly, A scores 225 points.
      • B over A: B is preferred to A in columns 1 and 2. So, B scores \(95+90=185\) points.

      Step 2: Continuing in this way, we complete the pairwise comparison matrix, as shown in .

    2. Step 1: Losing pairings are crossed off with an \(\times\). In the event of a tie, we will draw a slash, \(\text{\}\).

      Step 2: Determine the number of points for each candidate by analyzing their row of wins. Each win is 1 point, each loss, \(\times\), is 0 points, and each tie, \(\text{\}\), is half a point. Construct an additional column for each candidate’s points.


      Step 3: The winner by the pairwise comparison method is Option A with 3 points.
    3. Option A was not the winner by the Hare method.
    4. The winner, Option A, is a Condorcet candidate because Option A won each pairwise comparison.

  10. Suppose that three people are playing the game Rock, Paper, Scissors. On the count of three, each person shows a hand signal for rock, paper, or scissors. Each hand signal beats another hand signal. The group keeps having a tie because Person A always picks rock, Person B always picks paper which beats rock, and Person C always picks scissors which beats paper, and is beaten by rock! This leads to a disagreement about which choice is best. They decide to use the pairwise comparison method determine the winner. Their preference rankings are given in the following table.

    VotersABC
    Rock (R)132
    Paper (P)213
    Scissors (S)321
    كشفت الإجابة

    Construct the comparison matrix:

    There is a tie! There is no winner.

    1. Suppose there is an election with five candidates—A, B, C, D, and E—and that Candidate C is a Condorcet candidate. How many points did Candidate C win?
    2. What is the greatest number of points that any one of the other candidates could win?
    3. Is it possible for Candidate C to lose or tie?

    كشفت الإجابة

    1. In any pairwise election with five candidates, each candidate must compete against four other candidates. It follows that the most points a single candidate can win is four points, which would occur if the candidate won every matchup. As a Condorcet candidate, Candidate C won all the pairwise matchups against Candidates A, B, D, and E, earning four points.
    2. The rest of the candidates lost to Candidate C. The most points a particular candidate could win if they won matchups with each of the other three candidates is three points.
    3. Since Candidate C has four points and the rest of the candidates have three points or less, Candidate C is the winner. Therefore, it is not possible for Candidate C to tie or lose.

  12. Suppose that Person A/B/C were just about to give up on their game of Rock, Paper, Scissors when they were joined by Person D who reminded them that their updated version, Rock, Paper, Scissors, Lizard, Spock was a far superior game with the added rules that Lizard eats Paper, Paper disproves Spock, Spock vaporizes Rock, Rock crushes Lizard, Lizard poisons Spock, Spock smashes Scissors, and Scissors decapitates Lizard.

    Person D encourages their friends to hold a new election. This time, for the sake of simplicity, the group decides to use approval voting to determine the best move in the game. The summary of approval ballots for Rock, Paper, Scissors, Lizard, Spock is given in the table below.

    VotersABCD
    RockYesNoNoNo
    PaperNoYesNoNo
    ScissorsNoNoYesNo
    LizardNoNoNoYes
    SpockYesYesYesYes
    كشفت الإجابة

    Count the number of approval votes for each candidate by counting the number of “Yes” votes in each row of the table.

    • Rock: 1
    • Paper: 1
    • Scissors: 1
    • Lizard: 1
    • Spock: 4

    Spock is the winning candidate, approved by four voters!

  13. The eight members of the Chionilis family—Annette, Rene, Seema, Titus, Galen, Elena, Max and Demitri—have another decision to make. Approval voting worked out nicely the last time. They are going to use it again, but this time, Annette, Rene, Seema, and Galen are feeling a little indecisive. They can't narrow their choice down to two. They will approve their three top choices, but the other family members will only approve two. These choices are reflected in the following table. Determine the restaurant that will be chosen.

    OptionsARSTGEMD
    Rainbow ChinaYesYesYesYesYesNoYesYes
    Dough Boys PizzaYesYesYesYesNoYesNoYes
    Taco CityYesNoYesNoYesYesNoNo
    Caribbean FlavorNoYesNoNoYesNoYesNo
    كشفت الإجابة

    Count the number of approval votes for each restaurant by counting the number of “Yes” votes in each row.

    • Rainbow China: 7
    • Dough Boys Pizza: 6
    • Taco City: 4
    • Caribbean Flavor: 3

    This time, Rainbow China won!

  14. Because the vote counts for George W. Bush and Al Gore differed by only 537 votes, many Democrats blamed Ralph Nader and the Green Party for their loss. Let’s consider how the election results might have differed if the approval voting method had been used.

    Use and the following assumptions to extrapolate the results of an approval method election:

    • 100 percent of Pat Buchanan supporters would approve George W. Bush.
    • 100 percent of Ralph Nader supporters would approve Al Gore.
    • 72 percent of Libertarians would approve George W. Bush.
    • 28 percent of Libertarians would approve Al Gore (as was roughly the known percentage at the time according to the Cato Institute).
    • 50 percent of the supporters of other candidates would approve George Bush while 50 percent would approve Al Gore.
    كشفت الإجابة

    Step 1: Create a summary of approval ballots based on the given assumptions. For the Libertarian candidate, 72 percent of 16,415 of the votes is \(0.72(16,415)=11,819\) and 28 percent is \(0.28(16,415)=4,596\). For the other candidates, 50 percent of the votes is \(0.50(6,680)=3,340\).

    Number of Votes2,912,790
    (G)    		2,912,253
    (A)    		97,488
    (R)    		17,484
    (B)    		11,819
    (72% H)    		4,596
    (28% H)    		3,340
    (50% O)    		3,340
    (50% O)
    (G) George W. BushYesNoNoYesYesNoNoYes
    (A) Al GoreNoYesYesNoNoYesYesNo
    (R) Ralph NaderNoNoYesNoNoNoNoNo
    (P) Pat BuchananNoNoNoYesNoNoNoNo
    (H) Harry BrownNoNoNoNoYesYesNoNo
    (O) 7 Other CandidatesNoNoNoNoNoNoYesYes

    Step 2: Count the number of approval votes for each candidate.

    • George W. Bush: \(2,912,790+17,484+11,819+3340=2,945,433\)
    • Al Gore: \(2,912,253+97,488+4,596+3,340=3,017,677\)
    • Ralph Nader: \(97,488\)
    • Pat Buchanan: \(17,484\)
    • Harry Brown: \(11,819+4,596=16,415\)
    • Other Candidates: \(6,680\)

    In this scenario, Al Gore is the winner.

  15. In the future, humans have explored distant solar systems and found three habitable planets which could be colonized. Since it will take all available resources to colonize one planet, humans must agree on the planet. Planet A has the most comfortable climate and most plentiful resources, but it is the farthest from Earth making travel to the planet a challenge. Planet B is half the distance but will require more resources to make comfortable. Planet C is the least suitable of the three and terraforming will be required, but it is close enough to make travel between Earth and Planet C possible on a more regular basis. The table below provides the voter preferences for the colonization of each planet.

    Percentage of Voters45%15%40%
    Planet A133
    Planet B212
    Planet C321

    If the entire population were able to vote, determine the winning planet using each of the methods listed below.

    1. Plurality
    2. Ranked-choice method
    3. Borda count
    كشفت الإجابة

    1. The plurality method only considers the top choice of each voter. By this system, Planet A has 45 percent of the vote, Planet B has 15 percent of the vote, and Planet C has 40 percent of the vote. Planet A wins.
    2. Using either instant runoff or a two-round system, Planet B with only 15 percent of the vote will be eliminated in the first round. In Round 2, the 15 percent that voted for Planet B would vote for their second choice, Planet C. This leaves Planet A with 45 percent and Planet C with 55 percent. Planet C has a majority and wins the election.
    3. To find the Borda score for each candidate, imagine there are exactly 100 voters. Then the summary of ranked ballots looks like:
      Out of 100 Voters451540
      Planet A133
      Planet B212
      Planet C321

      The Borda score for each candidate is as follows:
      Planet A: \((3-1)(45)+(3-3)(15)+(3-3)(40)=90\)
      Planet B: \((3-2)(45)+(3-1)(15)+(3-2)(40)=115\)
      Planet C: \((3-3)(45)+(3-2)(15)+(3-1)(40)=95\)
      Planet B wins.

Symbols used here

n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.
\forall,\ \exists
for all, there exists
Quantifiers: every x; at least one x.
\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow
not, and, or, implies, iff
Logical connectives.
\blacksquare\ \text{or}\ \square
end of proof (halmos)
Marks the point where the statement has been established.
a \equiv b \pmod n
congruent modulo n
n divides a − b; a and b have the same remainder.
O(n^2),\ \Theta,\ \Omega
big-O notation
Grows no faster than n² (up to a constant), for large n.
a \bmod n
remainder
What is left after dividing a by n.

How to: Voting Methods

  1. Apply plurality voting to determine a winner.
  2. Apply runoff voting to determine a winner.
  3. Apply ranked-choice voting to determine a winner.
  4. Apply Borda count voting to determine a winner.
  5. Apply pairwise comparison and Condorcet voting to determine a winner.
  6. Apply approval voting to determine a winner.
  7. Compare and contrast voting methods to identify flaws.
  8. Is there a winner based on the first round? Why or why not?

Questions people ask

What makes mathematics "discrete"?

It deals with separate, countable objects — integers, graphs, statements — rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.

How does a proof by induction work?

Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.

جرّب نفسك

Parts of this page are adapted from OpenStax Contemporary Mathematics (CC BY-NC-SA 4.0). Condensed and re-explained here; errors are ours.

أكثر في Discrete Math & Logic

Truth tablesSums and inductionProof by inductionAlgorithms and growth of functions