How do the Coombs, Bucklin, Plurality with Runoff, and Schulze Voting Methods Respond to Force Truncated Ballots in a Realistic Environment?
Advisor: Mr. Ryan Merritt
Internship Location: University of Maryland (remote)
Onsite Mentor: Professor Eric Pacuit
Elections employ various voting systems to determine winners based on voters' preferences. However, many recent ranked-choice elections have forced voters to truncate their ballots by only ranking a subset of the candidates. This study analyzes how forced ballot truncation affects the Bucklin, Coombs, plurality with runoff, and Schulze voting systems' abilities to output their true winning sets. This study also accounts for forced ballot truncation within the context of more realistic circumstances as compared to previous research on these voting methods including accounting for voters not completely filling out ballots and voters ordering their candidates who are aligned with their preferences instead of a random order. Using computer simulations, 840,000 sets of ballots were generated with a spatial model using different numbers of candidates, voters, and dimensions. The true winning set was determined for each system using complete preferences, then compared to winning sets derived from repeatedly truncated preferences within the same preference profile. Throughout the project, I will be working with Eric Pacuit, a professor at the University of Maryland, to consult on the design of the simulations as well as the process of analyzing the data. This project will result in an academic paper that will exhibit findings that provide insights into how forced ballot truncation impacts voting systems in realistic environments, hopefully aiding election designers in their work.
Project Blog
Week 0: Introduction
Hello readers! My name is Jonah Stein and I have been a student at BASIS Independent Brooklyn since its founding in 2014. For my senior project, I will be focusing on the realm of voting theory. The concept of coming to a “fair” decision among a group of voters with diverse opinions may seem relatively straight forward, but it is actually very complex. The most commonly employed method to make decisions is that of plurality, where the choice that the most voters prefer is the one that is chosen. However, although simple, there are many flaws in this method such as ignoring people’s second, third, and fourth preferences. To amend some of these issues, there have been many new voting systems proposed that involve voters ranking their choices, or in the most common case, candidates, in order of preference. In many of the elections that have employed these preferential voting systems, the election organizers have often truncated the ballots - limiting the number of candidates that each voter can rank. This is referred to as forced ballot truncation. There are no clear reasons as to why election designers force truncate ballots, but, regardless, it would be important for them to know the potential effects that it could have on the results. This senior project seeks to outline those effects by exploring how 4 preferential voting systems, with diverse decision mechanisms, respond to forced ballot truncation. To do this, I will be simulating roughly 100,000 elections and analyzing how the results are affected by removing the tail end of preferences, effectively accounting for forced ballot truncation. I will also be working with Eric Pacuit, a professor at the University of Maryland, to design the simulation and deepen my analysis of the results to come to stronger conclusions. At the end of the project, I will hopefully contribute helpful data points to the field, with my findings detailed in a research paper. If you are interested in learning more about my project, click here.
Week 1: Creating a Probability Model
Hello again, and welcome back to my blog. During the first week of my project, I wanted to start out on designing a probability model to mimic the voting patterns within realistic elections. One of the key aspects of my project is to study the effects of forced ballot truncation in realistic scenarios, and one of the main ways to do so is by accounting for the rate at which voters rank varying numbers of candidates (ie. How many voters rank only 1 candidate vs all of them). The probability model would then come into play while simulating preference profiles, truncating each ballot by varying lengths. Initially, I had planned on obtaining this probability model from previous research on the topic, however, after reading through many journal articles, I came to the conclusion that I would have to craft my own. So, I downloaded all the publicly available data from political elections that had used preferential ballots from the data library: preflib.org. In total, there were 309 elections to be analyzed. Then I created a program to aggregate the data into a spreadsheet that tracks the number of candidates and voters in each election. Lastly, the final field in the sheet stores the number of voters who ranked each number of candidates (ie. 10 voters ranked 1 candidate, 20 ranked 2, 100 ranked all 3).
In the coming weeks I will use this unpackaged data to construct the probability model, which will then be implemented within the simulation of preference profiles. There are a few different ways that I can use the data to create probability models, so I will need to consult with my on-site advisor to determine which method to use. That’s all for this week. Thanks for reading!
Week 2: Finishing the Probability Model
Hello, and welcome back to my blog where I will be detailing the progress I made on my senior project. Last week, I discussed how I had run into a minor roadblock, requiring me to create my own probability model for random ballot truncation. I had also mentioned that there were a few ways that I could’ve constructed the model, which I will detail below:
The first method that I had in mind was using the ballot data from every election I downloaded to calculate how often voters ranked each proportion of candidates(ie. 20% of voters ranked 50% of the candidates). This method was appealing because it would allow me to create a single, all-encompassing model based on the most data possible. However, it made a major assumption that made me uncomfortable. In an election with 4 candidates, it would be much more common for a voter to rank all the candidates versus in an election with 12 candidates. This would result in skewed data, which would affect the strength of the results.
To address this concern, the second option was to create separate probability models for elections with different numbers of candidates(ie. An election with 4 candidates will have a different model than one with 6 candidates). The one downside of this method is that each probability model will be based on less empirical data than the universal one that would’ve been produced from the first option.
After considering both of these methods, I decided to go with the second option. I figured that even though the models would use less data, they would still be based on enough to mimic realistic voter actions. Additionally, previous research that I had read designed their probability models for elections with a specific number of candidates. The probability models are now finished for every candidate length available, and I will choose . Next week, I will be working on developing the rest of the aspects required for the simulation. Stay tuned!
Week 3: The Voting Methods
Hello everyone, and welcome back to my blog. This week I started working on more code that will contribute to the simulation. More specifically, I focused on the voting systems themselves.
A voting system is, simply, a method used to choose a winner in an election while taking everyone’s opinion into account. There are many different voting systems that exist, and each one has its unique set of properties. The four voting systems (Coombs, Bucklin, plurality with runoff, and Schulze) that I chose were picked due to their differing and unique mechanisms. Coombs first checks whether there is a candidate with a majority of first preference votes, if there is, that candidate is declared the winner. Otherwise, the candidate with the highest number of least placed votes is eliminated, and the ballots that ranked the eliminated candidate first are reallocated to their second-preference candidate. The cycle then repeats, eliminating candidates until a candidate receives a majority of the ballots.
Bucklin, similarly, requires its winner to reach a majority of votes. It tallies up the first round of preferences, and if a candidate achieves a majority, it is declared the winner. If no candidate has a majority, the number of times each candidate was preferred second gets added to their first place tallies. If any candidate’s sum of first and second place votes is greater than 50% of the total ballots in the election, then they are the winner. This addition goes on until a candidate reaches a majority of votes, or every preference on every ballot is tallied, at which point the candidate with the plurality of votes wins.
Plurality with runoff first determines the two candidates with the most first-place rankings. If neither have a majority, then all the other candidates are eliminated and there is a runoff election between the two leading candidates using the secondary preferences on the ballots that most preferred the eliminated candidates.
Lastly, Schulze is the only election that is condorcet consistent, which means that its winner will always be the candidate that is preferred over every other candidate in a head-to-head election. It uses the margins between candidates to decide its winners.
Most of these voting systems, as well as the other aspects of the simulation, are taken from pref-voting, a python package developed by my onsite advisor Eric Pacuit. However, many of the functions had to be adapted for the simulation, which is what I spent the majority of this week doing. The adaptations aren’t fully complete yet, and I need to make a few decisions as to how they’ll work with truncated ballots, given that a few of the voting systems weren’t designed to work with incomplete preferences. But that’s next week’s task!
Week 4: Adapting the Voting Methods
Welcome back to my blog! This week, I finalized adapting the voting systems that I described in last week’s blog. As I said, I had to make a few assumptions when adapting the voting systems to the needs of my simulation, so in this blog, I’ll be detailing the decisions I made.
The Schulze and plurality with runoff voting methods were already designed to work with truncated ballots, so luckily I didn’t have to modify either of them. I did, however, have to modify Bucklin and Coombs.
Bucklin, as explained last week, decides its winner by continuously adding first, then second, then third preferences, and so on, until a candidate reaches a majority(>50%) of votes. When working with truncated ballots, it’s possible that a majority won’t be reached after tallying up every preference, so I needed to slightly change the decision mechanism. My Bucklin implementation follows the voting system’s normal behavior unless every ballot’s preference has been tallied, at which point, the candidates that have a plurality of votes(the most votes, but not necessarily >50%) win.
When adapting Coombs, I had to make many more assumptions. As you may recall, Coombs checks for a candidate with a majority of votes, but then defaults to eliminating the candidates with the highest number of last place votes. With truncated ballots, however, does one consider the last ranked candidate on the ballot the last place candidate, or are the candidates that were ignored considered last place? Voting theorists have differing stances on the topics, but after consulting various opinions and considering my simulation, I decided that the candidates that were ignored, or not ranked on the ballot, were considered to be last place. After deciding that, the rest of the voting system worked as usual.
The voting systems are now all designed to work with truncated ballots, meaning that I can move onto the next step. There are still a few more processes that I have to work out until I can run the simulation and start generating data, but I’m happy with my progress so far!
Week 5: Generating Preference Profiles
Welcome back to my blog, this time for week 5. This week, I decided to focus on generating the preference profiles, which, for all intensive purposes, can be considered the ballots. There are many different ways to generate these profiles, so the majority of my time was spent reading journal articles and similar studies to best design my generation methods. Most of the studies that I read, as well as my previous knowledge lead me to choosing a spatial model to generate the preference profiles, as it was determined to be the most realistic generation method. If you are familiar with the political compass, then this model will seem somewhat familiar. In the political compass, there are two dimensions, one representing an economic scale, and the other a social one. Based on the weight and direction of your preferences, you can be placed on the graph.
Source: Political Compass [1]
The spatial generation model leverages this concept by generating points on a graph like this for both candidates and voters. Each voter’s preference is then determined by its proximities to each candidate, with the closest candidate being ranked first, and the furthest ranked last.
The example above would illustrate a spatial model with two dimensions, an x and y axis. However, there can be additional dimensions, which add complexity and nuance to the simulation. Furthermore, when generating the profiles, the number of candidates and voters need to be specified. The academic articles helped me when deciding which variables to use.
There was little research similar to mine that had used spatial generation models, instead opting to use a different, more random model. Despite the different generation model, I will still be basing my variables off of them, so that my results can have direct comparisons. Those studies had generated profiles with 4,5,6, and 7 candidates and with voter populations of 100, 200, 300, 400, 500, 600, and 2000. Since they hadn’t used spatial models in their research, I had to look elsewhere to decide how many dimensions my spatial model would use. I ended up finding research claiming that preferences generated with 2,3, and 4 dimensions were most realistic, so I went with those.
Next week, I need to program the functions to truncate the profiles, but after that I’ll be able to generate the data and start learning from it. Hang tight!
Week 6: Truncation Functions
Once again, welcome back to my blog. Last week, I was able to decide on how I wanted to generate the preference profiles, opting to use a spatial generation model with 4, 5, 6, and 7 candidates, voter populations of 100, 200, 300, 400, 500, 600, and 2000, and dimensions of 2, 3, and 4. Once the complete profiles are generated, I need to be able to truncate them probabilistically to model realistic voting patterns and uniformly in order to mimic forced ballot truncation. This week I dedicated my time to creating these truncation methods.
The majority of the work for the probabilistic truncation function was done within the first two weeks of this project when I generated the probability distributions. If you recall, I generated different probability distributions for elections with each number of candidates(ie. One for elections with 4 candidates and another for elections with 5 candidates). Since that was already complete, I just had to write a function to truncate the preference profiles based on those distributions. The function works by iterating through every ballot in the preference profile, each time truncating the ranking to a somewhat random length (based on a number generated from the probability distribution).
The next method that I wrote this week was to truncate the profiles uniformly, meaning that the ballots all get sliced down to the same, specified length. The function takes in two parameters: a preference profile and the length of the ballot to truncate down to. It then iterates through every ballot and removes the candidates that were ranked behind the specified length. If the ballot is already shorter than the specified length, then the ballot stays the same. For this reason, not every ballot in the resulting profile will necessarily be of uniform length.
Now that these two functions are complete, I can start putting together the simulation, which is what I’ll be doing next week. Don’t miss it!
Week 7: Finalizing and Running the Simulation
Hello all, and welcome back. All my previous work has been leading up to this: the simulation. This week, I was able to finish it, meaning that I will soon have the data needed to move forward in my project. In this blog, I will explain the design of the simulation.
The first step of the simulation is to generate a complete preference profile using the spatial generation model that I described in week 5. These profiles are generated with a set of 3 variables: number of candidates, number of voters, and number of dimensions. Once that profile is generated with the set of variables, it is probabilistically truncated using the function developed last week. As described previously, this is done to mimic realistic voting patterns, which aligns with the goal of my project.
The next step is to find the “true” winner for each voting system. The “true” winner is the candidate that wins when all preferences are expressed. This “true” winner will be used as the basis on which to judge how each voting system performs under forced ballot truncation.
Once the “true” winners are found for each system, all the ballots are uniformly truncated by 1 candidate (refer to last week’s blog if you want more information). New winners are then calculated using the profiles with the truncated ballots and those winners are compared to the “true” winner. It is then recorded whether the “true” winner and new winner match, and then the ballots are truncated once again and the process repeats until all the ballots are truncated to 1 candidate. This entire process is then repeated 10,000 times for the same set of variables: generating a preference of profile, calculating the “true” winner, truncating the ballots, and comparing the winners.This larger process is repeated for each permutation of variables, which results in 84 iterations, meaning that 840,000 total preference profiles were generated while collecting data for this project. All of this data is now recorded in a spreadsheet, which I will start analyzing next week. See you then!
Week 8: Bump in the Road
After 7 weeks of relatively smooth sailing, I came upon my first major hiccup. In weeks 3 and 4, I explained how some of the voting systems that I was working with weren’t designed to work with truncated ballots, so I had to tweak them. Unfortunately, I messed up – or so I thought.
After taking quick glances at the data from the simulation that I ran last week, it seemed like the Bucklin voting method was behaving unexpectedly. There were two features that caught my eye, but the most glaring one was that, unlike every other voting method, when elections were truncated by one ballot, the winner didn’t match the “true” winner.
First, I looked into whether there was a bug in my code, but after many thorough glances I moved on from that possibility. Since that wasn’t the issue, I decided to test my implementation of the voting system in other ways, such as manually calculating election results from profiles that caused Bucklin to find different winners from elections truncated by 1 candidate.
Everything seemed to be working correctly, so I talked to my off site advisor about it. He explained a few things to me, which sorted my confusion. The fact that Bucklin elections truncated by 1 candidate produced winners differing from the “true” winners” was actually expected.
As a quick refresher, Bucklin finds its winner by tallying up the first round of preferences, and if a candidate achieves a majority, it is declared the winner. If no candidate has a majority, the number of times each candidate was preferred second gets added to their first place tallies. If any candidate’s sum of first and second place votes is greater than 50% of the total ballots in the election, then they are the winner. This addition goes on until a candidate reaches a majority of votes, or every preference on every ballot is tallied, at which point the candidate with the plurality of votes wins.
I had rushed to assume that truncating ballots by 1 candidate shouldn’t affect the election outcomes. However, since voters don’t rank every candidate, there is no guarantee that a majority will be reached, which means that the last round of voters actually does affect the results.
Ultimately, It turned out that there weren't any issues, which I was happy about, or else I would have needed to rerun the simulation, which took over a week to complete. Sorting out this situation took up my entire week, but I’m glad it's behind me. Beyond what was described above, there are other interesting results that I will cover in the paper that I produce at the end of this project. Stay tuned!
Week 9: Analyzing the data. For real this time.
Hello readers, and welcome back to my blog! This week I picked up from where I was after being thrown off course from last week’s debacle. And luckily, my pace has returned to normal and I am back on track.
Throughout the week I worked on more carefully analyzing the data produced from the simulation. With over 840,000 preference profiles generated, there was a lot of data to sort through. The first thing that I wanted to do was isolate each variable (number of candidates, dimensions, and voters). This would allow me to pinpoint how each of them affected the elections and the voting methods’ abilities to select their true winning sets.
Controlling each of these variables produced interesting results, especially in regard to my previous research. In my previous research in which ballots were still force truncated, but completely filled, the number of voters and candidates significantly impacted the performance of each of the voting methods. On the other hand, in this research project, those variables had a much weaker effect on the results.
Beyond isolating those variables, I created graphs to be used both in my final deliverable as well as my final presentation. I also took note and explored other interesting trends that caught my eye, which will all be recorded and described in the final research paper that I produce.
Analyzing the data this week was a lot of fun for me because I got more practice with conducting data analysis with python, a skill that I intend to hone further in the future.
I now have all the information I need to finalize my research paper and presentation, which will be the tasks for next week. See you then!
Week 10: Wrapping Up
Welcome back, this time to my penultimate senior project blog. The first part of this week involved me finishing up my research paper. By this point, I had written most of my research paper. The literature review had been written very early on as I was already somewhat familiar with the topic and had conducted additional research to ensure that I was conducting my study in the best way possible. I had also already written the methodology section around the same time I was blogging about it in the earlier weeks. I still had a lot to do, however, including the results, discussion, and conclusion sections.
The results section required me to reformat many of the graphs I produced last week, which I then inserted into the paper. In the discussion section, I described more of the patterns that I mentioned last week, making sure to go into more depth and explain each of them more comprehensively.
The second part of my week was taken up with work on my final presentation that I will be giving to the BASIS community. Most of this was relatively easy, taking what I already had in my research paper and converting it to slide form. I do, however, need to work on my communication and explanations of each of the topics, especially when presenting them in a concise form in front of an audience. I plan on practicing this a lot more up until the day I present. I can’t wait to share my findings with you all. See you on the stage!
Post 12: Concluding Blog
For the last time, welcome back to my senior project blog. My project has concluded, and I’m looking forward to the summer and starting college next fall! In case you want to see more, here are the slides from my presentation and my final paper. This project taught me a lot about the topic of voting theory and the process of conducting research. It was especially interesting completing a project based on my own previous research, an experience that I hope to continue in the future. This project wouldn’t have been possible without outside help. I’d like to thank my on site advisor, Eric Pacuit for providing his expert advice and guiding me throughout the process. I’d also like to thank Mr. Merritt for his support and instruction during the project. Lastly, I’d like to thank all of my past Basis teachers and faculty, for providing me with 10 years of fun, engagement, and education. As I look forward to college, I’m excited to learn even more about this topic as well as other ones that capture my interest to the same intense degree. I also intend to continue participating in and conducting research on more advanced topics.