Election Monoids And “Equal” Votes
I care a lot about the best ways to run elections. I also care about mathematics, and algebra in particular. What happens when you mix the two? Let’s find out!
Background and Definitions
First, some background. When an election is held, most people expect that each voter votes for some option, and the option with the most votes wins. This is called plurality voting. However, if there are more than two options, this turns out to be a terrible way to run an election! There’s a whole slew of better alternatives, but I’d like to focus on some kinds of structure that characterize them.
Let’s define some words that can describe any election, even if it looks different from the ones we’re accustomed to. In any election, some group of voters each cast a ballot, and the result of the election is determined by these ballots. More formally:
- There exists a set ℬ of possible ballots that any voter may cast. We don’t say anything about what the ballots look like. Maybe you vote for a candidate. Maybe you vote for more than one candidate. Maybe you rank the candidates. Maybe you score them. But in any case, some kind of ballot exists.
- When everyone votes, the collection of all ballots that were cast is a finite multiset of ballots, each taken from ℬ. The set of ballot collections is denoted by the Kleene star, ℬ*. By calling this a multiset, we’re assuming here that ballots are anonymous, so there can be duplicates, and we can jumble them around in any order without changing the result.
But, of course, the point of any election is to make a decision, which we call the outcome or result of the election, so:
- There exists a set ℛ of possible election results.
- There is a function r : ℬ* → ℛ giving the election result for a collection of ballots.
The main thing we care about when looking at a ballot or a collection of ballots is what effect it has on the election’s outcome. In general, there might be nominally different ways of filling out a ballot — and there usually are different collections of ballots — that have the same effect. For instance, on an approval ballot, whether you approve of everyone, approve of no one, or don’t vote at all, the effect is the same.
The mathematical way to isolate the effect of a ballot or ballots is to define an equivalence relation. We have to be careful though! A collection of ballots might give the same outcome on their own, but we also care about what effect they have when there are more ballots cast. Formally, we say:
- Two ballot collections X and Y have the same effect if, when combined with the same other ballots B, r(X ⨄ B) = r(Y ⨄ B). The symbol ⨄ just means combining two ballot collections together.
- This is an equivalence relation, so it partitions ℬ into equivalence classes. We call these equivalence classes ballot effects, and the effect of a ballot collection B is written as [B].
An example
In case that’s getting too abstract, let’s look at an example. In a three-candidate plurality election, each voter can vote for only one of the three candidates. The traditional way to count votes is to add up and report how many people voted for each candidate.
But that’s actually too much information! For example, the effect is the same whether each candidate receives 5 votes or 100 million votes, as long as they are tied. Taking the quotient by the equivalence relation above, then, discards information about vote counts that all candidates have in common, focusing only on the differences between them.
This can be conveniently visualized using a hexagonal lattice:
The gray space in the center represents no effect: a collection of ballots that is empty or exactly balance each other. As ballot voting for A, B, and C are added, one can move in three direction — up, down-left, and down-right — to reach the new effect.
I have only shown the effects that can be achieved with five or fewer ballots in this diagram, but the full set of effects with more ballots continues this tiling over the entire plane.
A wild monoid appears!
I’m looking for structure, and there an obvious structure to these ballot effects. We can combine two ballot effects as follows:
- Binary operation: [X] ⋅ [Y] = [X ⨄ Y]
- Identity: 1 = [∅]
Technically, one needs to verify that the binary operation is well-defined, but it’s easy to do so. It’s also associative, as combining ballot collections inherently is. Therefore, this forms a monoid E, which we will call the election monoid for this election. The election monoid describes the structure of what effects voters can have on the result of the election, and how they combine together.
Often, we may be interested not just about the effect of a collection, but also how many voters are needed to achieve that effect. In that case, we can look at subsets of the election monoid that tell us what effects can be achieved with specific numbers of ballots. This gives an ascending chain:
E₀ ⊆ E₁ ⊆ E₂ ⊆ …
This division of the election monoid into layers has a kind of compatibility with the monoid structure. Namely:
Eₘ ⋅ Eₙ ⊆ Eₘ₊ₙ
It turns out this kind of structure isn’t uncommon, and it is sometimes called filtered or graded, so that E can be described as a filtered monoid.
Looking at our three-candidate plurality election again, the nice thing about this geometric diagram is that it embeds the election monoid into a vector space, so combining effects of ballot collections amounts to just adding vectors in this space. We can also see the filtration into ballot counts.
If no ballots are cast, the result is always a three-way tie. As additional ballots are cast, we can see how the set of possible outcomes grows in a triangular shape until it eventually covers the entire plane.
Application: Equal Vote Coalition’s so-called “Equality Criterion”
The Equal Vote Coalition is one of many advocacy groups promoting election reform in the United States. They primarily advocate for STAR voting, a hybrid system in which voters score candidates, then the top two candidates by average score are compared in a runoff by the number of ballots that prefer each. However, the EVC also supports other methods, including approval and a specific Condorcet method (Copeland with Borda Count as a tiebreaker, which they have branded Ranked Robin).
In support of their advocacy, they often promote something they like to call the “Equality Criterion”, even taking the unusual step of proposing it to courts as a legal standard against which to hold elections. The criterion is defined in a recent paper as follows:
The Equality Criterion states that for any given vote, there is a possible opposite vote, such that if both were cast, it would not change the outcome of an election.
In practice, if we restrict ourselves to systems with anonymous ballots as we are doing here, the main work done by this criterion is to exclude voting methods that incorporate single-choice votes among more than three candidates, including not only simple plurality voting, but also instant runoff voting (confusingly called “Ranked Choice” by some despite the wide variety of voting options that incorporate ranked choices), and hybrid methods such Smith/IRV and Tideman’s alternative method. It does not exclude score and approval voting, STAR voting, Borda count, or Condorcet methods that operate only on pairwise comparison.
Without necessarily endorsing the criterion or the claims that it relates to equality, let’s look at it through this new lens. In the notation above, this criterion says that for all x in ℬ, there exists y in ℬ such that [{x, y}] = [∅]. It’s not hard to show by a simple induction, though, that there is an equivalent statement of the property in terms of the filtered algebraic structure of vote effects.
The Algebraic “Equality Criterion”: For all n, every x in Eₙ has an inverse also in Eₙ. In other words, the election monoid is a filtered group.
Recall the three-candidate plurality election mentioned above. The effects do indeed have inverses, obtained by reflecting across the origin in the ordinary manner of a vector space. (It’s easy to check that these inverses always land back on the hexagonal grid.) However, the filtration doesn’t contain inverses for everything in each component. For example, E₂ contains the effect of putting candidate A ahead by 2 votes, but the inverse effect of putting A behind by 2 votes doesn’t occur until E₄. Therefore, a three-candidate plurality election fails the criterion.
Manufacturing “equality”
But wait! The election monoid is a group, so we were almost there. It’s only the filtration that causes the property to fail. What if we simply choose a different filtration? For the property to pass, we want to grow in a shape so that each ballot effect can be reflected across the origin and land back in the same shape. The shape that works is hexagonal rings, rather than triangles.
To work out what the ballots should look like to produce this filtration, take a look at the degree 1 component, representing the effects that can be achieved with a single ballot. Not only can you vote uniquely for candidates A, B, or C, you can also now vote for any two of them. (Or none, or all, but this is irrelevant since its effect is equivalent to not voting at all.) That’s an approval ballot!
Most of the common counterexamples to the criterion have this same phenomenon, where ballot effects do have inverses, but those inverses just don’t live in the same components of the filtration because it takes multiple voters to achieve them. In that case, one can follow the same process to restore the property. First, you take the degree-one component and expand it to something that includes all of its own inverses. Second, you design a ballot that can have all of those effects.
By the way, instant runoff ballot effects also have inverses. There is, indeed, a generalization of instant runoff voting that satisfies this “Equality Criterion” simply by allowing more ballots. One way to describe such a weird creature would be to have voters choose whether to use their ballot for offense, to elect their preferred candidates, or for defense, to stop the candidates they don’t want. In the latter case, the bottom-ranked candidate loses a point instead of the top-ranked candidate gaining one.
In practice, we wouldn’t consider using such a clumsy ballot in an election, but it’s as a starting point for other ideas. First, we should give a voter both effects instead just one or the other. Now we have a less crazy proposal: same ranked ballots, same instant runoff procedure, but eliminate the candidate with the worst difference between their numbers of first-place and last-place votes. We might then try some other ideas in the same spirit that use even more of the ordinal information, such as eliminating the candidate with the lowest Borda count. These may not be great ideas, but they might not be the worst systems ever proposed.
Stupid group tricks
As we saw in the last section, choosing a new filtration in this way can modify many of the election systems where this criterion fails, constructing a generalization of the system that satisfies the criterion. But this only applies if ballot effects have inverses. Sometimes, the inverses may not exist at all.
In general, if you have a commutative monoid (like the election monoid here) and would like to find inverses to make it into a group, there’s a universal method named for Alexander Grothendieck. If the election monoid is not already a group, Grothendieck’s construction can create one using pairs of ballot effects, similar to how fractions are constructed from pairs of whole numbers.
This process can be hit and miss. For instance, suppose that instead of choosing candidates, the election is about a referendum (a yes or no question), and it needs more than a mere majority to pass. This election monoid turns out to have inverses only if the threshold needed to pass the measure is a rational number. So if you want to (for whatever reason) require that the proportion of yes votes is π/4 (about 78.5%), then you get a non-invertible election monoid.
Grothendieck’s construction adds the missing inverses, but the resulting election doesn’t really retain the desired effect: instead of making “no” votes stronger than “yes” votes, it offers voters a choice of whether their vote should count more or less. Rational voters should not choose to diminish their votes, so we can remove these options. The election has now returned to a 50% threshold.
In other cases, Grothendieck’s construction is more sensible, even if the election systems it’s applied to are not! Imagine the winner is chosen using a spinner, of the style you find in children’s board games. Instead of spinning randomly, though, each player can choose to rotate it clockwise by either 1, 2, or 3 radians. Whichever candidate it lands on at the end wins.
If the votes were a rational fraction of a full turn, you could undo a vote with enough clockwise turns; for example, undoing a 1/4 turn by adding a 3/4 turn to add up to a full cycle. Here, because each vote is an irrational fraction of the full circle, there are again no inverses. Grothendieck’s construction adds inverses by allowing you to turn the spinner counter-clockwise as well.
The end of the road
There’s one case where even Grothendieck’s construction fails us: when the monoid is not cancellative. A monoid is cancellative if x⋅y = x⋅z implies that y = z. The word cancellative here refers to cancelling the x in that equation. In other words, adding the same additional ballots (x) can never make other ballots’ (y and z) have the same effect unless they already did.
A non-cancellative monoid cannot be turned into a group by adding more elements. Grothendieck’s construction will do its best, but it will forget distinctions between different ballot collections that should elect different candidates! That’s not something we can tolerate, This, then, is a fundamental limit of when we can manufacture the “Equality Criterion” for voting systems that don’t have it to begin with.
What would such an irreconcilable election system look like? Suppose you’re again voting yes or no on a referendum, but this time the rules say that we choose the result with the most votes, except that if fewer than a thousand votes are cast, the referendum automatically fails. It’s a kind of protection against sneaking through a referendum with very low turnout. Cancellativity fails here because if two ballot collections differ only in whether the participation threshold has been met, adding additional votes to each can cause them to become identical. This kind of thing happens any time you allow a fixed number of voters to irreversibly change the election.
Wrapping it up
So we constructed an algebraic approach to thinking about elections, ballots, and their effects. We then applied that to the Equal Vote Coalitions so-called “Equality Criterion”, and it revealed a connection between this criterion and a filtered group structure. By understanding that connection, we were able to see not just reword the criterion, but explore:
- The different ways in which elections might fail the criterion.
- Some universal techniques for modifying election systems to recover the criterion when it fails. One of those ended up reinventing approval voting, while another suggested some interesting IRV variants.
- Where the limits are, and when a failure of this criterion simply cannot be repaired.
To be clear, I neither endorse nor oppose this criterion, and have avoided giving my opinions on specific proposals or voting reforms. The important bit isn’t about the details of this particular criterion, but rather about what happens when we try different perspectives, look for well-understood structure, and see where that takes us.
Well, that and it was fun. Hope you enjoyed it, as well.
