CS50x - Problem Set 3 - Tideman.
elections, voters, ballots
Problem to solve
You already know about plurality elections, which follow a very simple algorithm for determining the winner of an election: every voter gets one vote, and the candidate with the most votes wins.
There’s another kind of voting system known as a ranked-choice voting system. In a ranked-choice system, voters can vote for more than one candidate. Instead of just voting for their top choice, they can rank the candidates in order of preference.
The Tideman voting method (also known as “ranked pairs”) is a ranked-choice voting method that’s guaranteed to produce the Condorcet winner - the person who would have won any head-to-head matchup against another candidate - of the election if one exists. In a file called tideman.c in a folder called tideman, create a program to simulate an election by the Tideman voting method.
The Tideman voting system works by making a “graph” of candidates, where an arrow (i.e. edge) from candidate A to candidate B indicates that candidate A wins against candidate B in a head-to-head matchup.
Looking at one of these graphs, the Tideman method says the winner of the election should be the “source” of the graph (i.e. the candidate that has no arrow pointing at them). It's possible however that there is no Condorcet winner because the graph creates an endless loop.
To prevent loops, the algorithm locks in the strongest wins first, since those are arguably the most significant. In particular, the Tideman algorithm specifies that matchup edges should be “locked in” to the graph one at a time, based on the “strength” of the victory (the more people who prefer a candidate over their opponent, the stronger the victory). So long as the edge can be locked into the graph without creating a cycle, the edge is added; otherwise, the edge is ignored.
Put more formally, the Tideman voting method consists of three parts:
- Tally: Once all of the voters have indicated all of their preferences, determine, for each pair of candidates, who the preferred candidate is and by what margin they are preferred.
- Sort: Sort the pairs of candidates in decreasing order of strength of victory, where strength of victory is defined to be the number of voters who prefer the preferred candidate.
- Lock: Starting with the strongest pair, go through the pairs of candidates in order and “lock in” each pair to the candidate graph, so long as locking in that pair does not create a cycle in the graph.
Once the graph is complete, the source of the graph (the one with no edges pointing towards it) is the winner!
For this problem, the main function is already written for us and is downloaded from here. All we have to do is implement the following functions:
- bool vote(int rank, string name, int ranks[]);
- void record_preferences(int ranks[]);
- void add_pairs(void);
- void sort_pairs(void);
- void lock_pairs(void);
- void print_winner(void);
Let's start with the first function.
bool vote(int rank, string name, int ranks[ ])
We see here that the function will return a bool value, so it will return true if the vote is valid (and record the vote in the ranks array), and return false if the vote is invalid - the name has already been registered or isn't one of the candidates. As for the ranks[ ] array, the main function will ask each voter for a name in order of preference. Our vote function will look for the name in the list of candidates, if it finds a match, it will record the rank and return true, if it doesn't record a rank, then we can return false. Let's write some pseudocode:
Loop through each candidate in our array of candidates
If the given name matches the candidates name
Record index of candidate in the rank array
Return true
Return false
Now let's see the code:
bool vote(int rank, string name, int ranks[])
{
// Loop through candidates
for (int i = 0; i < candidate_count; i++)
{
// If name matches candidate's name, store rank and return true
if (strcmp(name, candidates[i]) == 0)
{
ranks[rank] = i;
return true
}
}
// If name is not in list of candidates, return false
return false
}
Let's move on to the next function.
void record_preferences(int ranks[ ])
Now, preferences uses a matrix - a 2d array - to record how many voters prefer one candidate over another. It's initialized as a global variable like this:
// preferences[i][j] is number of voters who prefer i over j
int preferences[MAX][MAX];
Here's a little graphic to visualize how it works:
A B C
A [ 0, 2, 3 ]
B [ 1, 0, 4 ]
C [ 0, 1, 0 ]
In the matrix above, the candidate on the row to the left will be the winner, the candidate on the column at the top is the loser, and the number it corresponds to is how many voters preferred the left candidate. So, [A][B] = 2 (highlighted in green) means that 2 voters preferred A over B.
This function will need a double loop to go through the matrix and add 1 to the count for each voter's ranks[ ] array, the pseudocode looks like this:
Loop through preferred candidates
Loop through losing candidates
Add 1 to preferred candidate's spot in preferences[i][j]
Return
And here's the code:
void record_preferences(int ranks[ ])
{
// Loop through preferred candidates
for (int i = 0; i < candidate_count; i++)
{
// Loop through the next index of ranks
for (int j = i + 1; j < candidate_count; j++)
{
preferences[ranks[i]][ranks[j]]++;
}
}
return;
}
You can see that it adds 1 to the preferences matrix where i is the lower rank, and thus the preferred candidate. Let's move on to the next function:
void add_pairs(void)
This blog is getting quite long and complicated and I'm not even half way done! So I'm just going to put my next 2 functions with a brief explanation. The add_pairs function loops through the preferrences array and stores the winner and loser of each pair, as well as keeping track of how many pairs we have (so we can use them later):
void add_pairs(void)
{
// Loop through entire preferrences array
for (int i = 0; i < candidate_count; i++)
{
for (int j = 0; j < candidate_count; j++)
{
// Store each pair's winner and loser and iterate pair_count
if (preferences[i][j] > preferences[j][i])
{
pairs[pair_count].winner = i;
pairs[pair_count].loser = j;
pair_count++;
}
}
}
return
}
void sort_pairs(void)
This function sorts the pairs in decreasing order by the "strength" of their victory. I realized after going over it, my bubble sort algorithm probably isn't the most efficient, but I wanted to experiment with different types of loops at the time. Here is the code:
void sort_pairs(void)
{
// Reverse bubble sort, weakest pair will bubble to the top
int swap_count = 0;
do
{
// Initialize an empty pair to swap if needed
pair swap_pair;
// Reset swap_count
swap_count = 0;
// Loop through each pair
for (int i = 0; i < pair_count - 1; i++)
{
// Look at each adjacent pair, if number of voters is less, swap places
if (preferences[pairs[i].winner][pairs[i].loser] <
preferences[pairs[i + 1].winner][pairs[i + 1].loser])
{
swap_pair = pairs[i];
pairs[i] = pairs[i + 1];
pairs[i + 1] = swap_pair;
swap_count++;
}
}
}
while (swap_count != 0);
return;
}
void lock_pairs(void)
Now the fun part. We need to lock the pairs in order, but we also need to check if we're going to create a cycle or loop before we lock it in, to do this I'll make a helper function above the lock_pairs function, this new function creates_cycle will recursively check if locking in a pair will create a cycle. Let's start with the main one though. This one is quite simple, it will go through all the pairs and if the pair won't create a cycle, it'll lock in the pair in another 2d matrix: bool locked[MAX][MAX]. Here's the code:
void lock_pairs(void)
{
// Loop through pairs and lock edges
for (int i = 0; i < pair_count; i++)
{
if (!creates_cycle(pairs[i].winner, pairs[i].loser))
{
locked[pairs[i].winner][pairs[i].loser] = true;
}
}
return;
}
bool creates_cycle(int winner, int loser)
Now for the recursive function. I'd like to break this one down a bit, since I still feel like I fully understand what's going on with most recursive functions. In this function, we give it the index of the winning candidate, and the index of the losing candidate. Then we want to check all the possible edges to see if we're creating a cycle in the graph.
Every recursive function has a base case, and a recursive case. The base case marks the very end of the loop, where we terminate the function. The recursive case calls the function again with modified parameters, thus creating a loop until you reach the base case.
In this function, the base case will be when we've gone through all the possible candidates and we've looped back to where we started.
The recursive case will loop through all the candidates and check if the given loser has an edge over a candidate, if the loser does have an edge, it will recursively check again if there's an edge where the new loser points back to the original winner. With each call, it checks if the loser of any pair can eventually point back to the winner, if it does, it will return true because a cycle was created. Here's the code:
bool creates_cycle(int winner, int loser)
{
// Base case: loser points back to winner, creating a cycle
if (loser == winner)
{
return true;
}
// Recursive case: check if loser has an edge, and if the new loser points back to winner
for (int i = 0; i < candidate_count; i++)
{
if (locked[loser][i])
{
if (creates_cycle(winner, i))
{
return true;
}
}
}
// If no cycle is found, return false
return false;
}
Putting these two functions together, lock_pairs and creates_cycle, really does look quite elegant - after I finished them of course. It took quite a long time to figure out the logic and lots of trial and error for each of these functions.
Of course, there's one function left: print_winner. And it's not without its complications, but I'm quite tired and this blog is already running long, so I think I'll have to leave you hanging here in suspense. Until next time!
