projects.mako.cc - rubyvote/blob - lib/rubyvote/condorcet.rb

   1 # election library -- a ruby library for elections
   2 # copyright © 2005 MIT Media Lab and Benjamin Mako Hill
   3
   4 # This program is free software; you can redistribute it and/or modify
   5 # it under the terms of the GNU General Public License as published by
   6 # the Free Software Foundation; either version 2 of the License, or
   7 # (at your option) any later version.
   8
   9 # This program is distributed in the hope that it will be useful, but
  10 # WITHOUT ANY WARRANTY; without even the implied warranty of
  11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12 # General Public License for more details.
  13
  14 # You should have received a copy of the GNU General Public License
  15 # along with this program; if not, write to the Free Software
  16 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17 # 02110-1301, USA.
  18
  19 #################################################################
  20 ## ==== condorcet.rb ====
  21 ##
  22 ## This file contains Condorcet election methods. Currently this
  23 ## includes a pure condorcet and a CloneproofSSD implementation
  24 ## modeled after the Python-based Debian project election code and
  25 ## that gives the same results in several tested corner cases.
  26 #################################################################
  27
  28 ##################################################################
  29 ## CondorcetVote Classes and SubClasses
  30 ##
  31 ## The CondorcetVote class is subclassed by the PureCondorcetVote and
  32 ## the CloneproofSSDVote classes but should not be used directly.
  33
  34 class CondorcetVote < ElectionVote
  35
  36   attr_accessor :results
  37
  38   def initialize(votes=nil)
  39     unless defined?(@candidates)
  40       @candidates = Array.new
  41       votes.each do |vote_row|
  42         vote_row = vote_row.flatten if vote_row.class == Array
  43         vote_row.each do |vote|
  44           @candidates << vote unless @candidates.include?(vote)
  45         end
  46       end
  47     end
  48     super(votes)
  49     @results = Array.new
  50   end
  51
  52   def tally_vote(vote=nil)
  53
  54     vote.each_with_index do |winners, index|
  55       if vote.flatten.length < @candidates.length
  56         implied_losers = @candidates.select { |c| not vote.flatten.include?(c) }
  57         vote.push(implied_losers)
  58       end
  59       if vote.length - 1 == index
  60         losers = []
  61       else
  62         losers = vote.flatten.last( vote.flatten.length - index - 1)
  63       end
  64
  65       losers.each do |place|
  66         place = [place] unless place.class == Array
  67         place.each do |loser|
  68
  69           winners = [winners] unless winners.class == Array
  70           next if winners.include?(loser)
  71           winners.each do |winner|
  72             @votes[winner] = Hash.new unless @votes.has_key?(winner)
  73             @votes[loser] = Hash.new unless @votes.has_key?(loser)
  74
  75             if @votes[winner].has_key?(loser)
  76               @votes[winner][loser] += 1
  77             else
  78               @votes[winner][loser] = 1
  79             end
  80
  81             # make sure we have a comparable object
  82             @votes[loser][winner] = 0 unless @votes[loser].has_key?( winner )
  83           end
  84         end
  85       end
  86     end
  87   end
  88
  89   def results
  90     if @results.size < 2 && (not @candidates.empty?)
  91       tabulate
  92     end
  93     @results
  94   end
  95
  96   def result
  97     find_only_winner unless @winner
  98     @winner
  99   end
 100
 101   protected
 102
 103   def verify_vote(vote=nil)
 104     vote.instance_of?( Array ) and
 105       vote == vote.uniq
 106   end
 107
 108   def tabulate
 109     find_only_winner unless @winner
 110     until @candidates.empty?
 111       aResult = resultFactory( self )
 112       @results << aResult.winners
 113       filter_out(aResult)
 114     end
 115   end
 116
 117   def find_only_winner
 118     @winner = resultFactory( self )
 119     @results << @winner.winners
 120     filter_out(@winner)
 121   end
 122
 123 end
 124
 125 class PureCondorcetVote < CondorcetVote
 126   def resultFactory(init)
 127     PureCondorcetResult.new(init)
 128   end
 129 end
 130
 131 class CloneproofSSDVote < CondorcetVote
 132   def resultFactory(init)
 133     CloneproofSSDResult.new(init)
 134   end
 135
 136 end
 137
 138
 139 ##################################################################
 140 ## CondorcetResult Classes and SubClasses
 141 ##
 142 ## The CondorcetResult class is subclassed by the PureCondorcetResult
 143 ## and the CloneproofSSDResult classes but should not be used
 144 ## directly.
 145
 146 class CondorcetResult < ElectionResult
 147   attr_reader :matrix
 148
 149   def initialize(voteobj=nil)
 150     unless voteobj and voteobj.kind_of?( CondorcetVote )
 151       raise ArgumentError, "You must pass a CondorcetVote array.", caller
 152     end
 153     super(voteobj)
 154     @matrix = voteobj.votes
 155   end
 156
 157   def victories_and_ties
 158     victors = Array.new
 159     ties = Array.new
 160     victories = Hash.new
 161     candidates = @matrix.keys.sort
 162
 163     candidates.each do |candidate|
 164       candidates.each do |challenger|
 165         next if candidate == challenger
 166         diff = @matrix[candidate][challenger] - @matrix[challenger][candidate]
 167         if diff > 0
 168           victors << [candidate, challenger, diff]
 169         elsif diff == 0 && ties.include?([challenger, candidate]) == false
 170           ties << [candidate, challenger]
 171         end
 172       end
 173     end
 174
 175     victors.each do |list|
 176       if victories.has_key?(list[0])
 177         victories[list[0]][list[1]] = list[2]
 178       else
 179         victories[list[0]] = Hash.new
 180         victories[list[0]][list[1]] = list[2]
 181       end
 182     end
 183
 184     return victories, ties
 185   end
 186
 187   protected
 188   def defeats(candidates=nil, votes=nil)
 189     candidates ||= @election.candidates || []
 190     # we're assumign that if there are candidates, there must be at
 191     # least one vote for them
 192     votes ||= @election.votes
 193
 194     defeats = Array.new
 195     candidates.each do |candidate|
 196       candidates.each do |challenger|
 197         next if candidate == challenger
 198         if votes[candidate][challenger] > votes[challenger][candidate]
 199           defeats << [ candidate, challenger ]
 200         end
 201       end
 202     end
 203
 204     defeats
 205   end
 206
 207 end
 208
 209 class PureCondorcetResult < CondorcetResult
 210   def initialize(voteobj=nil)
 211     super(voteobj)
 212     self.condorcet()
 213   end
 214
 215   protected
 216
 217   def condorcet
 218     votes = @election.votes
 219     candidates = @election.candidates
 220
 221     unless votes.length > 0 and candidates.length > 0
 222       return @winners=[]
 223     end
 224
 225     victors = Hash.new
 226     candidates.each do |candidate|
 227       victors[candidate] = Array.new
 228     end
 229
 230     self.defeats.each do |pair|
 231       winner, loser = *pair
 232       victors[winner] << loser
 233     end
 234
 235     victory_margin = 1
 236     while true
 237       winners = @election.candidates.find_all do |candidate|
 238         victors[candidate].length == @election.candidates.length - victory_margin
 239       end
 240       if winners.length > 0
 241         @winners = winners
 242         return @winners
 243       else
 244         victory_margin += 1
 245       end
 246     end
 247   end
 248 end
 249
 250 class CloneproofSSDResult < CondorcetResult
 251   def initialize(voteobj=nil)
 252     super(voteobj)
 253     @winners = self.cpssd()
 254   end
 255
 256   protected
 257
 258   def cpssd
 259     votes = @election.votes
 260     candidates = @election.candidates.dup
 261
 262     def in_schwartz_set?(candidate, candidates, transitive_defeats)
 263       candidates.each do |challenger|
 264         next if candidate == challenger
 265
 266         if transitive_defeats.include?( [ challenger, candidate ] ) and
 267             not transitive_defeats.include?( [ candidate, challenger ] )
 268           return false
 269         end
 270       end
 271       return true
 272     end
 273
 274     loop do
 275
 276       # see the array with the standard defeats
 277       transitive_defeats = self.defeats(candidates, votes)
 278       defeats_hash = Hash.new
 279       transitive_defeats.each { |td| defeats_hash[td] = 1 }
 280
 281       candidates = [candidates] unless candidates.class == Array
 282       candidates.each do |cand1|
 283         candidates.each do |cand2|
 284           unless cand1 == cand2
 285             candidates.each do |cand3|
 286               if not cand2 == cand3 and
 287                   not cand1 == cand3 and
 288                   defeats_hash[[cand2, cand1]] and
 289                   defeats_hash[[cand1, cand3]] and
 290                   not defeats_hash[[cand2, cand3]]
 291                 transitive_defeats << [cand2, cand3]
 292                 defeats_hash[[cand2, cand3]] = 1
 293               end
 294             end
 295           end
 296         end
 297       end
 298
 299       schwartz_set = Array.new
 300       candidates.each do |candidate|
 301         if in_schwartz_set?(candidate, candidates, transitive_defeats)
 302           schwartz_set << candidate
 303         end
 304       end
 305
 306       candidates = schwartz_set
 307
 308       # look through the schwartz set now for defeats
 309       defeats = self.defeats(candidates, votes)
 310
 311       # it's a tie or there's only one option
 312       break if defeats.length == 0
 313
 314       def is_weaker_defeat?( pair1, pair2 )
 315         votes = @election.votes
 316         if votes[pair1[0]][pair1[1]] > votes[pair2[0]][pair2[1]]
 317           return true
 318         elsif votes[pair1[0]][pair1[1]] == votes[pair2[0]][pair2[1]] and
 319             votes[pair1[1]][pair1[0]] > votes[pair2[1]][pair2[0]]
 320           return true
 321         else
 322           false
 323         end
 324       end
 325
 326       defeats.sort! do |pair1, pair2|
 327         if is_weaker_defeat?( pair1, pair2 )
 328           +1
 329         elsif is_weaker_defeat?( pair2, pair1 )
 330           -1
 331         else
 332           0
 333         end
 334       end
 335
 336       votes[defeats[0][0]][defeats[0][1]] = 0
 337       votes[defeats[0][1]][defeats[0][0]] = 0
 338
 339     end
 340
 341     return candidates
 342   end
 343
 344 end