# The Symmetry and complexity of elections

## Donald G. Saari

##### Department of Mathematics, Northwestern University, Evanston, Ill. 60208-2730
On personal and professional levels, the Marquis de Condorcet did like his fellow Academy member J.C. Borda. It is not clear why; maybe it was the regrettable tension that sometimes exists between abstract and applied mathematicians, or maybe Condorcet harbored jealousy over Borda beating him by over a decade in recognizing the complex and interesting mathematical issues that arise in the social sciences. Whatever the reason, rather than serving as an obscure historical footnote about the French Academy of Sciences during this prerevolutionary period of the 1780's, their conflict still characterizes basic divisions in the voting theory field that they started. Their concern, which is as critical today as two centuries ago, was whether we may inadvertently choose badly in our elections. Only recently have we become to understand the mathematical complexity of the problem along with what are some of the answers.

The story starts in 1770 when Borda worried whether Academy's decisions reflected who they truly wanted. His concern was not whether the voters were informed or voted, but rather about how they tallied the ballots. Through a cleverly constructed example, Borda demonstrated that the Academy's procedure was so bad that they could elect someone who they actually viewed as inferior while their election's bottom-ranked candidate is who they find to be superior! Clearly, such a misguided procedure should have been tossed into the trash heap of history. It was not; instead we still use it to select members of the Senate, Congress, City Councils, Mayors, Assemblies, and, indirectly, the President of the USA. This highly flawed approach is the standard plurality vote where we vote for one candidate and the winner is the candidate with the most votes.

Borda's example has twelve voters trying to rank the three candidates Alice, Becky, and Candy. Suppose the preferences of five voters are Alice first, Candy second, and Becky last -- denoted by Alice Candy Becky. The next four voters have the preferences Becky Candy Alice, and the last three have Candy Becky Alice. Trivially, the plurality election outcome is Alice Becky Candy with a 5:4:3 tally.

To analyze this outcome, let's play some thought games. For instance, had Becky dropped out of contention just before balloting, who should win the comparison between the top- and bottom-place plurality candidates? If our elections mean what we think they do, the immediate answer is Alice. But instead, a quick count shows that Candy would beat Alice with a 7:5 vote! Compounding the contradiction is that in the other two-person races Candy also beats Becky by 8:4 and Becky defeats Alice by 7:5. As Borda pointed out, these head-to-head comparisons strongly suggest that these voters view the plurality bottom-ranked Candy as the superior choice -- they choose her over anyone else in pairwise votes -- while they view the plurality winner Alice -- who always loses when compared with others -- as the inferior option! This suggests that we could suffer elections where we know we chose badly, but we do not know why. The true villain is our standard voting procedure.

Actual examples illustrating this frustrating behavior are easy to find. An interesting one is the 1991 Louisiana gubernatorial race featuring David Duke, former Gov. Edwards, and the incumbent Gov. Roemer. While Roemer's controversial decisions ensured that he would not be an overwhelming favorite for re-election, his opponents carried even heavier political baggage. During his term, Edwards was indicted for corruption and Duke was a former leader of the Klu Klux Klan, so it is reasonable to expect that Roemer would have beaten either of them in a two-person race. Instead, probably due to our flawed election procedure as illustrated by Borda's example, Roemer came in last. Edwards won the subsequent, highly publicized ``Krook or Klan" runoff.

To understand what goes wrong, notice the considerable amount of information dismissed by the plurality vote -- by registering only a voter's top-ranked candidate the procedure ignores how the voter ranks other candidates. In Borda's example, for instance, the faulty election outcome reflects the procedure's inability to capture Candy's favored status of being the only candidate who all voters rank in first or second place.

We all appreciate the critical nature of this lost information. For proof, just recall almost any New Hampshire Presidential Primary where the news media describes how some candidate siphons votes away from another one with similar views. The candidates react with cries of ``Don't waste your vote, vote for me!" So, as captured by Borda's example, it could be that when most voters like several closely contending candidates, none wins because of how the voters split the vote!

Even worse, suppose after nine serious candidates are in the New Hampshire primary a radical, R, joins the election chase on, say, the ``Return to the Snowshoe" platform. Suppose R is so repulsive that almost 90% of the voters have R bottom-ranked. But if the views of the respectable candidates are sufficiently close to split the vote, R could win with only slightly over 10% of the vote coming from the lunatic fringe, the uninformed, or voters mistaking R for someone else (as once happened in Illinois). R, a candidate almost universally despised, could win! This is the problem that Borda worried about.

While this Snowshoe example is extreme, it suggests that we might find elections exhibiting Borda's phenomenon when the views of top-ranked candidates represent a small portion of the electorate. By checking, we discover that again Roemer and certain other candidates in the 1995 Louisiana gubernatorial election may have been victimized by the plurality vote. While the final two candidates did not suffer from scandal, it is difficult to claim that both represented the views of a vast number of voters. Similarly, recent Russian elections provide a rich source of examples.

### Borda Count and Condorcet

The obvious remedy is to recognize voters' lower ranked candidates. Borda suggested assigning 2 and 1 points, respectively, to a voter's top- and second-ranked candidate; the candidate with the highest total wins. (With four candidates, the Borda Count credits 3, 2, and 1 points, respectively, to a voter's top-, second-, and third-ranked candidate. The obvious generalization holds for any number of candidates.) These weights matter; for instance, the Borda Count outcome for the introductory example is Candy Becky Alice supported by the tally 15:11:10. This Borda ranking reverses the flawed plurality outcome and agrees with the pairwise elections.

A way to compare the Borda Count and the plurality vote is to recall how students are academically ranked in schools and universities. The plurality vote, which recognizes only top-ranked candidates, is similar to ranking students by counting the A's while ignoring all lower grades. So, if Rose has A's in five classes and B's in all others while Claudia has A's in six classes and fails all others, then this procedure, like the plurality vote, ranks Claudia above Rose! The Borda Count, however, resembles the standard 4.0 system where A's are assigned four points, B's three points, and so forth; here Rose would have the higher ranking. So, personal experience explains why the Borda Count is more reliable. Yet, in critical decisions affecting our personal finances (as reflected by economic policy) and even our lives (as reflected by foreign policy), we use the inferior approach!

But, is the Borda Count the best choice? Rather than using 2, 1, 0, why not reward excellence by using, say, 6, 1, 0? How about penalizing inferiority by using 4, 3, 0? What about allowing each voter to decide how to divide a certain number of points among the candidates? (Incidentally, a version of this last approach was endorsed by the Reagan and the Bush administrations; Lani Guinier was labeled a radical for supporting the same method.) Once Borda opened Pandora's Box, the mathematicians in the French Academy recognized the infinite number of options, so the issue became to determine which weighted method is the ``best." Only recently has this problem been resolved.

A little over a decade after Borda made his proposal, Condorcet became interested. Probably after carefully examining Borda's example and his emphasis on using pairwise outcomes to measure merit, Condorcet proposed using the head-to-head elections to rank candidates. For Condorcet, the candidate who wins all pairwise comparisons is the winner. (In Borda's example, Candy is the Condorcet winner while Alice is the Condorcet loser.) Without doubt, the Condorcet winner enjoys a distinct appeal with its rugged ``winner take all" sense of individualism. This intuitive sense probably explains why the Condorcet winner has become the widely used standard to judge the merits of other procedures.

But, does Condorcet's method matter? Won't it just replicate the Borda ranking? It need not. Demonstrating his masterful sense of combinatorics, Condorcet constructed an example showing how Borda, or any other way to weight candidates, could fail to elect the Condorcet winner! (His example is given later.) Borda must have treated Condorcet's negative conclusions as a stinging personal defeat; after all, Condorcet, his adversary, used his measure to identify crippling flaws of his Borda Count. Even today, this fact that a Condorcet winner need not be elected is cited as a fatal flaw of the Borda Count.

So why don't we use Condorcet's method? Again demonstrating his powerful mathematical insight, Condorcet constructed examples showing that his approach, too, has a serious problem; a winner need not exist! The Condorcet profile can be illustrated with just three voters who are defined by the preferences Anna Brigid Connie, Brigid Connie Anna, and Connie Anna Brigid. A quick count shows that in pairwise elections Anna beats Brigid and Brigid beats Connie both with a 2:1 vote. Presumably, this requires Anna to beat Connie, but she does not. Instead, a cycle is formed because Connie beats Anna by 2:1. This cycle, where each candidate wins and loses an election, denies determining a Condorcet winner and/or loser!

A two-century debate has failed to resolve this Borda-Condorcet controversy. Yet, there remains a strong consensus for Condorcet's approach when his winner is defined. Also, a wide variety of other methods have been promoted and examined to make this field of social choice a very active, contested academic area. For instance, because cycles foil the intent of Condorcet's approach, several clever investigations have characterized different kinds of cycles and what they might mean. However, the severe mathematical problems have restricted progress.

### Arrow

Kenneth Arrow was unaware of this rich history when, almost a half century ago, he worried about the same issues. His contributions and seminal approach revived interest in this field while ushering in a new era. Instead of trying to promote one procedure over another, Arrow sought all procedures that satisfy a short list of seemingly innocuous, yet critical conditions. The idea is similar to buying a car where, after first identifying those that are reliable and affordable, we can select a car with other desired features. Similarly for voting methods, first find those procedures which satisfy basic properties before selecting a fancier approach.

A key factor, needed to avoid cycles, is transitivity. This condition, which models rational behavior, requires a voter preferring Margarete Melanie and Melanie Karen to also prefer Margarete Karen. If voters fail to be transitive, then we are in a ``garbage in, garbage out" setting where when their cyclic, confused preferences are fed into a procedure, we must expect similar confused cyclic outcomes to emerge as ``garbage out." This is why we consider only voters with transitive preferences (to avoid ``garbage in") and procedures with transitive outcomes (to avoid ``garbage out").

Arrow's first assumption is that each voter can rank the candidates in any desired transitive manner. This is reasonable; it corresponds to where the rational voters enjoy a freedom of belief. His next condition is an obvious ``unanimity" assumption; in those special settings where all voters rank a pair in the same way, say everyone prefers Judy to Lois, then that is the group's ranking of this pair. It is difficult to find anything controversial about this.

The third condition is imposed to avoid the problems illustrated by Borda's example. Arrow's Independence of Irrelevant Alternative condition, or IIA, requires the group's relative ranking of any two candidates to be determined by each voter's relative ranking of this pair. For instance, if the group outcome is Vivian Joyce Toini, then the relative Vivian Toini ranking should prevail no matter what the voters think about Joyce as long as they retain their same views about Vivian and Toini. Without this assumption, paradoxes continue. Notice how IIA captures and extends Condorcet's notion.

These conditions are so basic, so elementary, so fundamental, so intuitive that it should be easy to find all sorts of procedures satisfying them. For instance, the majority vote suffices with two candidates. However, Arrow proved the shocking result that with three or more candidates, the only procedure with transitive outcomes that satisfies these conditions is a dictatorship! Does this reduce democracy to a shambles?

It is easy to understand the consternation generated by Arrow's conclusion! It completely threw decision theory and related academic areas into tail-spin that continues today. Indeed, Arrow's result is so counter-intuitive, so surprising, and so basic that it correctly formed a portion of his Nobel Prize. And, his conclusion generated an huge literature; following Arrow's lead, we have been treated to all sorts of discoveries showing that much of what we take for granted about basic election and decision procedures is wrong. Nearly a half century later, most conferences related to these topics include papers addressing this issue. In fact, a researcher highly regarded in this field recently wrote to me that Arrow's result reduces us to choosing ``between a dictator or a paradox." This is not reassuring.

### Resolutions

Although Arrow's Theorem and the many extensions suggest that this field is destined to an eternal mess, there are positive answers, coming from mathematical symmetries, which provide reasonable, comforting resolutions! Instead of having to choose ``between a dictator or a paradox," we can select from among reasonable methods. A major surprise is that the mathematics is reversing most of the previously widely accepted answers in this field! Another surprise is that we obtain a sufficiently simple explanation for Arrow's Theorem that had Arrow recognized and described it, his result might not have attracted much attention! This would have been unfortunate.

The argument starts by describing the source of cycles. By understanding why cycles occur, we discover that rather than serving as a standard, the Condorcet winner is a bad concept! It then becomes an exercise to analyze the Borda-Condorcet debate; the surprising conclusion is that Borda's method, not Condorcet's approach, is the one to trust! Still other extensions allow us to analyze all weighted methods to determine all possible faults; again, the Borda Count is the most fault-free procedure. Modification of these arguments show that Arrow's conclusion is not as disturbing as commonly described; indeed, there are comfortable resolutions -- a natural one is the Borda Count!

Figure 1

To see the symmetry of Condorcet's profile, construct a ``ranking triangle." This is a movable equilateral triangle attached at the center where the vertices are labeled with the rankings 1, 2, and 3. Choose a ranking for the three candidates, say A B C, and, as indicated in Figure 1, place these names near the appropriate vertex of the ranking triangle.

This placement defines one preference for the Condorcet profile; to define the next one, rotate the ranking triangle in the indicated direction to define the preference B C A. The next rotation of the ranking triangle leads to the preference C A B. Because another rotation returns the ranking triangle to its initial position, the profile is complete. (A little experimentation shows that the only other ``orbit," or Condorcet profile, involves interchanging any two names to create A C B, C B A, B A C.)

A nice explanation for Condorcet's profile is one I heard when Dr. D. Briars, Director of Mathematics for the Pittsburgh schools, invited me to lecture on mathematics to different school groups during the annual Mathematics Awareness Week. While most audiences were high school classes, one was Ms Chamberlain's fourth grade class. When these students saw Condorcet's profile, they immediately argued that no candidate is preferred. As they accurately observed, each candidate is in first, second, and third place once, so no candidate is favored over another. Notice how their observation coincides with the way the profile is constructed with the ranking triangle. Indeed, their argument for a complete tie agrees with the outcome for a plurality vote, the Borda Count, and all other weighted voting methods. So, what is there about this profile which, instead of the fair, natural tie vote, forces the pairwise vote to offer the A B, B C, C A cycle?

To explain the cycle, divide each ranking from this profile into its pairwise rankings

A B C ---> A B & B C & A C
B C A ---> B A & B C & C A
C A B ---> A B & C B & C A

A weakness of the pairwise vote is that it only tallies the ballots; it cannot monitor who cast them. Consequently, the procedure cannot determine whether the first voter's pairwise preferences are as listed in the top row of the table, or whether they are the ones along the diagonal defining the cyclic, confused preferences A B, B C, C A. (See Fig. 2) Similarly, the procedure cannot distinguish whether the second voter's preferences come from the second row or the second diagonal which also define the cyclic A B, B C, C A, or whether the third voter's preferences come from the third row or the remaining diagonal to define the reversed cycle.

In other words, the pairwise vote cannot determine whether the voters have the specified transitive preferences, or whether they were cast by confused, irrational voters with cyclic preferences where two are A B, B C, C A, and the last is the directly opposite cyclic preferences A C, C B, B A. As this latter situation has two voters in favor of a (cyclic) proposition and one directly opposed, the only fair outcome is to adopt the proposition with its 2:1 vote. The pairwise vote agrees; it supports the cyclic proposal. But the pairwise vote cannot distinguish between Condorcet's profile and the cyclic outcome, so the cycle is the only reasonable, fair outcome for Condorcet's profile.

Cycles, then, manifest the deplorable property that the pairwise vote vitiates the critical assumption of rational voters with transitive preferences! Indeed, it is not difficult to explain all cycles, for any number of candidates, as the confusion by the pairwise vote between the actual transitive profile and a confused voter profile where the cyclic outcome is the natural one! Remember, a procedure is agnostic; it only reacts to inputs. If it is not designed to monitor for transitive preferences, it cannot. This is similar to a car where the performance depends on who uses it; a car cannot monitor whether the driver has a valid license or can drive. So, the assumption of transitive preferences must be viewed as determining what happens when a certain type of voter use this particular decision vehicle. As shown, assuming the voters are transitive has no impact on the final outcome because there are settings where this method cannot distinguish between transitive and cyclic preferences.

To better explain this point, notice that the Borda Count does monitor whether a voter is rational! For the Borda Count, the ballot of a voter without transitive preferences cannot be tallied. Thus, in a surprisingly simple manner the Borda Count does monitor whether preferences are transitive while the pairwise vote cannot.

Because cycles indicate the loss of the assumption of transitive preferences, these profiles return us to a ``garbage in" environment. Thus we must be leery of all procedures based on pairwise comparisons including the Condorcet Winner. To show why the Condorcet winner is suspect, start with an example that has an undisputed outcome. Next, add a strong enough Condorcet cycle -- a ``garbage in" factor -- to change the identity of the Condorcet winner. In this manner, rather than reflecting any merit, this new Condorcet winner just manifests the inability of the pairwise vote to distinguish between transitive and intransitive preferences!

To illustrate with actual numbers, should 20 voters prefer Angela Bobbie Carol while 28 prefer Bobbie Angela Carol, then Carol is not a factor -- this is an election between Bobbie and Angela. Bobbie is the obvious winner with the 28:20 tally, she is the Condorcet winner, the winner with almost all weighted voting methods, and so forth. Now, complicate the issue by adding a 27-voter Condorcet profile where each of the preferences Angela Bobbie Carol, Bobbie Carol Angela, and Carol Angela Bobbie are assigned to nine voters. This Condorcet addition has no impact on the weighted voting rankings, but the resulting pairwise cycle changes the pairwise outcomes. It has to; the pairwise vote treats these new voters as being confused and irrational with cyclic preferences! The new result? The weighted ranking method, such as the plurality vote and the Borda Count, ignore the Condorcet portion so they retain their Bobbie Angela Carol ranking, but the destruction of transitivity now crowns Angela as the Condorcet winner! Rather than reflecting Angela's merits, this outcome underscores a serious flaw of the pairwise vote and Condorcet's approach.

Incidentally, this example is essentially the one used by Condorcet to discredit the Borda Count and all other weighted voting system. (To recover Condorcet's example, add another voter for each of the six possible types.) But, by destroying the assumption of transitive preferences, rather than the example supporting Condorcet's approach, it underscores problems with the Condorcet winner! Similar arguments show that any conflict between Condorcet's method and the Borda Count outcome manifests serious faults with Condorcet's method; not Borda's. This result completely reverses what has been commonly accepted for a couple of centuries!

### Arrow's Theorem

This same argument explains Arrow's Theorem. Arrow's IIA assumption requires procedures to concentrate only on pairs while totally ignoring whether the pairs satisfy transitivity. As such, IIA admits only procedure that are prefectly reasonable in an irrational society where voters can only rank pairs. Thus IIA disqualifies any procedure, such as the Borda Count, which monitors and requires the voters to have transitive preferences. Consequently Arrow's result can be viewed as seeking a procedure which satisfies his assumptions and which can serve societies with irrational voters, but which always has transitive outcomes in those special settings when used by voters with transitive preferences. Namely, which methods designed to handle irrationality become reasonable when the voters are rational?

One procedure is a dictator. When the transitive preferences of the dictator are subdivided into binary rankings, they can be recomposed in only one manner -- the same transitive ranking. But, with more than one voter, no procedure can always reconstruct the parts to predict transitive preferences. In other words, Arrow's IIA destroys the critical assumption of transitive preferences. As this returns us to a ``garbage in" environment, we must expect ``garbage out" conclusions. This explains Arrow's assertion.

In fact, all results I have examined that extend Arrow's assertion and promise all sorts of serious consequences for decisions and for economies admit the same explanation. Rather than being as troubling as previously expected, the basic lesson is that if we want to have rational outcomes, we must use procedures sophisticated enought to monitor whether the voters have rational beliefs! A way to preserve as much of Arrow's framework as possible is to slightly modify IIA so that it admits only transitive preferences. By doing so, the Draconian conclusion about dictators is replaced with the far more acceptable Borda Count!

### Weighted voting methods

Among the procedures which can monitor whether voters have transitive preferences are the weighted voting methods. But there are so many of them that we need another symmetry sieve to discard some of them. A natural symmetry is neutrality; this is where if the names of the voters are interchanged, then so are the election outcomes. To illustrate, if in Borda's example we discovered that every single voter thought Beckey was Alice and Alice was Beckey, then there is no problem -- just interchange their names in the election outcome. Neutrality, which requires a procedure to respect certain symmetrical changes in names, is satisfied by all weighted voting methods.

A closely related symmetry can be illustrated with an actual election in my academic department. When our Chair asked us to vote for three candidates, we all assumed he wanted us to list our top-ranked candidate first, the second-ranked candidate second, and so forth. We were wrong; he wanted the reverse order by listing our third-ranked candidate first. Again, as with neutrality, there seems to be little problem; just write the election outcome in the reversed manner. The only problem with this natural assumption is that it can be wrong.

Indeed, most methods fail this reversal symmetry. To illustrate, count how many times each candidate is top-ranked when three voters have the preferences Hollie Anneli Katri, three have Katri Anneli Hollie, four have Hollie Katri Anneli, and the last four have Anneli Katri Hollie to compute the plurality outcome of Hollie Anneli Katri with a 7:4:3 vote. When a ranking is reversed, the previously bottom-ranked candidate now becomes the first-choice. So, to find the outcome when all voters completely reverse their rankings, just count how many times each candidate is bottom-ranked in the original setting. This count reveals the surprise that instead of the expected reversed ranking of Katri Anneli Hollie when all voters reverse preferences, the actual answer is our original Hollie Anneli Katri with the identical 7:4:3 vote! Imagine the resulting sceptical reaction had our Chair announced that nothing changed in the election after reversing preferences!

Something is wrong. But, an examination of the example makes it arguable that its correct outcome should be a complete tie. This is because we can group voters into pairs with directly opposing views so it is natural to assume that their votes cancel. For instance, a voter with the Anneli Katri Hollie preferences should cancel the vote of an opposing voter with preferences Hollie Katri Anneli. This is true with the pairwise vote; it is not with the plurality vote.

So, which weighted procedures satisfy reversal symmetry? The surprising answer -- only the Borda Count! (For larger number of candidates, the reversal symmetry is supplemented with related symmetry properties where, say, everyone has the same candidate ranked last, but reverses the order of all remaining candidates.) All other weighted voting methods introduce a reversal bias that distorts the election outcome.

We discover, then, that the pairwise vote drops the assumption of transitivity while weighted methods do not. Similarly, the Borda Count and the pairwise vote respect the reversal property, but all other weighted voting methods (and procedures based on them) suffer this bias. Thus the only method satisfying both mathematical symmetries -- symmetries reflecting a sense of fairness -- is the Borda Count! This symmetry preservation is caused by the fixed differences between successive assigned weights for the Borda Count.

Examples illustrating the central role of the Borda Count now become easy to construct by exploiting the different biases. To do so, start with earlier preferences defining the undisputed Bobbie Angela Carol outcome. To demonstrate the weakness of Condorcet's approach, add, as done earlier, a cycle to make Angela the Condorcet winner through the voting power of the nonexistent cyclic voters. Weighted methods are immune to this cyclic effect, so they retain their original rankings. Next use the reversal bias to further complicate the story by making Carol the plurality winner while Angela and Bobbie remain, respectively, the Condorcet and Borda winners. This is done by adding 58 voters evenly split between Angela Bobbie Carol and the reversed Carol Bobbie Angela, and another 42 voters evenly split between Carol Angela Bobbie and the reversed Bobbie Angela Carol. The added voters do not effect the Borda outcome nor the pairwise rankings, but they crown Carol as the plurality winner! So, the resulting profile has Angela as the Condorcet winner, Bobbie as the Borda winner, and Carol as the plurality winner.

Observe how this symmetry description introduces a way to decompose profiles into component parts. Some of these components identify the portion where basic assumptions, such as transitive preferences are lost. Others demonstrate subtle biases that vitiate our expectations of voting procedures. This data decomposition makes it easy to construct examples illustrating all possible paradoxes. Conversely, a procedure which is not neutral on these symmetry components must admit paradoxes that raise serious doubt about the validity of the outcome. This means that we should search for procedures that are neutral on these components of bias. The only one is the Borda Count!

### Summary

It is surprising how basic mathematical symmetries lift much of the mystery that for centuries has surrounded election procedures. Certain symmetries identify the doubtful procedures because they destroy basic assumptions that voters are rational; these methods include any satisfying Arrow's IIA assumption, pairwise voting, and so forth. Similarly, a way to resolve Arrow's problem is to extend IIA so the new version monitors whether voters have transitive preferences. When done in a minimal fashion, the Borda Count emerges. Other symmetries identify undesired properties for other procedures; only the Borda Count does not suffer them. Borda would have been surprised to discover how his approach finally has been vindicated! In particular, I suspect he would have been pleased to learn how mathematics support his notions over those of his nemesis Condorcet.