# Lab 4: Every Vote Counts!¶

Due Dates

This is a two part lab:

• Part 1 is due at 10pm on either October 5 or October 6.

• Part 2 is due at 10pm on either October 12 or October 13.

Objectives

In this lab we will learn how to use Python to read in preferential ballot data from sample elections and determine the winner by implementing several different voting algorithms. In doing so, you will gain experience with the following:

• Reading data from a csv file, parsing it using string methods, and storing it in appropriate Python data structures.

• Using lists, and lists of lists.

• Filtering lists through list comprehensions.

• Using convenient list methods: `append()`, `count()`, `extend()`, etc.

• Iterating using `while` loops when the stopping condition is not predetermined (needed for Part 2).

## Voting Rules Matter¶

When a group of people need to collectively make a decision or choose an alternative, they typically do so through voting.

The most common and natural voting rule is the plurality rule: count the number of votes received by each candidate and the candidate with the most number of votes wins. While this seems like a pretty reasonable rule, it can lead to some undesirable results. For example, in the 2000 US Presidential Elections, the race was very close and the outcome came down to the state of Florida where the final vote counts (ignoring other candidates) were:

Ballot

Count

Bush

2,912,790

Gore

2,912,253

97,488

There was only a ~500 vote difference between Bush and Gore, and it was generally assumed that most people who voted for Nader preferred Gore as their second choice. Thus, Nader was considered a “spoiler” candidate, since his presence flipped the results of the election. On the flip side, if the plurality rule is used, it can disincentivize truthful voting on the side of the voters: voters are not incentivized to vote for their top candidate if they believe that their candidate has a low likelihood of winning.

To alleviate these issues with plurality voting, many alternative voting rules have been studied and implemented. We will investigate some of these voting rules in this lab.

### Algorithm 1: Plurality Voting¶

To motivate the different schemes outlined below, we’ll use a running example in which 21 voters are choosing among three candidates, `Ava`, `Bob`, and `Cid`. Under plurality voting as described above, we may end up with the following results:

Ballot

Count

Ava

8

Bob

7

Cid

6

The clear winner by plurality voting is `Ava`.

### Algorithm 2: Borda Voting¶

When considering alternatives to plurality voting, a natural question is what information do we elicit from the voters. It is clear from the problems with plurality voting that eliciting just the first choice of candidates can be insufficient. Many voting rules thus ask voters to rank all candidates from their most to least preferred. We will look at several voting schemes based on rank ordering of candidates. These schemes are used not only in government elections, but also for picking winners in sports competitions, Eurovision, the Oscars, etc. If we ask our 21 voters to rank order our three candidates, we may now end up with the following results, in which, for example, seven voters ranked the candidates `Ava` then `Cid` then `Bob`.

Ballot

Count

Ava, Cid, Bob

7

Bob, Cid, Ava

7

Cid, Bob, Ava

6

Ava, Bob, Cid

1

Borda voting is a well known voting scheme based on rank orders. Variants of Borda are used in many elections, including those to elect members of the National Assembly in Slovenia, the winner of Eurovision’s Song Contest, and Major League Baseball’s MVP.

Suppose there are `n` candidates in an election that are rank ordered by each voter. Under Borda voting, a “total score” is computed for each candidate as follows. A candidate gets `n` points for each first-place vote, `n-1` points for each second place vote, and so on, down to `1` point for each last place vote. The Borda score of each candidate is the total points they receive, and the candidate(s) with the most points wins.

In the example above, candidate `Ava` received 8 first place votes and 13 last place votes; `Bob` received 7 first place votes, 7 second place votes, and 7 third place votes; and `Cid` received 6 first place votes, 14 second place votes, and 1 third place vote. Thus, the Borda algorithm would assign the following scores:

• `Ava` : `3·8 + 2·0  + 1·13 = 37 `

• `Bob` : `3·7 + 2·7  + 1·7  = 42 `

• `Cid` : `3·6 + 2·14 + 1·1  = 47`

and `Cid` would win the election (in contrast to `Ava` who was the plurality winner.)

### Algorithm 3: Ranked-Choice Voting¶

Recently, ranked-choice voting, or instant run-off, has gained popularity. Voters in Massachusetts were asked to consider switching to this scheme in a 2020 ballot measure (which was defeated), and New York conducted its 2021 mayoral election with ranked voting. The idea behind ranked-choice voting is to give voters more expressive power by taking into account how they rank each candidate (rather than just their top choice). The election iteratively removes candidates from the ballots using the following algorithm:

1. If there is a candidate who receives a majority (more than half) of the first-place votes, then this candidate wins and the election ends.

2. If there is no majority winner but all remaining candidates are tied, then the election is a tie.

3. The candidate with the fewest number of first-place votes is eliminated from the election, with candidates ranked below moving up to take their spot. If more than one candidate receives the lowest number of votes, then all such candidates are eliminated.

Let’s revisit the 21 ballots in our election for `Ava`, `Bob`, and `Cid`:

Ballot

Count

Ava, Cid, Bob

7

Bob, Cid, Ava

7

Cid, Bob, Ava

6

Ava, Bob, Cid

1

Starting with Step 1, we see that `Ava` has 8 first place votes, `Bob` has 7, and `Cid` has 6. `Ava` has the most first-place votes, but 8 votes is not a majority of 21 (since `8 < 21 // 2`). Thus there is no majority winner, and we move on to Step 2 in our algorithm. Since `Cid` has the fewest first-place votes, `Cid` is eliminated. After removing `Cid`, the updated ballots are:

Ballot

Count

Ava, Bob

8

Bob, Ava

13

Step 3 tells us that we must repeat the process, and return to Step 1. Now, `Bob` is a majority winner, since `13 > 21 // 2`, and thus `Bob` wins the election.

Notice that plurality, borda, and ranked-choice all return a different winner in this election!

### Algorithm 4: Condorcet Voting¶

A Condorcet winner is a candidate who wins a majority of the vote in head-to-head elections against each other candidate. In particular, we say candidate `Ava` beats `Bob` if a majority of voters rank `Ava` higher than `Bob`. Candidate `Ava` is a Condorcet winner if `Ava` beats every other candidate.

In our running example, `Cid` beats both `Ava` and `Bob` in a head-to-head race (with a score of 13-8 in both cases), and thus `Cid` is the Condorcet winner.

Note that a Condorcet winner may not always exist: it is possible that `Ava` defeats `Bob`, `Bob` defeats `Cid`, and `Cid` defeats `Ava` with no candidate beating every other. This is called the Condorcet Paradox. A similar cycle of “defeat” is embodied in the rules of rocks-paper-scissors (or roshambo), and even in the ecology of side-blotched lizards.

## Getting Started¶

Before you begin, clone this week’s repository in the usual manner.

1. Open the Terminal and `cd` into your cs134 directory:

```cd cs134
```
2. Clone your repository from https://evolene.cs.williams.edu using the following command, where you should replace `23xyz3` with your CS username.

```git clone https://evolene.cs.williams.edu/cs134-labs/23xyz3/lab04.git
```
3. Navigate to your newly created lab04 subdirectory in the Terminal:

```cd lab04
```
4. Explore the starter code for this lab: you will be implementing helpful methods for voting rules in `voting.py` and the different voting rules themselves in `election.py`.

## Part 1. Plurality and Borda Voting¶

In Part 1, we’ll implement our first two voting algorithms, plurality and Borda. To get started, we’ll write some essential helper functions for manipulating ballots. Since those are quite general functions and useful for implementing many different voting algorithms, we’ll separate them out into a voting module defined in the `voting.py` file.

Implement the function `readBallot()` in `voting.py` which takes a path to a csv file (comma-separated values file) as an input string, e.g. `'data/simple.csv'`, and returns a list of lists of strings, where each “small” interior list is a single ballot containing candidate names (strings) ordered from most preferred to least preferred. For example, the csv file `simple.csv` in subdirectory `data` contains the following four voter preferences (one per line):

```Aamir,Chris,Beth
Beth,Aamir,Chris
Chris,Beth,Aamir
Aamir,Beth,Chris
```

Invoking `readBallot('data/simple.csv')` should return a list of four lists of strings, where each interior list represents the complete preference of a single voter.

You may test this function in the following ways:

```>>> readBallot('data/simple.csv')
[['Aamir', 'Chris', 'Beth'], ['Beth', 'Aamir', 'Chris'], ['Chris', 'Beth', 'Aamir'], ['Aamir', 'Beth', 'Chris']]
'Scarlett OHara'
'Cid'
```

Please add a meaningful docstring to `readBallot()`, and include at least two new doctests to test the function, perhaps including those above.

### 1.2. Collect the first choice votes¶

Implement the function `firstChoiceVotes()` in `voting.py` which takes a list of lists of strings (e.g., those returned by `readBallot()`) as input, and then creates and returns a new list of strings containing only the first choice of all voters. This is a good place to use a list comprehension.

You may test this function in the following ways:

```>>> firstChoiceVotes(readBallot('data/simple.csv'))
['Aamir', 'Beth', 'Chris', 'Aamir']
>>> firstChoiceVotes([['Abe', 'Betsy'], ['Eve'], ['Fred', 'Gina'], []])
['Abe', 'Eve', 'Fred']
```

Please add a meaningful docstring to `firstChoice()`, and include at least two new doctests to test the function.

### 1.3. Find the candidate with the most votes in a list of votes¶

Next, complete the function `mostVotes()` in `voting.py` that takes as input a list of strings of `votes` (e.g., the first choice of all voters as returned by `firstChoice()`), and returns a list of strings of names that appear the most number of times in `votes`.

You may test this function in the following ways:

```>>> mostVotes(['Aamir', 'Beth', 'Chris', 'Aamir'])
['Aamir']
>>> mostVotes(['Abe', 'Abe', 'Betsy', 'Betsy', 'Carmen', 'Dave', 'Eva', 'Frida', 'Frida'])
['Abe', 'Betsy', 'Frida']
[]
```

Hint: You may find the list method `.count()` useful here to count the number of times an element appears in a list.

Please add a meaningful docstring to `mostVotes()`, and include at least two new doctests to test the function.

### 1.4. Implement Plurality Voting¶

It’s now time to complete the function `plurality()` in `election.py`. Refer back to Algorithm 1: Plurality Voting for the rules of this algorithm. It takes as input the ballot data `ballots` as a list of lists of strings (in the form returned by `readBallot()`), and returns a list of strings consisting of the name(s) of the candidate(s) who receives the most number of votes. (Note: In the case of ties, there may be more than one winner!)

In the example above (from `data/example.csv`), candidate `Ava` would win the plurality election with `8` first place votes.

You must use the functions provided in the voting module. Do not use any loops.

You may test this function in the following ways:

```>>> plurality(readBallot('data/simple.csv'))
['Aamir']
['Ava']
['Scarlett OHara', 'Samwise Gamgee']
```

### 1.5. Collect the names of all candidates appearing in a list of ballots¶

Implement the function `candidates()` in `voting.py` which takes a list of lists of strings (e.g., those returned by `readBallot()`) as input, and then creates and returns a new list of strings containing the names of all candidates that appear on any of the ballots, in the order that they appear, i.e., candidates appearing on the first ballot should appear before candidates appearing only in subsequent ballots.

You may test this function in the following ways:

```>>> candidates(readBallot('data/simple.csv'))
['Aamir', 'Chris', 'Beth']
>>> candidates([['Abe', 'Carmen'], ['Betsy'], ['Betsy', 'Gina'], []])
['Abe', 'Carmen', 'Betsy', 'Gina']
```

Please add a meaningful docstring to `candidates()`, and include at least two new doctests to test the function.

### 1.6. Implement Borda Voting¶

Complete the function `borda()` in `election.py`. Refer back to Algorithm 2: Borda Voting for the rules of this algorithm. The `borda()` function takes as input the ballot data `ballots` as a list of lists of strings (in the form returned by `readBallot()`), computes the Borda score of each candidate, and returns a list of strings of the winner(s): that is, the candidates(s) who receive the maximum Borda score. You may assume that each list in `ballots` includes all candidates (that is, there are no “undervotes”: every voter provides a complete ranking of all candidates). You may use loops this time, and you may also wish to write a helper function `bordaScore()` that takes a `candidate` and the ballot data `ballots` and returns an integer Borda score for that candidate. Since `bordaScore()` is specific to this one algorithm, it is better placed in `election.py` than with the general functions in `voting.py`. If you implement this function, you may test it with the following doctests:

```>>> bordaScore('Ava',readBallot('data/example.csv'))
37
42
47
```

Once you have completed the `borda()` function, you may wish to use these tests:

```>>> borda(readBallot('data/simple.csv'))
['Aamir']
['Cid']
['Harry Potter']
```

### 1.7 Running Elections¶

In Homework 1, you may recall that we asked you to vote for your favorite ice cream flavor. Now is the time to elect a winning flavor through each of the voting methods! Uncomment the print statements for Part 1 provided in the `if __name__ == '__main__':` block at the end of `election.py` and see which flavor wins for the different voting rules.

(Disclaimer: Well, okay, so apparently you all like “Cookies and Cream” so much that it was the hands-down winner for all voting algorithms… To make life a little more interesting, we’ll “disqualify” “Cookies and Cream” and remove that flavor from the ballots. You should see different winners as a result. There is code in the `if __name__ == '__main__':` block to handle this. But you have to complete Part 2, first!)

## Part 2. Ranked-Choice and Condorcet Voting¶

In Part 2, we’ll again write several helper functions in `voting.py` and also the Ranked Order voting algorithm. We’ll leave Condorcet voting as extra credit, but give it a try if you like!

You may wish to comment out all of the print statements in the `if __name__ == '__main__':` block at the end of `election.py` until after you have completed the rank-order voting.

### 2.1. Find the candidates with the least first place votes¶

Complete the function `leastVotes()` in `voting.py` that takes as input a list of strings of `votes` (e.g., the first choice of all voters), and returns a list of the names appearing the least number of times in the list `votes`. Be careful! This function is a bit more subtle than `mostVotes()`, because there is always a possibility that there will be candidates getting no votes. To account for this scenario, we’ll pass a second list of strings of `candidates` that includes the names of all candidates that could have received votes.

You may test these functions in the following ways:

```>>> leastVotes(['Aamir', 'Beth', 'Chris', 'Aamir'], ['Aamir', 'Beth', 'Chris'])
['Beth', 'Chris']
>>> leastVotes(['Abe', 'Abe', 'Betsy', 'Betsy', 'Carmen', 'Dave', 'Eva', 'Frida', 'Frida'], ['Abe', 'Betsy', 'Carmen', 'Dave', 'Eva', 'Frida'])
['Carmen', 'Dave', 'Eva']
>>> leastVotes(['Abe', 'Betsy', 'Betsy'], ['Abe', 'Betsy', 'Carmen'])
['Carmen']
```

As in `mostVotes()`, you may find the list method `.count()` useful here to count the number of times an element appears in a list.

Please add a meaningful docstring to `leastVotes()`, and include at least two new doctests.

### 2.2. Determine the majority winner¶

Most voting rules agree on the principle that if one candidate receives the majority of first place votes, that candidate should win the election. Often times in real elections with popular choices, however, there is no majority candidate.

Implement the `majority()` function in `voting.py`, that takes as input a list of strings `votes` (e.g., the first-choice of all voters), checks if there is a single candidate who wins the majority (i.e., more than half) of the votes. It returns the name of that candidate if such a candidate exists. Otherwise, the function returns `''`, the empty string. More precisely, a candidate is a majority winner if and only if they receive more than `n//2` first place votes, where `n` is the total number of votes. You may not use a loop in this function, although you may use other functions in your voting module.

Also, you may assume that all candidate names are at least one letter long when writing `majority` and the rest of the functions in Part 2. That is, you do not need to worry about `''` appearing in the list of votes passed to `majority`. (What could go wrong if you had to consider that case?)

You may test this function in the following ways:

```>>> majority(['Aamir', 'Beth', 'Chris', 'Aamir'])
''
>>> majority(['Abe', 'Abe', 'Abe', 'Betsy', 'Carmen', 'Dave', 'Abe', 'Abe', 'Frida'])
'Abe'
>>> majority([])
''
>>> majority(['Aamir', 'Beth', 'Beth', 'Aamir'])
''
```

Please add a meaningful docstring to `majority()`, and include at least two new doctests to test the function.

### 2.3. Eliminate candidates¶

Finally, implement a function `eliminateCandidates()` in `voting.py` that takes as input two lists (in order):

• a list of strings of candidates to be eliminated called `candidates`, and,

• ballot data as a list of lists of strings called `ballots` (in the form returned by `readBallots()`).

The function must eliminate any votes to candidates in `candidates` and return the updated ballots as a new list of lists of strings. For example, consider a voter’s preference list `['Aamir', 'Chris', 'Beth']`; if `Chris` is eliminated, the new preference list must be `['Aamir', 'Beth']` (that is, `Beth` moves up to second place to take the spot vacated by `Chris`.) This is another good place to use a list comprehension, and since we need to return a new list you should avoid using `remove()`.

You may test this function in the following ways:

```>>> eliminateCandidates(['Chris'], readBallot('data/simple.csv'))
[['Aamir', 'Beth'], ['Beth', 'Aamir'], ['Beth', 'Aamir'], ['Aamir', 'Beth']]
[['Harry Potter', 'Scarlett OHara'], ['Harry Potter', 'Scarlett OHara'], ['Scarlett OHara', 'Harry Potter']]
```

Please add a meaningful docstring to `eliminateCandidates()`, and include at least two new doctests to test the function.

### 2.4. Implement Ranked-Choice Voting¶

Complete the function `rankedChoice()` in `election.py` that implements the ranked-choice voting rule. Refer back to Algorithm 3: Ranked-Choice Voting for the rules of this algorithm. Given ballot data as list of lists of strings, the `rankedChoice()` function should return a list of strings of candidate(s) that win the election based on ranked-choice voting. Use the helper functions implemented in `voting.py`.

You may test this function in the following ways:

```>>> rankedChoice(readBallot('data/simple.csv'))
['Aamir']
['Bob']
['Scarlett OHara']
```

Hints:

• Sketch out your algorithm before you begin to implement it. Pay very close attention to the three steps we outlined, and think about how to use your helper functions in `voting.py` in each step. You may wish to go through a few small examples by hand to ensure you understand how the algorithm works.

• You will need to determine whether all remaining candidates are in a tie in Step 2 of the algorithm. There are many ways to do this. Suppose there are a total of `n` candidates left in the ballots. One way to test if they are all tied is to test whether the number of candidates having the least number first-choice votes is equal to `n`.

• You will need to write a `while` loop to implement this algorithm. Most of the time, we can readily determine when the loop should exit and write a reasonable test at the top of the loop. In this case, though, the proper test to perform at the top of the loop is not very intuitive to construct, so an alternative is to use a `while True:` loop and have the body of the loop `return` the answer as soon as it is known:

```while True:
# If there is a majority winner, return a list containing that candidate
...
# If all remaining candidates are tied, return a list containing those candidates
...
# Elminate the candidates with the least first-choice votes.
...
```

### 2.5. (Extra Credit) Find the Condorcet winner¶

Write a function `condorcet()` in `election.py` that takes ballot data as a list of lists of strings, and returns the name as a string of the Condorcet winner (if a Condorcet winner exists), else the function should return an empty string. Refer back to Algorithm 4: Condorcet Voting for the rules of this algorithm.

### 2.6. Running Elections¶

Uncomment the remaining print statements for Part 2 in the `if __name__ == '__main__':` block at the end of `election.py`, and see how your new voting algorithms compare to the ones from Part 1. You can also rerun your Part 1 algorithms after eliminating Cookies and Cream.

1. Part 1 of this lab is due at the usual time in the first week of this two-week lab. Part 2 is due at the usual time in the second week.

2. Use the helper functions defined in `voting.py` whenever possible. One of the main advantages of functions is enabling code reuse, and avoiding redundancy.

3. This lab assignment provides several opportunities to use list comprehensions: to get some practice with them, you must write at least one list comprehension in either `voting.py` or `election.py`. We have noted a few obvious places to try incorporating a list comprehension in this handout.

4. Do not modify function names or interpret parameters differently! Make sure your functions follow the expected behavior in terms of type of input and output: if they return lists, their default return `type` must always be `list`. A function’s documentation serves, in some way, as a contract between you and your users. Deviating from this contract makes it hard for potential users to adopt your implementation!

5. Functionality and programming style are important, just as both the content and the writing style are important when writing an essay. Make sure your variables are named well, and your use of comments, white space, and line breaks promote readability. We expect to see code that makes your logic as clear and easy to follow as possible. Python Style Guide is available on the course website to help you with stylistic decisions.

6. Do not forget to add, commit, and push your work as it progresses! Test your code often to simplify debugging.

7. As always, the file `GradeSheet.txt` in your `lab04` repository goes over the grading guidelines and documents our expectations.