From robla@eskimo.com Thu Aug 1 05:10:51 1996 Date: Thu, 01 Aug 1996 02:06:28 -0700 From: Rob Lanphier Reply-To: robla@eskimo.com X-Mailer: Mozilla 3.0b5aGold (Win95; I) Mime-Version: 1.0 To: orwant@media.mit.edu Cc: landerso@ida.org, seppley@alumni.caltech.edu, dfb@bbs.cruzio.com Subject: Final Draft (sans figures) Content-Type: multipart/mixed; boundary="------------45A665BC72CD" This is a multi-part message in MIME format. --------------45A665BC72CD Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hi Jon, Margaret will be working on some figures tomorrow, but I think the rest of this is a done deal. I'm more than willing to do more editing as needed (and I could continue to work on this forever and still not be satisfied), but I at least have something here that I've run the spell checker over :) Bruce, Steve, and Mike, thank you for all of your help. I think this is a much stronger article for it. -- Rob Lanphier robla@eskimo.com http://www.eskimo.com/~robla --------------45A665BC72CD Content-Type: text/plain; charset=us-ascii; name="pjarticle.txt" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="pjarticle.txt" Perl, Politics, and Pairwise Voting: Perl as the Activist's Friend The U.S. Presidential elections once again draw near, and once again we see that it will come down to one of two men, each representing the two major U.S. political parties. So it goes with the two-party system. What is it that makes the two-party system a two-party system? The two party system is a direct consequence of plurality voting, the predominant form of balloting used in the United States where the highest vote getter wins an election. This relationship between the two-party duopoly and plurality voting is known as "Duverger's Law", after the 20th century political scientist who had the guts to call it a "law" (Riker, 1982). Duverger's Law has some disturbing consequences which leaves many voters dissatisfied with the status quo. Politicians will always claim to "feel our pain", but at least in the U.S., two-party skeptics abound. Recent polls have shown that nearly 60% of the American people would support the formation of a new major party (Barrett, 1996). The main reason Duverger's Law rings so true is that we have a binary ballot that groups people into two categories: a winner and one or more losers. The resulting dilemmas that voters are faced with in siding with a winner manifest themselves several ways: * Because you can't please all of the people all of the time, it is in politicians' best interest to build divisions, and then build consensus among slightly over 50% of the electorate, giving them roughly 49% of the electorate to use as a convenient scapegoat. * Along the same line, specific-issue-oriented voters are encouraged to ally with just enough people to give themselves a majority. This gives politicians a "path of least resistance" toward which they can target their campaigns. * Ultimately, since voters are powerless to state any more than one preference, they are forced to take sides even when they stand in the middle. The bottom line is that the ballot doesn't let people state what they really feel. They can only make a crude approximation of their preference, and then hope that somehow, the politicians will "get it". Voters are often forced into a choice between the lesser of two evils. They may not like either candidate, but rather than make a principled stand and vote for none of the above or perhaps a lesser known candidate with no chance of winning, they make the strategically correct decision and vote. Have the strategy problems above ever demonstrably taken the electorate where it didn't want to go? Yes it has. Abraham Lincoln is widely considered to be the best U.S. president in history. Yet, for better or worse, it was largely a function of the strategic error of his foes that he won the gnarled four-way 1860 election with the smallest plurality of any president (39% of the vote), and the result of that election led to U.S. Civil War. (However, the numbers probably would have been substantially different had slaves the right to vote). In our century, the most famous three-way strategy dilemma was when Theodore Roosevelt, angry from losing the Republican nomination, split the Republican Party vote for their 1912 Nominee (and incumbent president) Howard Taft by creating the Bull Moose Party. This allowed Woodrow Wilson to win handily with a mere 42% of the vote (as opposed to Roosevelt's 27% and Taft's 23%). This inspired many states to create "sore loser" laws that keep candidates who fail to win major party nominations from forming third parties, and by making third-party ballot access much more difficult. Even recently, presidential politics were affected by the three-way split. In 1966, Thomas Finan and Carlton Sickles, two relatively liberal candidates from the left-of-center state of Maryland split the vote within the state Democratic party nominations for governor. This led to conservative George P. Mahoney winning the Democratic nomination, only to be beaten by Spiro Agnew, who went on to be Vice President under Richard Nixon. When Agnew resigned in 1973, it opened the door for Gerald Ford to be appointed Vice President, and then later President. A tenuous connection to the presidency, albeit, but a very real one, nonetheless. (Anderson, 1994) Much more serious threats to democracy have been the candidacies that "might have been". Since our system discourages anything but a two-candidate race, we seldom see more. Rosenstone, Behr, and Lazarus point out that that few qualified candidates would run under a third-party label because of the disadvantages they are often faced with (1984). For instance, they point out the bias that third-party candidacies face in the media by quoting James M. Perry of The Wall Street Journal: We base [our decision] on the simple proposition that readers don't want to waste their time on someone who won't have a role in the campaign. We're not going to run a page-one spread on a fringe candidate. We don't have a multiparty system. Until we do, nobody's going to cover these candidates. (Rosenstone, et. al, 1984). With such biases built into the system, it is little wonder that third- party candidates can't gain the critical mass of support necessary to become a credible threat. A pragmatic, intelligent potential candidate might look at the seemingly insurmountable odds and not run as a third-party candidate. Thus, the dearth of credible third-party candidates becomes the self-fulfilling prophecy, and the two-party duopoly maintains control of the system. The Preference Ballot The key to breaking this lock is to allow voters the ability to vote for candidates regardless of their perceived odds of winning. To do this, we must expand the power of the ballot. This can be done many ways, but the method that I will discuss here is the ranked ballot, or "preference ballot" as shown below:
2Fred Flintstone
Wilma Flintstone
3Barney Rubble
1Betty Rubble
The great thing about preference votes is that preference votes express a voter's thoughts much better than a vote-for-one ballot, allowing them to "bargain for a compromise" should their top choice not be very popular. This allows people greater flexibility in casting protest votes, while not throwing the election to the evilest candidate (not that Wilma Flintstone is evil; this is just an example). The ranked ballot does a great job at limiting strategy, but it doesn't eliminate it completely, no matter which way you count it. Political scientists have debated the relative merits of ranked ballots for years, and many of the discussions have centered around Arrow's Impossibility Theorem. Impossibility Theorems Political scientists have been debating for some time now about whether or not it's even possible to come up with a way to tally preference votes. Most of the debate started with Arrow's Impossibility Theorem, which claims that any system where people are allowed to freely and exactly list their preferences has a major defect in it. Arrow proves this by showing a series of conditions for fairness, not all of which may be satisfied simultaneously. Arrow's criteria are a bit too complicated to be easily summarized here, but other mathematicians have tweaked and fiddled with the conditions, and have come up their own sets of conditions. Fishburn and Brams (1983) came up with a particularly concise set, which are listed below: No-Show Paradox: The addition of identical ballots with candidate x ranked last may change the winner from another candidate to x. Thwarted-Majorities Paradox: A candidate who can defeat every other candidate in direct-comparison majority votes may lose the election. [This is also known as the Condorcet criterion, named after the 18th century election theorist who popularized it.] Multiple-Districts Paradox: A candidate can win in each district separately, yet lose the general election in the combined districts. More-is-less Paradox: If the winner were ranked higher by some voters, all else unchanged, then another candidate might have won. Fishburn and Brams maintain in their 1983 paper that at least one of these four paradoxes will be possible in any election method that uses a ranked ballot. One may make the case that since all voting systems are vulnerable to at least one of these paradoxes, that a perfect system doesn't exist. However, there are those that question just how reasonable satisfying all of possible criteria are, and thus question the pragmatic value of this line of reasoning. (Anderson, 1994). In preference voting as in anything else, it's not going to be possible to please all of the people all of the time. This means we are stuck with the task of merely minimizing the sticking points rather than pursuing the holy grail of a perfect system. There are many (myself included) who believe that we can reduce the flaws to rare circumstances. The Borda Method This is probably the best known method within the United States for tallying ranked ballots. It is used by the Associated Press and the United Press International to determine the champions in NCAA college sports. Sports writers or coaches are asked to rank the 25 best teams, and then the top team on each ballot gets 25 votes, the second team gets 24, and so on. The top vote getters are ranked by votes received. This relatively simple method is easy to understand, hence, its appeal. However, it discourages people from ranking anything but their top preference, thus making it difficult to derive compromise candidates from their vote. Consider a three way election between Joe Left, Sally Middle, and Martha Right. I will use this example to describe an election where a reasonable compromise (Sally Middle) exists between two somewhat popular extremes. Given that the seat in question must go to one person and only one, it seems reasonable that the middle candidate be chosen. Let's say the sincere wishes of these voters are shown in Figure A: Insert rl-FigA.gif here: Figure A If Borda's method is used, where the first place candidate on the ballot receives two points per ballot, and the second place candidate receives one point per ballot, then the following result will occur: Borda Points Awarded Joe Sally Martha Left Middle Right ================================ +---------------------+ 40 | Joe Left | ballots | 2 Sally Middle | 40 80 | 1 Martha Right | +---------------------+ +---------------------+ 9 | Joe Left | ballots | 1 Sally Middle | 18 9 | 2 Martha Right | +---------------------+ +---------------------+ 16 | 2 Joe Left | ballots | 1 Sally Middle | 16 32 | Martha Right | +---------------------+ +---------------------+ 35 | 1 Joe Left | ballots | 2 Sally Middle | 70 35 | Martha Right | +---------------------+ =============================== 86 125 89 Figure B The good news here is that Borda's method does indeed choose the compromise when everyone votes sincerely. However, strategically speaking, if Martha Right supporters have a good idea of what the poll numbers are, they can (and should) drop Sally Middle off of their ballot. If all Martha Right supporters do this, they cause a 40 point drop in Sally Middle's Borda score, causing Martha Right to win. Even if some Martha Right supporters don't do this, it is likely many Joe Left supporters will do the same thing in absence of 100% accurate polling numbers. (i.e. if they think that Joe Left has a shot at winning.) Thus Borda picks a compromise when voters naively list all of their preferences, but fails when voters catch on to how to "game" the system. The biggest problem with Borda's method is that it fails to meet the "thwarted majorities" criterion that Fishburn and Brams listed. This is arguably one of the most important criterion in determining the winner in a single-winner method, and thus, many examples like the one above can be created. The "Hare" Method The Hare method is perhaps the best known method for tabulating "preference ballots" outside of the United States. It was invented in 1860 by Thomas Hare. It's used in Australia and Ireland for single-office elections. Preference ballots are tabulated counting only the first-place candidate on each ballot. The candidate with the fewest number of first place votes is eliminated, and these ballots are transferred to their second place counterparts. The Hare method is a popular way of eliminating primaries and allowing people to vote for potentially unpopular alternatives to the two "major" candidates without fear of "wasting" one's vote. It does a pretty good job of eliminating strategy and in many ways is a substantial improvement over winner-takes-all. Using Hare to tally the results from Figure A, we tally the first choices to find that Martha Right receives 40% of the vote, Joe Left receives 35% of the vote and Sally Middle is eliminated with only 25% of the vote. The votes for Sally Middle are redistributed based on the second choice of those voters and Joe Left then wins with 51% of the vote. Thus, Hare falls short when considering popular compromises, such as Sally Middle, also because it fails the Condorcet criterion. Pairwise Election Methods Under a class of election methods known as "pairwise" methods the election above would result in a different winner. The relative election results of every possible combination of two candidates is tallied and the winner of every relevant pairwise election is declared winner of the overall election. In the above example, the results of the pairwise elections would be as follows: Joe Left (51%) vs Martha Right (49%) Sally Middle (60%) vs Martha Right (40%) Sally Middle (65%) vs Joe Left (35%) Sally Middle beats both Joe Left and Martha Right, and therefore wins the election overall. What distinguishes the different pairwise election methods from one another is how they deal with circular preferences. A circular preference is one where the outcome results in one candidate defeating another who in turn defeats our original winner. This isn't necessarily a flaw in pairwise systems. One may say that this is a sign that the electorate is ambivalent about who should be the winner. Some theorists, such as Charles Dodgson (a.k.a. Lewis Carroll, author of _Alice in Wonderland_), claim that if a single winner can't be found, then the election should be called off (Levin and Nalebuff, 1995). Nonetheless, many pairwise methods have been designed to deal with this problem. This is a list of descriptions of pairwise elections, and how the various methods deal with that case: * Condorcet's Method Condorcet's method is probably the most well known of these methods. Each voter's list is used to simulate how that voter would have voted in pairwise elections between each of the candidates listed on the ballot, and between those listed on the ballot and those that aren't. Separate tallies of every possible two-way election are kept, and the winner is the candidate that wins all two-way elections. Circular preferences are resolved in Condorcet's method by choosing the candidate whose largest pairwise defeat is the smallest, as measured by how many voters explicitly voted for another candidate over said candidate. The reason why many election reformers prefer this method is that, under most plausible circumstances, it solves the "lesser of two evils" problem described above, which many consider to be the litmus for determining a good pairwise method. However, as Bruce Anderson, a mathematician for the Institute for Defense Analyses notes, in presumably rare circumstances, it may produce unexpected results. * Smith's Method Smith's Method isn't so much pairwise tie breaker as it is a method of determining which candidates should qualify to be in a tie-breaker. The "Smith Set" is the smallest non-zero set of candidates who beat all the candidates outside the set in all pairwise elections. Not all pairwise methods will pick a member of the Smith Set (most notably, Condorcet's method) yet intuitively, one would hope that the winner is picked from this set. Smith's method, therefore, makes a good precondition to a tie-breaker such as Condorcet's. * Copeland's Method Copeland's Method computes the winner of the election by counting the number of pairwise wins, losses, and ties for each candidate. The candidate with the best "record" wins the election, much in the same way that a sports team with the best record gets the top seed in that sport's playoffs. The easy analogy to sports makes this method much easier to explain and comprehend than other methods. One problem with Copeland's Method, much like Smith's method, is prone to ties, and so is often paired with another tie breaker. Also, it is vulnerable to a problem where if there are three parties that are locked in a three-way tie, the party that has the most candidates on the ballot will probably have the winning candidates. This is because they win the most pairwise matchups, even though many of their victories will come from intraparty matchups. This may encourage parties with sufficient funds to run very large numbers of similar candidates in order to skew the election in their favor. There are several other methods that exist for choosing a winner in a preference balloted election, many of which provide a defensible set of criteria which they satisfy. For those of us trying to educate people on alternative election methods, our goal has been to come up with the most important criterion and find the election method which best meets those criteria. What's this got to do with Perl? For many of us who aren't mathematicians by trade, it becomes difficult to debate the relative merits of the different methods without a way of visualizing some examples. The solution was to write a program which shows the data in an easy to understand format. Now it's time to do a little preaching to the choir. I chose to write this program in Perl for several reasons, many of which are all too familiar to Perl affectiondos. However, they bear repeating in the context of programs for elections: * Perl is freely available, with source code - This is a particularly crucial feature for something that may serve in the public sphere. Though there are relatively few voters with the knowledge or initiative to dig down into the source code, there is a certain peace-of-mind that can be derived from knowing that anyone can dig into the underbelly of this vote-counting machine at any time (or pay for someone to do it on their behalf.) * Perl is available on many platforms - Since Perl is available on so many platforms, very few people with a computer are shut out from using it. This means election results can be verified on a very wide range of computers. Having the source available also ensures that it will be possible to port it to new platforms as they become available. * Limitless arrays - Since array sizes don't need to be predetermined, I was able to easily write this such that it will accept as many candidates and votes as the host computer will allow. * CGI Standard - CGI programming has become today's standard in cross-platform GUI development, and Perl is the standard for writing CGI programs. Using HTML tables made this task so much easier, since most web browsers that support tables can be counted on to display the information produced by my program clearly. * Speed of development - My initial prototype really wasn't that tough to write, and constituted very little source code. The current version is much larger, but it is still quite manageable. I relied pretty heavily on Perl 5 when I wrote this program. This is because Perl 5 supports two-dimensional arrays, something that I really needed for storage of the pairwise election results. The Algorithms Before I talk about Perl specifically, I though I should explain the algorithm that I'm implementing with this program. Here is a sample field of candidates: A-John Anderson B-Jerry Brown C-Bill Clinton D-Bob Dole E-Dwight Eisenhower F-Steve Forbes I create an NxN matrix, where N is the number of candidates in the field (6x6, in the case above). The computation of this matrix is stage one of two stages to compute the winner. The matrix consists of how many votes the x coordinate candidate received over the y coordinate candidate. So, [A, B] is the number of votes John Anderson received over Jerry Brown. [B, A] is the number of votes Jerry Brown received over John Anderson. Each ballot is tallied by determining the pairwise result of the ballot. So, if someone ranks their ballot: A, B, C, E, D, F ...then I increment [A,B], [A,C], [A,E], [A,D], [A,F], [B,C], [B,E], [B,D], [B,F], [C,E], [C,D], [C,F], [E,D], [E,F], and [D,F], since this is how the voter would have voted in each pairwise election, given their ranked ballot. This assumes, of course, that the voter's preferences are transitive, i.e. if they prefer A over B and B over C, they will prefer A over C. The ranked ballot lets us get away with some shorthand that simplifies the process for the voter greatly, and insures a certain consistency in their ballot. The second stage computation involves using the matrix to determine the pairwise winners. Each complementary matchup is evaluated, and the winner receives one point in his/her "win" column, and the loser receives one point in his/her "loss" column. If the simulated pairwise election is a tie, both receive one point in the "tie" column. Here is a possible outcome: Wins Losses Ties E 5 0 (Our deceased former president beats everyone in separate pairwise elections) A 4 1 (A loses to E, but beats everyone else) B 3 2 (B loses to A and E) C 1 3 1 (C loses to A, E and B, and ties D) D 1 3 1 (D loses to A, E and B, and ties C) F 0 5 (F loses in all elections) This is a clean pairwise victory for Eisenhower. If no candidate emerges unscathed by a pairwise defeat or tie, an alternative method of calculating the winner involves finding the candidate whose worst pairwise defeat was the smallest. For instance, lets modify the table above: Wins Losses Ties E 3 3 (E loses to C, D, and F) A 4 2 (A loses to E and D) B 3 3 (B loses to F, A, and E) C 3 3 (C loses to A, E and B) D 3 3 (D loses to A, F and B) F 2 4 (F loses to A, B, C, and D) This is where pairwise methods start to differ. Copeland's method would select A (John Anderson) as the winner, since he has the most wins. In order to calculate the winner in a Condorcet election, it is then necessary to look at the matchups where each candidate was defeated. Let's say we are talking about a 1000 vote election. The table below shows the losses for each candidate: E (495, 505) (492, 508) (474, 526)* A (491, 509) (482, 518)* B (482, 518) (476, 524)* (492, 508) C (474, 526)* (488, 512) (490, 510) D (497, 503) (491, 509)* (493, 507) F (482, 518) (481, 519) (477, 523)* (498, 502) * Worst defeat In this election, D (Bob Dole) has the smallest "worst defeat" with 509 votes against him. Therefore, he would win using Condorcet's method. This is true in spite of the fact that A lost fewer elections, and in fact beat D in a pairwise election. The theory behind this is that Marquis de Condorcet thought it appropriate to ask the question "Given that there is no candidate who a majority of the electorate would pick over any other candidate, who is the candidate that a plurality chooses over any other candidate?" No solution to this quandary is going to be particularly satisfying, but many would argue Condorcet's tie-breaker works about as well as any when trying to avoid a new election to find a winner. The Ballot: On the election-methods-list (a mailing list where election methods are discussed; see the end of the article for more information), an ASCII notation evolved that works pretty well as shorthand for expressing a bundle of ballots. I've extended that shorthand to make it easily implemented in Perl. We start off associating candidates with an integer by creating a two-column, comma separated list of candidate numbers and candidates. Figure C shows an example of this. 1,Joe Left 2,Sally Middle 3,Martha Right 4,Bertha Up 5,George Down Figure C Parsing that portion is trivial. What becomes a bit more interesting is parsing the next portion. This consists of a lists of candidate numbers separated by greater-than signs (">") when there is a preference, and equal signs ("=") when there isn't. For example, let's look at the ballot in figure D: This ballot: maps to this line: +---------------------+ | Joe Left | | 3 Sally Middle | | 1 Martha Right | 3 > 4 = 5 > 2 | 2 Bertha Up | | 2 George Down | +---------------------+ Figure D Given the associations defined in Figure C and the ballot in Figure D, the line representing this ballot would be encoded as "3 > 4 = 5 > 2", i.e. 3 preferred to 4 or 5 preferred to 2, or Martha preferred to Bertha or George preferred to Sally (and Joe Left an implied last). This value can optionally be prepended by a quantity of voters who voted in that way. 40 ballots: map to this line: +---------------------+ | Joe Left | | 3 Sally Middle | | 1 Martha Right | 40: 3 > 4 = 5 > 2 | 2 Bertha Up | | 2 George Down | +---------------------+ Figure E For example, coding the example in Figure A, we arrive at the following: 40: 3 > 2 9: 2 > 3 16: 2 > 1 35: 1 > 2 Now for the Perl to do it. I'm sure I'll hear of ways to condense this down to one really simple line, but even the snippet below isn't too bad: my(@votelist)=(); foreach $tier (split(/>/, $ballotstring)) { my(@foo)=split(/=/, $tier); push(@votelist,\@foo); } This relies on Perl 5's ability to create lists of lists, and creates a structure that is an ordered list of tiers, with each tier consisting of equally-ranked candidates. This structure is stored in an object, along with a quantity in cases where it is specified. The Pairwise Engine The code segment below shows how simple it is to implement the pairwise vote in Perl. This code sample below is the function that calculates the pairwise tally: sub pairwise_tally { my ($self, $votelist)=@_; # $self is an object (ala Perl 5) that stores all basic pairwise # election data # # @self->{'tally'} is a two-dimensional array (also ala Perl 5) that # stores the pairwise tally results. # # $self->{'tally'}[$candx][$candy] is the number of votes that $candx # received over $candy. # # $votelist is a string that is essentially a raw text file that # contains all of the ballots. for(split(/\n/,$votelist)) { # $loservec-a boolean vector with a flag set for all "losers" # reset with every new ballot. All are losers until they are # listed on a ballot. my($loservec)=$self->{'candvec'}; # Parse ballot. Skip if no ballot is returned. (!(my($ballot)=new ballot_obj($self, $_))) && next; # @{$ballot->{'rankings'}} is an array of integers # representing the candidates this voter (or voters) voted # for, in order of preference. # In addition, $ballot->{'quantity'} is the number of identical # ballots we are considering at this time. my(@votelist)=@{$ballot->{'rankings'}}; foreach $tier (@votelist) { # For each preference listed... # Remove the chosen candidate(s) from the loser vector. foreach $peer (@{$tier}) { vec($loservec, $peer, 1) = 0; } # For all candidates... for ($i = 0; $i<= $#{$self->{'candidate'}}; $i++) { # If said candidate hasn't been listed yet... if(vec($loservec,$i,1)) { # ...they've been beat by the chosen candidate. # Increment their "votes for the other guy" # counter by the appropriate number of ballots foreach $peer (@{$tier}) { if(defined($self->{'tally'}[$peer][$i])) { $self->{'tally'}[$peer][$i] +=$ballot->{'quantity'}; } else { $self->{'tally'}[$peer][$i] =$ballot->{'quantity'}; } } } } } $self->{'total_vote'}+=$ballot->{'quantity'}; } } Note that what is great about this is that I don't have to pre-declare the size of $self->{'tally'}, the array in which I'm storing the pairwise results. This makes it possible to have as many candidates as the host computer will allow, without predeclaring a ridiculously large array or creating my own dynamic structure. This keeps the code relatively simple (though, admittedly, the quasi-object oriented stuff I'm doing makes it more complex to read a chunk out of context). The next stage involves figuring out the winners. For this I create what is in essence a database of the candidates, with separate fields denoting the number of wins, losses, ties, and worst defeat, as measured by total number of votes against that candidate. Sadly, I wasn't feeling particularly programmer friendly the day I was writing this, and so I made a goofy two-dimensional array rather than an associative array or one-dimensional array with better names. Fortunately, the code below isn't too difficult to grok. Here is the meaning of each of the fields, where $i is the candidate number: $edata->{'results'}[$i][0] # Number of defeats for $i $edata->{'results'}[$i][1] # Number of ties for $i $edata->{'results'}[$i][2] # Number of victories for $i $edata->{'results'}[$i][3] # Worst defeat, as measured by # total votes against $i All pairwise tallies are considered as this is filled in. This gives us the data we need to calculate the Condorcet, Smith, and Copeland winners. I'll leave it to you to fetch the code if you want to see how all of the methods are calculated, but to give you a taste, here's the code for calculating the Copeland winners: sub rank_copeland { my($self, $edata)=@_; # A Copeland score is computed by doubling the number of victories # and adding the number ties a candidate received. my(@copeland_rankings)=sort {-(($self->{'results'}[$a][2]*2 + $self->{'results'}[$a][1]) <=> ($self->{'results'}[$b][2]*2 + $self->{'results'}[$b][1]))} $edata->candnum_array; $self->{'copeland_rankings'}=\@copeland_rankings; } Passing an anonymous function to the sort routine, I'm able to quickly get a listing of the candidates in order of their Copeland scores, picking the winners off of the top. Using CGI to Spit It All Out The best thing about using Perl is that, in combination with CGI, it's a piece of cake to generate nice looking output, even with copious amounts of complicated data. Given the ballots in Figure A, I'm able to generate the following output from my program. Insert Figure F The really great news about this program is that I do have it installed on a publicly available web server, and so you don't need to try to set it up yourself to actually see what it does for yourself. Just browse to the following URL: http://www.eskimo.com/~robla/politics/condorcet.html There is still plenty of work to be done with this program. * A much more user-friendly front end would be really nice. * A "voting booth" program could be written to generate data for use with this program. * There are also many common election methods out there that could be implemented along with this program for comparison reasons. Hare and Borda functions, for example, would be great to compare with Condorcet, Copeland, and Smith. * It would also be nice to compute not just the winner, but a list of winners, in order of preference, for each election method. * A future version could allow one to combine methods view their properties. For example, a method very popular on the election-methods-list is Smith//Condorcet (compute the Smith winner, and break ties using Condorcet). An interface for arbitrarily chaining these methods together would be great. Random Thoughts Versatile and robust election systems have applications beyond the traditional role of government. Local elections, local decision making, and shareholder elections are all obvious applications for such creations. Perhaps there is a role for election methods in computer science or specifically artificial intelligence (for instance, one could imagine a genetic algorithm that generates a pool of voters who submit "preference ballots" to make decisions). Sadly, our education system, rather than teaching us anything about good decision-making methods, indoctrinates us into believing that the American system is the finest in the world and need not be questioned. The vote-for-only-one ballot would be okay if there were only one issue spectrum and only two points of view, but society is a bit more complex than that. Many pundits and armchair activists talk about how the American system of politics is broken, and then can only offer up ways of restricting "the bad guys" as a solution to the problems, be the bad guys big business, labor unions, or special-interest coalitions. Yet few people are actually really putting the system itself under scrutiny. This is a shame, because we really should be considering the consequences of having such a simplistic feedback mechanism to our government. References Anderson, Lowell Bruce, "Voting Theory". From _Handbooks in OR & MS, Vol.6_ editors S.M. Pollock, et al. Elsevier Science B.V., 1994. Barrett, Laurence I., "Give Me Your Tired Parties." AllPolitics. March 1, 1996 (http://allpolitics.com/news/email/9603/01/index.shtml) Fishburn, Peter C. and Steven Brams, "Paradoxes of Preferential Voting." Mathematics Magazine, Vol. 56, No. 4, Sept. 1983, p. 207-214. Levin, Jonathan and Barry Nalebuff, "An Introduction to Vote-Counting Schemes." The Journal of Economic Perspectives. Vol. 9, No. 1, p. 3-26, Winter 1995. Niemi, Richard G. and William H. Riker, "The Choice of Voting Systems." Scientific American. Vol. 234, No. 6, p. 21-27. Riker, W.H., "The Two-party System and Duverger's Law: An Essay on the History of Political Science." The American Political Science Review. Vol. 76, p. 753-766, 1982. Sites * The Condorcet's Method Home Page (http://www.eskimo.com/~robla/politics/condorcet.html) This is a home page that I put together from various pieces I've found on the 'net, and includes programs written by other people in other computer languages. * The Election Methods Mailing List (http://www.eskimo.com/~robla/cpr/election-methods.html) This list discusses the technical details of election methods. It involves the sort of gritty details this article covers. Much of the work above owes a huge debt of gratitude to the members of this list (special thanks to Mike Ossipoff, Steve Eppley, and Bruce Anderson). * The Center for Voting and Democracy (http://www.igc.apc.org/cvd) This is an organization which is working toward all forms of election reform. Though their primary focus has been on advancing proportional representation, they do advocate single-winner reform as well. --------------45A665BC72CD--