By Akshay Agarwal
(Yvonne Livesey, 2022)
Elections. At first glance determining the winner of an election seems pretty straightforward: tally up each voter’s favourite candidate, and wallah, the one with the most votes is the ‘winner’. This, we soon will find out, is unfortunately the way most of our elections work: from student governments to club elections to presidential elections. However, assuming there’s a large election with hundreds of candidates, what if I told you the winner of such an election could potentially be less popular than more than half of the other candidates? That it deterministically doesn’t select the winner at all? Rather, the winner of an election among hundreds of people cannot really be considered the winner at all. Today, we’ll begin by showing the issue of a normal election within a large group of candidates, then go on to explore the computer science data structures of graphs and trees, and finally, see how much of a better system we know, and how much better can it get.
For a smaller case, let’s assume that a particular election has ten candidates,
with each of them numbered from one to ten, running for a single spot in a majority vote election. Now, let’s assume candidate one gets the majority of votes, barely surpassing candidate two by one vote. Out of the voters, there are two voters, voter A and voter B, whose ‘order’ of favourite candidates is candidate four, candidate two, and then candidate one. Thus, in the election, they voted for candidate four (who didn’t get many votes), but if candidate four didn’t exist, they would both vote for candidate two who would then end up winning the election. Strange, right? Even though a candidate gets the most votes, they’re not necessarily the most popular candidate, they were just the most popular first choice of the voters. Therefore, mathematically speaking, the only deterministic way of determining the most popular candidate is by a direct comparison between two of them; candidate one vs candidate two, for instance. However, scaling a two-person voting system to a system with hundreds of candidates is difficult, and that’s what we’ll be trying to figure out. Let’s first begin by analyzing some intuitive ideas of such a system.
But first, as analyzing each voting system with words is cumbersome, all the voting systems we’ll be analyzing can be modeled as a directed graph, which is a data structure used in computer science. A directed graph consists of two parts: nodes and edges, where each node is a candidate, and each edge between nodes points to the “more popular” candidate of the two.
For instance, on the diagram to the left, the three green circles are the nodes, representing candidates one, two, and three. The edge between nodes one and three which points towards three, shows that candidate three is more popular than candidate one.
Personally, my first thought was to create a system where each pair of candidates goes against each other; if everyone goes against each other, the most popular candidate will inevitably be revealed. However, creating the directed graph for such a situation proves otherwise:
As is evident, even in this simple case with three candidates, each candidate beats one other candidate, and loses to another. So, from this graph, who’s the winner? Hard to tell right? This is what’s called a cyclic graph, as there’s a visible cycle. We don’t want to create a system where the graph will be cyclic, as determining the winner isn’t possible.
Now the second try, up till a few months ago, this was the best system mathematicians and computer scientists were able to create. Fischer, Procaccia, and Samorodnitsky worked on the Copeland Rule, which is essentially the simulation of an election as a ‘knockout tournament’. The graph of such a process is:
This graph is one of a knockout tournament where the “1st round” has all four candidates, and each subsequent round removes half the candidates, until there eventually is only one left. Such a graph is a special case of a graph, known as a balanced binary tree, which means that each subsequent row you go down, doubles the number of children nodes (nodes below their “parent”). Such a voting tree certainly does yield a winner, as visible on the top node; however, notice the number of matches the winner needs to win: just two (in this example). In fact, mathematically, we can say that if there are n candidates, the winner will only have to beat log(n) (base 2) of the other candidates.
Ideally, the winner of an election would beat at least half the candidates, as that means they surpass at least half of the other candidates; this is significantly lower than that number. Unfortunately, nobody has been able to create an algorithm that achieves such amazing results; in fact, a group of three researchers recently made a model which made it such that the winner had to defeat square root of n of the other candidates. However, the scope of that article is beyond that of this paper, although the fundamental understanding of graphs is still required, so if you’re interested, feel free to look up Loh and Iglesias’ paper, referenced in the citations below.
Even if you’re not going to be the one who spends years of their life on improving the voting tree, I hope this article gives you a better perspective on graphs in computer science, how to efficiently improve an algorithm, and the way we can solve practically any real-life situation with the power of computer science. In the future, whenever you see any sort of system, whether that be how school bus paths are decided or how Youtube searches work, I hope this article gives you the concept of how to analytically analyze such algorithms, and potentially improve on them. I’ll hopefully be able to open the newspaper one day and see you listed for analytically improving an important algorithm.
References
Iglesias, Jennifer, et al. “Computing with Voting Trees.” SIAM Journal on Discrete Mathematics, vol. 28, no. 2, Jan. 2014, pp. 673–684, 10.1137/130906726. Accessed 6 Nov. 2022.
F. Fischer., A. D. Procaccia, and A. Samorodnitsky, A new perspective on implementation by voting trees, Random Structures and Algorithms 39 (2011), 59–82.
N. Miller, A new solution set for tournaments and majority voting: further graph theoretical approaches to the theory of voting. Am. J. Pol. Sci. 24 (1980), 68-96.
Comments