This is a two part lab. We will run a set of tests on your code after the Part 1 deadline, and we will share those test results to provide you feedback on your progress. We will grade your entire submission after the Part 2 deadline.
| Lab Component | Monday Lab Deadline | Tuesday Lab Deadline |
|---|---|---|
| Part 1: Q1-Q5 (Algorithms 1 & 2) | 10pm Feb 28 | 10pm Feb 29 |
| Part 2 Q6-Q9 (Algorithm 3) | 10pm Mar 6 | 10pm Mar 7 |
In this lab we will 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:
while loops when the stopping condition
is not predetermined.get_countDefine a function called get_count(elem, l) that takes
two arguments:
elem is a single string (i.e., type(elem)
is <class 'str'>)l is a list of strings (i.e.,
type(l) is <class 'list'>)The function get_count(elem, l) should
return the number of times that elem
appears in list l. Here are some examples of its usage:
>>> get_count('a', ['a', 'b', 'a', 'c', 'a'])
3
>>> get_count('b', ['a', 'b', 'a', 'c', 'a'])
1
>>> get_count('d', ['a', 'b', 'a', 'c', 'a'])
0Important: You should write your prelab solution
using pen and paper. This function will also be useful within the lab
itself, so after you are satisfied with your answer, you should add your
implementation to voting.py (we’ve already provided a place
for it in the file).
When a group of people need to collectively make a decision, they often do so through voting.
The most common and natural voting rule is the plurality rule, which determines a winner as follows: count the number of votes received by each candidate, and the candidate with the most votes wins.
While this seems like a pretty reasonable rule, plurality can lead to some undesirable results. For example, in the 2000 US Presidential Election, 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 |
|---|---|
| George Bush | 2,912,790 |
| Al Gore | 2,912,253 |
| Ralph Nader | 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. Another critique of the plurality rule is that 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 proposed. We will investigate some of these voting rules in this lab.
When considering alternatives to plurality voting, a natural question is, “What information should we elicit from the voters?” 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.
In anticipation of this lab, we ran a CS134-wide election as part of Homework 1, where each of you was asked to rank five Spring St. establishments (Spring St. Market, Tunnel City, the Log, Blue Mango, and Spice Root) as the place you’d most like to receive a gift card to. We are calling this election the Spring St Throwdown. As we implement each voting algorithm, we will determine which establishment won this throwdown under that algorithm’s rules.
To begin, clone this week’s repository in the usual manner.
Open the Terminal and cd into your cs134
directory:
cd cs134Clone 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.gitNavigate to your newly created lab04 subdirectory in the Terminal:
cd lab04Explore the starter code for this lab: you will be implementing
helpful functions for voting rules in voting.py and the
different voting rules themselves in election.py.
We’ll start with the simplest voting algorithm: plurality voting. Under this voting rule, the candidate with the most first-place votes is declared the winner. For example, consider a toy example of an election with three candidates and four voters. The tabular ballot data in this election might look something like this.
| Voter ID | Choice 1 | Choice 2 | Choice 3 |
|---|---|---|---|
| 0 | Aamir | Chris | Beth |
| 1 | Beth | Aamir | Chris |
| 2 | Chris | Beth | Aamir |
| 3 | Aamir | Beth | Chris |
To store this ballot data, we use the data type str for
candidate names. Each individual voter’s ballot is represented as a
single list of these names (as strings) in
order. To represent all ballots, we will use a
list of lists. Given this representation, the
ballots of the above toy example would then look like the following list
of lists:
ballots = [['Aamir', 'Chris', 'Beth'],
['Beth', 'Aamir', 'Chris'],
['Chris', 'Beth', 'Aamir'],
['Aamir', 'Beth', 'Chris']]To get started, we’ll write some essential helper functions for
manipulating these ballots. Since the helper functions are quite general
and useful for implementing many different voting algorithms, we’ll
separate them out into a file called voting.py.
Implement the function first_choice_votes(ballots) in
voting.py which takes a list of ballots (i.e., a list of
lists of strings) as its only argument, and returns a new list
of strings containing only the first choice of all voters.
Important: Your function should ignore ballots that do not contain any candidates (i.e. empty lists). For example:
>>> first_choice_votes([['Abe', 'Betsy'], ['Eve'], ['Fred', 'Gina'], []])
['Abe', 'Eve', 'Fred']We have defined some additional example ballots in the file
runtests.py, that you can use to test your function.
You may test this function in interactive Python as follows:
>>> from runtests import aamir_beth_chris_ballots
>>> from voting import first_choice_votes
>>> ballots = aamir_beth_chris_ballots()
>>> first_choice_votes(ballots)
['Aamir', 'Beth', 'Chris', 'Aamir']Alternatively, you can run the tests provided in
runtests.py by typing the following into the Terminal:
python3 runtests.py q1If you look at the code for runtests.py, you’ll see that
it is divided into four sections (each with its own section heading):
DATASETS, OUR PROVIDED TESTS,
YOUR EXTRA TESTS, and TEST RUNNER.
DATASETS defines a few examples of ballot data that
can be used to test your functions.
OUR PROVIDED TESTS is a collection of functions that
test the correctness of your code.
YOUR EXTRA TESTS is a place for you to create your
own additional tests, in order to increase your confidence that your
code is working correctly. You are required to create one extra
test for each question of this lab.
TEST RUNNER runs the tests. Specifically, when you
type:
python runtests.py qNin the Terminal (where N is the question number you want
to test), then it will run the tests for question
N.
Please add an additional test to the function
my_first_choice_votes_test in runtests.py (we
have provided an incomplete def statement in the
YOUR EXTRA TESTS section) that tests the correctness of
your implementation of first_choice_votes.
Implement the helper function get_candidates(ballots) in
voting.py which takes one argument: ballots
which is a list of lists of strings. It should return 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 interactive Python:
>>> from runtests import *
>>> from voting import *
>>> get_candidates([['Abe', 'Carmen'], ['Betsy'], ['Betsy', 'Gina'], []])
['Abe', 'Carmen', 'Betsy', 'Gina']
>>> get_candidates(aamir_beth_chris_ballots())
['Aamir', 'Chris', 'Beth']Alternatively, you can type the following into the Terminal:
python3 runtests.py q2Please add a helpful docstring to
(Update: We’ve already included a docstring for
you!). Add an additional test called
get_candidatesmy_get_candidates_test in runtests.py (we have
provided an incomplete def statement in the
YOUR EXTRA TESTS section) that tests the correctness of
your implementation of get_candidates.
Next, complete the function
most_votes(candidates, votes) in voting.py
that has two input parameters candidates and
votes. The first parameter candidates is
a list of strings that contains the names of all
candidates still in the election. The second parameter
votes is also a list of strings and
represents votes received by the candidates, e.g., votes
can be the first choice of all voters.
The function should return a new list of strings
which contains the names of the candidates that appear most frequently
in votes. Note that most_votes returns a list
of strings (rather than a single string) because multiple candidates
might be tied for the most votes.
Hint: You may find the function get_count
useful here (written as part of your prelab) to count the number of
times an element appears in a list.
You may test this function in interactive Python:
>>> from voting import most_votes
>>> most_votes(['Aamir', 'Beth', 'Chris'],['Aamir', 'Beth', 'Chris', 'Aamir'])
['Aamir']
>>> most_votes(['Abe', 'Betsy', 'Carmen','Dave', 'Eva', 'Frida'],['Abe', 'Abe', 'Betsy', 'Betsy', 'Carmen', 'Dave', 'Eva', 'Frida', 'Frida'])
['Abe', 'Betsy', 'Frida']
>>> most_votes([],[])
[]Alternatively, you can type the following into the Terminal:
python3 runtests.py q3Please add a helpful docstring to
(Update: We’ve already included a docstring for
you!). Add an additional test called
most_votes.my_most_votes_test in runtests.py (we have
provided an incomplete def statement in the
YOUR EXTRA TESTS section) that tests the correctness of
your implementation of most_votes.
Time to use your helper functions to implement plurality voting!
Complete the function plurality in
election.py. It takes an argument called
ballots, which is a list of ballots, i.e. a list of
lists of strings. It should return a list of
strings consisting of the name(s) of the candidate(s) who
received the most votes. In the case of ties, there may be more than one
winner!
You must use the functions that you just implemented in
voting.py. Do not use any for or while loops
for this function.
You may test this function in interactive Python:
>>> from runtests import *
>>> plurality(aamir_beth_chris_ballots())
['Aamir']
>>> plurality(ava_bob_cid_ballots())
['Ava']
>>> plurality(character_ballots())
['Scarlett OHara', 'Samwise Gamgee']Alternatively, you can type the following into the Terminal:
python3 runtests.py q4Add an additional test called
my_plurality_test in runtests.py (we have
provided an incomplete def statement in the
YOUR EXTRA TESTS section) that tests the correctness of
your implementation of plurality.
Spring Street Throwdown (Plurality). Now that you’ve implemented plurality voting, you can run a plurality-based election on the Spring Street Throwdown election ballots! Type the following into the Terminal:
python3 throwdown.pyto see if your favorite restaurant won (according to the plurality rule)!
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.
Consider for example the ballots defined in the
ava_bob_cid_ballots() function in runtests.py.
In this election, there are 21 voters and three candidates
(Ava, Bob, and Cid) and the
ballots of the voters are tallied in the table below.
| Rank Ordering | # Ballots with Rank Ordering |
|---|---|
| Ava, Cid, Bob | 7 |
| Bob, Cid, Ava | 7 |
| Cid, Bob, Ava | 6 |
| Ava, Bob, Cid | 1 |
In this example, 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 = 37Bob : 3·7 + 2·7 + 1·7 = 42Cid : 3·6 + 2·14 + 1·1 = 47and Cid would win the election (in contrast to
Ava is the plurality winner.)
We are now ready to implement Borda voting! Complete the function
borda in election.py. The borda
function takes as input the ballot data ballots as a
list of lists of strings, 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, every voter provides a complete ranking of all
candidates).
Hint 1: You may wish to write an additional helper function
borda_score that takes a candidate and the
ballot data ballots and returns an integer Borda score for
that candidate. Since borda_score 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:
>>> from runtests import ava_bob_cid_ballots
>>> from election import *
>>> borda_score('Ava', ava_bob_cid_ballots())
37
>>> borda_score('Bob', ava_bob_cid_ballots())
42
>>> borda_score('Cid', ava_bob_cid_ballots())
47Once you have completed the borda function, you may wish
to use these tests in interactive Python:
>>> from runtests import *
>>> borda(aamir_beth_chris_ballots())
['Aamir']
>>> borda(ava_bob_cid_ballots())
['Cid']
>>> borda(character_ballots())
['Harry Potter']Alternatively, you can type the following into the Terminal:
python3 runtests.py q5Add an additional test called
my_borda_test in runtests.py (we have provided
an incomplete def statement in the
YOUR EXTRA TESTS section) that tests the correctness of
your implementation.
Spring Street Throwdown (Borda). Now that you’ve implemented Borda voting, you can run a Borda election on the Spring Street Throwdown ballots! Type the following into the Terminal:
python3 throwdown.pyto see if your favorite restaurant won (according to the Borda rule)!
You are done with Part 1 of this lab. Remember to add, commit, and push your changes to the files you have edited by typing the following in the Terminal:
git commit -am "Done with Part 1"
git push 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-choice voting. Ranked-choice voting iteratively removes candidates from the ballots using the following algorithm:
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.
If there is no majority winner but all remaining candidates are tied (receive the same number of first-place votes), then the election is a tie. All tied candidates are winners and the election ends.
Otherwise, 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 example ballots defined in the
ava_bob_cid_ballots() function in runtests.py.
In this election, there are 21 voters and three candidates
(Ava, Bob, and Cid) and the
ballots of the voters are tallied in the table below.
| 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 ballot tallies
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 example! Ava is
the plurality winner, Cid is the Borda winner and
Bob is the ranked-choice winner. Voting rules matter.
To implement the ranked-choice voting algorithm, we’ll again begin by
writing several helper functions in voting.py.
Complete the function least_votes in
voting.py that has two input parameters
candidates and votes. The first parameter
candidates is a list of strings that
contains the names of all candidates still in the election. The second
parameter votes is also a list of strings
and represents votes received by the candidates, e.g.,
votes can be the first choice of all voters.
This function must return a new list of strings
containing the names of candidates from the list candidates
that appear the least number of times in the list votes. Be
careful! This function is a bit more subtle than
most_votes, because there is always a possibility that a
candidate receives zero first-place votes.
You may find the get_count function useful here as well
to count the number of times an element appears in a list.
You may test this function in interactive Python:
>>> from voting import least_votes
>>> least_votes(['Aamir', 'Beth', 'Chris'], ['Aamir', 'Beth', 'Chris', 'Aamir'])
['Beth', 'Chris']
>>> least_votes(['A', 'B', 'C', 'D', 'E', 'F'], ['A', 'A', 'B', 'B', 'C', 'D', 'E', 'F', 'F'])
['C', 'D', 'E']
>>> least_votes(['A', 'B', 'C'], ['A', 'B', 'B'])
['C']Alternatively, you can type the following into the Terminal:
python3 runtests.py q6Please add a helpful docstring to
(Update: We’ve already included a docstring for
you!) Add an additional test called
least_votes.my_least_votes_test in runtests.py (we have
provided an incomplete def statement in the
YOUR EXTRA TESTS section) that tests the correctness of
your implementation.
Most voting rules agree on the principle that if one candidate receives the majority of first place votes, that candidate should win the election. In real-world elections, however, a majority candidate might not always exist.
Implement the majority function in
voting.py, that has two input parameters
candidates and votes. The first parameter
candidates is a list of strings that
contains the names of all candidates still in the election. The second
parameter votes is also a list of strings
and represents votes received by the candidates, e.g.,
votes can be the first choice of all voters.
This function 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 as a string 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 for or while statement in
this function, although you may use other helper functions from
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.
You can test this function in interactive Python:
>>> from voting import majority
>>> majority(['Aamir', 'Beth', 'Chris'],['Aamir', 'Beth', 'Chris', 'Aamir'])
''
>>> majority(['Abe','Betsy','Carmen','Dave','Eva','Frida'],['Abe', 'Abe', 'Abe', 'Betsy', 'Carmen', 'Dave', 'Abe', 'Abe', 'Frida'])
'Abe'
>>> majority([],[])
''
>>> majority(['Aamir', 'Beth'],['Aamir', 'Beth', 'Beth', 'Aamir'])
''Alternatively, you can type the following into the Terminal:
python3 runtests.py q7Please add a helpful docstring to
(Update: We’ve already included a docstring for
you!) Add an additional test called
majority.my_majority_test in runtests.py (we have
provided an incomplete def statement in the
YOUR EXTRA TESTS section) that tests the correctness of
your implementation.
Next, implement the function eliminate_candidates in
voting.py that takes as input two lists (in order):
candidates, and,ballotsThe 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.)
You can test this function in interactive Python:
>>> from runtests import *
>>> eliminate_candidates(['Chris'], aamir_beth_chris_ballots())
[['Aamir', 'Beth'], ['Beth', 'Aamir'], ['Beth', 'Aamir'], ['Aamir', 'Beth']]
>>> eliminate_candidates(['Samwise Gamgee', 'Elizabeth Bennet'],character_ballots()[0:3])
[['Harry Potter', 'Scarlett OHara'], ['Harry Potter', 'Scarlett OHara'], ['Scarlett OHara', 'Harry Potter']]
>>> eliminate_candidates(['c', 'a'], [['c', 'a', 'd'] ,['c', 'd'], ['d', 'e', 'a'], ['a']])
[['d'], ['d'], ['d', 'e'], []]Observe (in the third test, above): if all candidates are eliminated from a ballot, you should still preserve the ballot as an empty list.
Alternatively, you can type the following into the Terminal:
python3 runtests.py q8Please add a helpful docstring to
(Update:
We’ve already included a docstring for you!) Add an
additional test called
eliminate_candidates.my_eliminate_candidates_test in runtests.py
(we have provided an incomplete def statement in the
YOUR EXTRA TESTS section) that tests the correctness of
your implementation.
We are now ready to implement ranked-choice voting! Complete the
function ranked_choice in election.py that
implements the ranked-choice voting rule. Given ballot data as a
list of lists of strings, the
ranked_choice 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 can test this function in interactive Python:
>>> from runtests import *
>>> ranked_choice(aamir_beth_chris_ballots())
['Aamir']
>>> ranked_choice(ava_bob_cid_ballots())
['Bob']
>>> ranked_choice(character_ballots())
['Scarlett OHara']Alternatively, you can type the following into the Terminal:
python3 runtests.py q9NOTE. If you are stuck in an infinite loop: Pressing Ctrl-C will exit out of the program and get you back to your prompt.
Add an additional test called
my_ranked_choice_test in runtests.py (we have
provided an incomplete def statement in the
YOUR EXTRA TESTS section) that tests the correctness of
your implementation.
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 check whether the
number of candidates with the least number first-choice votes is equal
to n.
You need a while loop to implement this algorithm.
The while loop must continue until the winner(s) are found. One way to
implement this check is to use a Boolean variable that
keeps track of whether a winner is found or not. Initially, this
variable is False as there is no winner. As your algorithm
proceeds, if a winner is found, you can set this variable to
True indicating that you are done, otherwise you keep
running the election.
Spring Street Throwdown (Ranked Choice). Now that you’ve implemented ranked-choice voting, you can run a ranked-choice election on the Spring Street Throwdown ballots! Type the following into the Terminal:
python3 throwdown.pyto see if your favorite restaurant won (according to ranked-choice 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.
Let’s revisit the example ballots defined in the
ava_bob_cid_ballots() function in runtests.py.
In this election, there are 21 voters and three candidates
(Ava, Bob, and Cid) and the
ballots of the voters are tallied in the table below.
| Ballot | Count |
|---|---|
| Ava, Cid, Bob | 7 |
| Bob, Cid, Ava | 7 |
| Cid, Bob, Ava | 6 |
| Ava, Bob, Cid | 1 |
In this election, 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.
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). If such a winner does not exist,
the function should return the empty string ''.
Do not modify function names or interpret
parameters differently from what is specified! 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!
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.
Do not forget to add, commit, and push your work as it progresses! Test your code often to simplify debugging.
As always, the file GradeSheet.txt in your
lab04 repository goes over the grading guidelines and
documents our expectations.