2012/02/08
The Labs.Com Issue_03_Voting
Last update 1999/02/20

TPJ: Issue_03_Voting

This is a collection of programs published by The Perl Journal. You can download all source-code also from TPJ: Programs.
  1. pairwise
  2. pairwise~
  3. finally~
  4. condorcet.pl
  5. More Samples on Voting
Issue_03_Voting
1. pairwise
Download pairwise

 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) th\ 
 at 
 #  stores the pairwise tally results.   
 # 
 #  $self->{'tally'}[$candx][$candy] is the number of votes that $ca\ 
 ndx 
 #  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 ident\ 
 ical 
         # ballots we are considering at this time. 
         my(@votelist)=@{$ballot->{'rankings'}}; 
         foreach $tier (@votelist) {          # For each preference lis\ 
 ted... 
             # 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'}; 
     } 
 } 

Issue_03_Voting
2. pairwise~

Download pairwise~

 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) th\ 
 at 
 #  stores the pairwise tally results.   
 # 
 #  $self->{'tally'}[$candx][$candy] is the number of votes that $ca\ 
 ndx 
 #  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 ident\ 
 ical 
         # ballots we are considering at this time. 
         my(@votelist)=@{$ballot->{'rankings'}}; 
         foreach $tier (@votelist) {          # For each preference lis\ 
 ted... 
             # 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 n\ 
 umber: 
     $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 b\ 
 y 
                                 # 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 b\ 
 e 
     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 o\ 
 f 
     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 busi\ 
 ness, 
 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-- 

Issue_03_Voting
3. finally~

Download finally~

 From robla@eskimo.com Thu Aug  1 05:10:51 1996 
 Date: Thu, 01 Aug 1996 02:06:28 -0700 
 From: Rob Lanphier <robla@eskimo.com> 
 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 res\ 
 t 
 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.  Thi\ 
 s 
    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 fring\ 
 e 
     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: 
  
 <table> 
   <tr><td rowspan=2>2</td><td>Fred Flintstone&\ 
 lt;/td></tr> 
   <tr><td>Wilma Flintstone</td></tr> 
   <tr><td>3</td><td>Barney Rubble</td>&l\ 
 t;/tr> 
   <tr><td>1</td><td>Betty Rubble</td><\ 
 ;/tr> 
 </table> 
 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: 
     <U>No-Show Paradox</U>: The addition of identical ball\ 
 ots with 
     candidate x ranked last may change the winner from another 
     candidate to x. 
     <U>Thwarted-Majorities Paradox</U>: A candidate who ca\ 
 n defeat 
     every other candidate in direct-comparison majority votes may lose 
     the election.  [This is also known as the <i>Condorcet 
     criterion</i>, named after the 18th century election theoris\ 
 t who 
     popularized it.] 
     <U>Multiple-Districts Paradox</U>: A candidate can win\ 
  in each 
     district separately, yet lose the general election in the combined 
     districts. 
     <U>More-is-less Paradox</U>: 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 <i>when everyone votes sincerely</i>.  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 
     <i>the</i> litmus for determining a good pairwise meth\ 
 od. 
     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 electio\ 
 ns) 
 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 defeat\ 
 ed. 
 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 &g\ 
 t; 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) th\ 
 at 
 #  stores the pairwise tally results.   
 # 
 #  $self->{'tally'}[$candx][$candy] is the number of votes that $ca\ 
 ndx 
 #  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 ident\ 
 ical 
         # ballots we are considering at this time. 
         my(@votelist)=@{$ballot->{'rankings'}}; 
         foreach $tier (@votelist) {          # For each preference lis\ 
 ted... 
             # 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 n\ 
 umber: 
     $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 b\ 
 y 
                                 # 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 b\ 
 e 
     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 o\ 
 f 
     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 busi\ 
 ness, 
 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-- 

Issue_03_Voting
4. condorcet.pl

Download condorcet.pl

 #!/usr/local/bin/perl 
 $rcsid='$Id: condorcet.pl,v 0.2 1995/12/31 13:29:33 robla Exp robla $'\ 
 ; 
 # $Log: condorcet.pl,v $ 
 # Revision 0.2  1995/12/31  13:29:33  robla 
 # Added comment capability to vote data 
 # Now truly "Condorcet complient" (thanks Mike O.) 
 # Now handles tie elections correctly (rather than arbitrarily picking\ 
  a winner) 
 # 
 # Revision 0.1.1.1  1995/12/22  04:02:38  robla 
 # Added more comments 
 # 
 # Revision 0.1  1995/12/22  02:46:22  robla 
 # First version.  The tie-breaker still incorrectly calculates worst 
 # defeat by votes for, rather than votes against. 
 # 
 #    condorcet.pl - tallies ranked preference ballots using Condorcet'\ 
 s method 
 # 
 #    This program is free software; you can redistribute it and/or mod\ 
 ify 
 #    it under the terms of the GNU General Public License as published\ 
  by 
 #    the Free Software Foundation; either version 2 of the License, or 
 #    (at your option) any later version. 
 # 
 #    This program is distributed in the hope that it will be useful, 
 #    but WITHOUT ANY WARRANTY; without even the implied warranty of 
 #    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
 #    GNU General Public License for more details. 
 # 
 #    You should have received a copy of the GNU General Public License 
 #    along with this program; if not, write to the Free Software 
 #    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 
 # 
 #    For more information about this program, check out my home page 
 #    at <URL:http://www.eskimo.com/~robla>, or email me (Rob Lan\ 
 phier 
 #    <robla@eskimo.com>) for what the web page doesn't answer. 
 # 
 #    See $helpstring below for more details. 
  
 $helpstring=qq/ 
  
  condorcet.pl - tallies ranked preference ballots using Condorcet's me\ 
 thod. 
  $rcsid 
  Copyright (C) 1995  Rob Lanphier 
  This program is free software; you can redistribute it and\/or modify 
  it under the terms of the GNU General Public License as published by 
  the Free Software Foundation; either version 2 of the License, or 
  (at your option) any later version. 
  
  See source code for more details. 
  
  usage:  perl condorcet.pl [-t] candidate-list ballot-list 
  
  -t    Print the raw tally table. (pair-wise election results) 
  
  candidate-list - contains a two column, comma-separated list of 
                   candidate number and candidate names.  Candidate     
                   numbers can be any non-negative integers of unlimite\ 
 d 
                   size.  For efficiency, numbering should start at zer\ 
 o 
                   and proceed up in increments of one, but this is not 
                   a requirement. 
  ballot-list -    this should be a list of ballots, one per line.  Eac\ 
 h 
                     line should contain a list of candidate numbers 
                   separated by commas. 
  Ballots are not checked for validity, and results may be 
  unpredictable with bad input. 
  
 /; 
  
 if ($ARGV[0] =~ /^-[hH\?]$/) 
 { 
     print $helpstring; 
     exit; 
 } 
 if ($ARGV[0] =~ /^-[tT]$/) 
 { 
     $printtally = 1; 
     shift(@ARGV); 
 } 
 open (CANDLIST, $clistfilename=shift(@ARGV)) || die "can't open $clist\ 
 filename" ; 
 # Load the candidate list 
 while (<CANDLIST>) 
 {    
     if (/(\d+)\s*,\s*(.*)$/)        # If the line starts with a number\ 
  and 
                                     # a comma (they all should)... 
     {                                # Stuff the candidate's name in a\ 
 n 
                                 # array and set a flag in $candvec 
                                 # corresponding to this candidate numb\ 
 er. 
         $candidate[$1]=$2; 
         vec($candvec, $1, 1)=1; 
     } 
 } 
  
 close(CANDLIST); 
  
 open (VOTES, $vlistfilename=shift(@ARGV)) || die "can't open $vlistfil\ 
 ename" ; 
  
  #  Variable "declaration" 
  #  $tally[candx][candy] 
  # 
  #  $tally is a two-dimensional array (ala Perl 5) that stores the 
  #  number of votes that candx received over candy. 
  
 while (<VOTES>) 
 {                                # Boolean vector with a flag set for 
                                 # all "losers" reset with every new 
                                 # ballot.  All are losers until they 
                                 # are listed on a ballot. 
     local($loservec)=$candvec; 
  
     s/#.*$//;                        # Strip comments 
  
     if (/^\D*$/)                # Ignore blank lines. 
     { 
         next; 
     } 
     local(@votelist)=split(/,/, $_); 
     foreach $vote (@votelist)        # For each preference listed... 
     { 
         vec($loservec, $vote, 1) = 0; # Remove the chosen candidate 
                                       # from the loser vector. 
         for ($i = 0; $i<= $#candidate; $i++) # For all candidates..\ 
 . 
         { 
             if(vec($loservec,$i,1)) # If they haven't been listed yet.\ 
 .. 
             { 
                 if(defined($tally[$vote][$i])) # They've been beat by 
                                                # the chosen candidate. 
                 { 
                     $tally[$vote][$i]++; 
                 }    
                 else 
                 { 
                     $tally[$vote][$i]=1; 
                 } 
             } 
         } 
     } 
     $total_vote++; 
 } 
 close(VOTES); 
 # Variable declaration for @results 
 # A two-dimensional array storing election results for each candidate 
 # 
 # Initialize the @results array. 
 for ($i=0;$i<=$#candidate;$i++) 
 { 
     if (vec($candvec,$i,1)) 
     {              
         $results[$i][0]=0;        # Number of victories for $i 
         $results[$i][1]=0;        # Number of ties for $i 
         $results[$i][2]=0;        # Number of defeats for $i 
         $results[$i][3]=0;        # Worst defeat, as measured by 
                                 # total votes against $i 
     } 
 } 
 # Now for the pairwise tally... 
 for ($i=0;$i<$#candidate;$i++) 
 { 
     if (vec($candvec,$i,1)) 
     { 
         for ($j=$i+1;$j<=$#candidate;$j++) 
         { 
             if (vec($candvec,$j,1)) 
             { 
                 if(!defined($tally[$i][$j])) # Initialize the tally 
                                              # array for uninitialized\ 
  value. 
                 { 
                     $tally[$i][$j] =0; 
                 } 
                 if(!defined($tally[$j][$i])) 
                 { 
                     $tally[$j][$i] =0; 
                 } 
                 local($itally)=$tally[$i][$j]; # Votes for candidate 
                                                # number $i 
                 local($jtally)=$tally[$j][$i]; # Votes for candidate 
                                                # number $j 
                 local($x)=($itally <=> $jtally)+1; 
                 local($y)=2-$x; 
                 $results[$i][$x]++; 
                 $results[$j][$y]++; 
                 if($jtally > $results[$i][3]) 
                 { 
                     $results[$i][3]=$jtally; # This is $i's worst defe\ 
 at. 
                 }                         
                 if($itally > $results[$j][3]) 
                 { 
                     $results[$j][3]=$itally; # This is $j's worst defe\ 
 at. 
                 } 
             } 
         } 
     } 
 } 
  
 if (!$printtally)  
 { 
     print "Total votes tallied: $total_vote\n"; 
 } 
 # This is the loop where the winner is calculated.  The winner is 
 # stored in an array to deal with the possibility of a tie, in which 
 # the array grows to accomodate multiple "winners".  God help us if 
 # there is a tie. 
  
 { 
     local($min_worst_defeat)=$total_vote; 
     for ($i=0;$i<=$#candidate;$i++) 
     { 
         if (vec($candvec,$i,1)) 
         {                                 
             if($results[$i][3]<$min_worst_defeat) 
             { 
                 $min_worst_defeat=$results[$i][3]; 
                 @leading_cand_num=($i); # $i is now the hands-down win\ 
 ner, so 
                 # far 
             } 
             elsif($results[$i][3]==$min_worst_defeat) 
             { 
                 push(@leading_cand_num, $i); # $i is tied for the lead 
                                              # with those already in t\ 
 he 
                                              # @leading_cand_num array 
             } 
             if($results[$i][0]==0 && 
                $results[$i][1]==0)        # If they haven't lost or ti\ 
 ed 
                                           # any elections, they win. 
             { 
                 @leading_cand_num=($i); 
                 print "Smoked 'em\n"; 
                 last;                # That's all she wrote. 
             } 
         } 
     } 
 } 
 if ($printtally)  
 { 
     # Print out the raw tally table. 
     for ($i=0;$i<=$#candidate;$i++) 
     { 
         if (vec($candvec,$i,1)) 
         {              
             print"\t$candidate[$i]"; 
         } 
     } 
     print "\n"; 
     for ($i=0;$i<=$#candidate;$i++) 
     { 
         if (vec($candvec,$i,1)) 
         {              
             print"$candidate[$i]"; 
             for ($j=0;$j<=$#candidate;$j++) 
             { 
                 if(vec($candvec,$j,1)) 
                 { 
                     print"\t$tally[$j][$i]"; 
                 } 
             }         
             print "\n"; 
         } 
     } 
     # End of raw tally table printout. 
 } 
 else 
 { 
     # Now for the moment we've been waiting for.  This is where we 
     # announce the winner(s) 
     if($#leading_cand_num==0)        # i.e. if there is only one 
                                      # leading_cand_num, they win 
     { 
         print"The winner is $candidate[$leading_cand_num[0]]\n\n"; 
     } 
     else                        # Oh, hell... 
     { 
         print"There has been a tie\nThe winners are:\n"; 
         for ($i=0;$i<=$#leading_cand_num;$i++) 
         { 
             print"The winner is $candidate[$leading_cand_num[$i]]\n"; 
         } 
         print"\n"; 
     } 
     print "Pairwise elections won-lost-tied:\n"; 
      
     for ($i=0;$i<=$#candidate;$i++) 
     { 
         if (vec($candvec,$i,1)) 
         {              
             if(!defined($results[$i][0])) 
             { 
                 $results[$i][0]=0; 
             } 
             if(!defined($results[$i][1])) 
             { 
                 $results[$i][1]=0; 
             } 
             if(!defined($results[$i][2])) 
             { 
                 $results[$i][2]=0; 
             } 
             print "$candidate[$i] $results[$i][2]-$results[$i][0]-$res\ 
 ults[$i][1]"; 
             print " (votes against in worst defeat (or closest victory\ 
 ): "; 
             print "$results[$i][3])\n"; 
         } 
     } 
 } 

Issue_03_Voting
5. More Samples on Voting

  • Issue_03_Voting

                                                                                                                                   

Hipocrisy of the finest: "I agree that no single company can create all the hardware and software. Openness is central because it's the foundation of choice."
-- Steve Balmer (Microsoft) blaming Apple regarding iPhone, February 18, 2009

Last update 1999/02/20

All Rights Reserved - (C) 1997 - 2009 by The Labs.Com
Top of Page

The Labs.Com