Fair voting: the quest for gold

Originating authors are Gabriel Rosenberg and Mark Iwen.
It is a little known fact that two gold medals were awarded for the same pairs figure skating competition in the 2002 Winter Olympics. These two medals were ultimately a result of contentious voting which initially resulted in the clear crowd favorites not winning the gold medal. The outrage over this decision was so great that the International Olympic Committee (IOC) eventually had to award a second gold metal to the second place figure skating pair in order to settle the scandal. As a secondary result, the voting system for deciding which figure skaters deserve which medals was changed (NB: Prior to 2003 judges individually scored participants and used these results to rank the athletes. These ranks (not scores) were then combined to award overall prizes).

Imagine that you are on the IOC in 2003 and have been tasked with developing a better voting system for judging figure skating competitions in the future. What voting system would you choose for ranking figure skaters? How would you make sure that the voting system was fair? Not surprisingly, mathematics can help us answer these questions!

Functions to the Rescue: The Power of Abstraction

One way of thinking about creating a new voting system for judging figure skaters (or a new voting system for any other purpose) is to begin by considering all possible voting systems. We can then construct a good voting system by slowly restricting all possible systems down to a smaller set of desirable alternatives. By proceeding in this fashion we can hope to not miss many good alternatives, thereby keeping our options as open as possible.

Lets begin this process by modeling (a very general class) of all possible voting systems. Any voting system in this setting is ultimately going to be concerned with ranking a set of skaters based on the input provided by a set of voters (e.g., the Olympic judges). Suppose that our set of competing skaters is , each of which is scored by each judge from the following set of judges,

Each judge assigns scores to the skaters which produces a different ranking of the skaters for each judge. For example, the judge’s scores for a particular competition might result in the following individual rankings (see Table 1).

Any voting system must take this set of nine individual rankings by each judge and output one final ranking which determines the first (gold), second (silver), third (bronze), fourth, fifth, etc. place winners from the set of all skaters, . Mathematically, we can see that our voting systems are exactly the set of functions which takes rankings of as input, and produce one final ranking of as output. Here represents the number of judges in .

Some Qualities a Good Voting System Might Have

Of course, we can immediately see that this set of functions is too general to be fair. For example, the function which always assigns the second skater (i.e., Berezhnaya in this case) a gold medal no matter how the judges actually vote is still a possible voting system. Clearly, we need to further restrict our possible voting functions in order to disqualify such unfair voting systems.

Respecting Unanimous Opinions: The Pareto Condition

The Pareto condition is one quality that most would agree that a good voting system should have. Loosely stated, the Pareto condition tells us that if a particular skater is ranked above another by all the judges, then a good voting system should ultimately rank the unanimously preferred skater above the other skater (e.g., if Cohen is ranked above Berezhnaya by all the judges, then Cohen should be ranked above Berezhnaya on the podium). This condition roughly guarantees that a voting system will respect unanimous voter opinions.

Although it is difficult to conceive of a natural voting system which could lead to a result that all voters dislike, this can actually happen when the voting system is hierarchical in nature. Consider, for example, that our four skaters perform in the following order: Asada, Dijkstra, Cohen, and Berezhnaya. Asada and Dijkstra are the first two to skate, and after they skate the judges prefer Asada by a 6-3 margin. Then, after Cohen skates next, the judges again vote by a 6-3 margin that Cohen was a better skater than Asada. Finally, Berezhnhaya skates and, sure enough, the judges believe that Berezhnaya is a better skater than Cohen by a clear 6-3 margin. A voting system based on these sequential pairwise comparisons may then lead to a podium ranking of Berezhnaya (gold), Cohen (silver), Asada (bronze), and Dijkstra (does not place). When the judges, though, write out their individual preference rankings (as seen in Table 2 where each column represents one judges ranking from highest place at the top, to lowest place at the bottom) they are shocked to discover that all nine of them thought that Dijkstra had skated better than Berezhnaya. The gold medal went to a skater that was unanimously thought to be worse than the 4th place finisher!

Independence of Irrelevant Alternatives

Imagine the following situation: Suppose that Asada and Berezhnaya have skated, but Cohen has yet to skate. In this situation the judges have all decided which of the first two skaters they like better, but are not sure yet how Cohen will compare since she hasn’t performed yet. The officials who tabulate the results, though, want to know where things stand right now (e.g., before a commercial break). Thus, the officials tell the judges to rank Cohen for the time being based on their best guesses of how she will do so that the officials can announce how Asada will finish relative to Berezhnaya. The voting function is evaluated, and its determined that Asada should finish ahead of Berezhnaya on the podium. The voting function also places Cohen somewhere on the podium, but everybody knows that the ranking is only a guess which will probably change once Cohen actually skates.

Later, after the commercial break, Cohen skates and some of the judges change their ballots in light of how Cohen performs. They don’t, however, change whether they ranked Asada higher than Berezhnaya, or vice-versa. When the official results are tabulated via the voting function, though, it now turns out that Berezhnaya finishes ahead of Asada on the podium! This both seems unfair, and makes for bad television to boot! Why should the placement of Cohen determine which of the other two skaters were better? A system where this strange behavior cannot occur is said to satisfy Independence of Irrelevant Alternatives, or IIA for short. Roughly speaking, a voting system which satisfies IIA will not change previously established partial rankings based on future performances.

Improved Opinions Should Never Hurt: Monotonicity

Next, imagine a situation where the medal results were announced with Asada taking the gold, Berezhnaya the silver, and Cohen the bronze. The Bulgarian judge then steps forward, though, and claims that her ballot was misread. Her ballot was read as: Asada, Berezhnaya, Cohen, though she actually voted Berezhnaya, Asada, Cohen. The officials recalculate the results and announce that now Berezhnaya should only take the bronze. This seems quite strange — being ranked higher by a judge somehow hurt Berezhnaya in the podium results! A system for which such a bizarre situation can never happen is said to satisfy monotonicity.

At first glance it might seem strange to even consider such a property. What kind of voting system would result in a skater being hurt by being ranked higher? Recall, however, that a potential voting system is merely a function and there is nothing requiring it be reasonable in context. It is up to us to figure out what makes the system reasonable.

It is interesting to note, though, that this seemingly reasonable property is NOT satisfied by some very common voting systems. In fact, any system which uses a series of runoff elections, such as the voting system used by the IOC to select a city to host the Olympics, fails to satisfy monotonicity. How frequently such non-monotonic situations actually occur is the subject of much research and debate, but just the fact that such a situation is possible in a voting system in current use may lead us in search of a different voting system.

Equality: Neutrality and Anonymity

Another property we might want our voting system to have, as a matter of fairness, is that it treat all skaters equally. That is, the same individuals should win independently of their skating order, names, nationality, etc.. We will say that a system with this characteristic satisfies neutrality. Similarly, we may want the voting system to treat all the judges equally. That is, the extent to which any judge’s vote counts toward determining a final skater ranking should also not depend on the judges voting order, name, nationality, etc.. A voting system which satisfies this property is said to have anonymity.

Interestingly enough, we can discover common (democratic!) voting systems which lack these properties. For example, any country which elects its leader based on accumulating election results from different geographical districts fails to satisfy anonymity. For example, in the United States voters from states with majority support of one political party could have their votes “count for more” by temporarily relocating to another state with a more closely contested election. This is exactly because voters from “swing state” have more power to influence which candidates get their state’s electoral votes.

Some Bad News: Arrow’s Theorem

We now have several reasonable criteria we would like our Olympic voting system to satisfy. In this section we will attempt to locate a set of good voting systems which have all the properties we have discussed above. As above, we will focus on a nine judge panel ranking three skaters.

Suppose we decide to test a new voting system that we are told satisfies the conditions of IIA, monotonicity, and neutrality. To help us test this new system, let us consider a case where there are three sets of judges. Let’s say the three judges from Asian countries all prefer that the top three skaters should finish in the order Asada, Berezhnaya, Cohen. Furthermore, suppose that the two American judges prefer that the skaters medal in the order Cohen, Asada, Berezhnaya. Finally, lets say that the four European judges prefer the skaters should finish in the order Berezhnaya, Cohen, Asada. Our voting system must return some order for the podium, but what can that order be?

Continuing our example, suppose that our good voting system results in a podium order with Berezhnaya finishing ahead of Asada. Since we know that our system satisfies IIA, this implies that whenever the four European judges rank Berezhnaya ahead of Asada, and the other five judges rank Asada ahead of Berezhnaya, we must end up with Berezhnaya ahead of Asada on the podium (i.e., Cohen’s position will not change anything regarding how Berezhnaya finishes relative to Asada!). Since we know our system is monotonic, this result would certainly still occur even if some of the other five judges also ranked Berezhnaya ahead of Asada (i.e., doing so should only improve Berezhnaya’s position!). This would mean that the four European judges hold some dictatorial power in the sense that WHENEVER they rank Berezhnaya ahead of Asada, they are guaranteed that Berezhnaya will finish ahead of Asada. Since we assumed that our voting system is neutral, there is nothing special about Berezhnaya and Asada in this example. WHENEVER the European judges rank one skater ahead of another skater, the skaters MUST finish in that order on the podium. So if the European judges vote as a bloc (all of them voting the same way) the podium result will agree with their vote regardless of how any other bloc voted. We would say that the European judges had dictatorial power.

As a result of our discussion in the previous paragraph, we might argue that the profile above should not result in Berezhnaya finishing ahead of Asada on the podium. Let us suppose instead that Asada should finish ahead of Berezhnaya. But, we can then look at where Cohen should place relative to Berezhnaya. If the podium order had Cohen ahead of Berezhnaya, then we are in a situation where the two American judges are the only ones ranking Cohen ahead of Berezhnaya (resulting in the podium order reflecting their opinion). Using the same reasoning we used before with the European judges, this would imply that the American judges had dictatorial power! If we do not want a minority to have dictatorial power, we are then forced to place Asada ahead of Berezhnaya ahead of Cohen on the podium. But, that implies that Asada is finishing ahead of Cohen. Given that the three Asian judges were the only ones that had Asada ahead of Cohen in their rankings, the same reasoning process we used with the European judges would now show that the Asian judges have dictatorial power. Dictatorship is inescapable!

Since our voting system must lead to some podium ranking for this profile, one of our three groups of judges must have dictatorial power. That is, in every single situation in which that group votes as a bloc with the same rankings, the podium result will agree with their vote. This is bad enough in that we would have a group consisting of a minority of the judges that would have the power when working in concert to could control the results of the voting system. The problem is even worse, though. Once we have a dictatorial group we could further divide that group into two subgroups and using reasoning similar to that above show that one of those subgroups was dictatorial. By continuing to further subdivide these dictatorial groups we are eventually left with a group consisting of a single judge–a dictator. Kenneth Arrow proved these results in 1950 even under the weaker conditions that the voting system merely satisfied IIA and the Pareto condition.

Voting Theory

Arrow was one of the first to study voting from this mathematical perspective, that is, as functions which may or may not have certain desired properties. His work, however, opened the door to a whole new area of research in which mathematicians, economists, and political scientists cross paths and share ideas about what is possible and what is desirable. For example Allan Gibbard in 1973 and Mark Satterthwaite in 1975 looked at the property of whether a voting system has the (seemingly undesirable) property that it can be manipulated. In other words, might there be situations where somebody could gain a more desirable outcome by lying about their preferences. Their work led to the conclusion that the only voting systems that were non-manipulable either had a single dictator, or else had at least one alternative that could never win. Subsequent researchers have looked at questions such as how often is such manipulation possible, and how likely is it to occur.

Moral

We see then that mathematical reasoning, through careful precise definitions and logical proof, can be applied to situations beyond mathematics and the natural sciences. Such reasoning may be necessary to convince oneself of a result that at first glance seems counterintuitive. In the context of our Olympic example, we can see that it is impossible to satisfy all four of the good characteristics we would like for our voting system, at least if it is based on judge rankings alone.

There is no need to succumb to despair, however. Our analysis above tells us that we must simply consider a larger class of voting schemes in our search for a good system. Example solutions involve actually using the numerical scores each Olympic judge produces for something beyond simply ranking their preferences. Other fixes include introducing a small amount of randomness into the voting scheme. For example, we could randomly drop some judge’s scores on occasion, thereby establishing a voting scheme which is not a function of the form we have considered. This last solution was, in fact, one of the aspects adopted as part of the new figure skating voting method implemented in 2004!

References

For All Practical Purposes by COMAP, 8th ed., W.H. Freeman & Company, 2008.

G. Szpiro, Numbers Rule: The Vexing Mathematics of Democracy, from Plato to the Present, Princeton University Press, 2010.

P. Tannebaum & R. Arnold, Excursions In Modern Mathematics, 7th edition, Prentice Hall, 2009.