projects.mako.cc - selectricity/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   def initialize(votes=nil)
  37     unless defined?(@candidates)
  38       @candidates = Array.new
  39       votes.each do |vote_row|
  40         vote_row = vote_row.flatten if vote_row.class == Array
  41         vote_row.each do |vote|
  42           @candidates << vote unless @candidates.include?(vote)
  43         end
  44       end
  45     end
  46     super(votes)
  47   end
  48
  49   def tally_vote(vote=nil)
  50
  51     vote.each_with_index do |winners, index|
  52       if vote.flatten.length < @candidates.length
  53         implied_losers = @candidates.select { |c| not vote.flatten.include?(c) }
  54         vote.push(implied_losers)
  55       end
  56       if vote.length - 1 == index
  57         losers = []
  58       else
  59         losers = vote.flatten.last( vote.flatten.length - index - 1)
  60       end
  61
  62       losers.each do |place|
  63         place = [place] unless place.class == Array
  64         place.each do |loser|
  65
  66           winners = [winners] unless winners.class == Array
  67           next if winners.include?(loser)
  68           winners.each do |winner|
  69             @votes[winner] = Hash.new unless @votes.has_key?(winner)
  70             @votes[loser] = Hash.new unless @votes.has_key?(loser)
  71
  72             if @votes[winner].has_key?(loser)
  73               @votes[winner][loser] += 1
  74             else
  75               @votes[winner][loser] = 1
  76             end
  77
  78             # make sure we have a comparable object
  79             @votes[loser][winner] = 0 unless @votes[loser].has_key?( winner )
  80           end
  81         end
  82       end
  83     end
  84   end
  85
  86   protected
  87
  88   def verify_vote(vote=nil)
  89     vote.instance_of?( Array ) and
  90       vote == vote.uniq
  91   end
  92 end
  93
  94 class PureCondorcetVote < CondorcetVote
  95   def result
  96     PureCondorcetResult.new(self)
  97   end
  98 end
  99
 100 class CloneproofSSDVote < CondorcetVote
 101   def result
 102     CloneproofSSDResult.new(self)
 103   end
 104 end
 105
 106
 107 ##################################################################
 108 ## CondorcetResult Classes and SubClasses
 109 ##
 110 ## The CondorcetResult class is subclassed by the PureCondorcetResult
 111 ## and the CloneproofSSDResult classes but should not be used
 112 ## directly.
 113
 114 class CondorcetResult < ElectionResult
 115   attr_reader :matrix
 116
 117   def initialize(voteobj=nil)
 118     unless voteobj and voteobj.kind_of?( CondorcetVote )
 119       raise ArgumentError, "You must pass a CondorcetVote array.", caller
 120     end
 121     super(voteobj)
 122     @matrix = voteobj.votes
 123   end
 124
 125   def victories_and_ties
 126     victors = Array.new
 127     ties = Array.new
 128     victories = Hash.new
 129     candidates = @matrix.keys.sort
 130
 131     candidates.each do |candidate|
 132       candidates.each do |challenger|
 133         next if candidate == challenger
 134         diff = @matrix[candidate][challenger] - @matrix[challenger][candidate]
 135         if diff > 0
 136           victors << [candidate, challenger, diff]
 137         elsif diff == 0 && ties.include?([challenger, candidate]) == false
 138           ties << [candidate, challenger]
 139         end
 140       end
 141     end
 142
 143     victors.each do |list|
 144       if victories.has_key?(list[0])
 145         victories[list[0]][list[1]] = list[2]
 146       else
 147         victories[list[0]] = Hash.new
 148         victories[list[0]][list[1]] = list[2]
 149       end
 150     end
 151
 152     return victories, ties
 153   end
 154
 155   def ranked_candidates
 156     if not defined?(@ranked_candidates)
 157       @ranked_candidates = build_ranked_candidates()
 158     end
 159
 160     @ranked_candidates
 161   end
 162
 163   protected
 164   def defeats(candidates=nil, votes=nil)
 165     candidates ||= @election.candidates || []
 166     # we're assumign that if there are candidates, there must be at
 167     # least one vote for them
 168     votes ||= @election.votes
 169
 170     defeats = Array.new
 171     candidates.each do |candidate|
 172       candidates.each do |challenger|
 173         next if candidate == challenger
 174         if votes[candidate][challenger] > votes[challenger][candidate]
 175           defeats << [ candidate, challenger ]
 176         end
 177       end
 178     end
 179
 180     defeats
 181   end
 182
 183   def build_ranked_candidates
 184     # build a lis of ranked candidates by dropping the winner and
 185     # cursing
 186
 187     ranked_candidates = []
 188
 189     resultobj = self.dup
 190     candidates = self.election.candidates
 191
 192     until candidates.empty?
 193       ranked_candidates << resultobj.winners
 194
 195       new_voteobj = resultobj.election.dup
 196       candidates = new_voteobj.candidates
 197       new_voteobj.candidates.delete_if {|x| resultobj.winners.include?(x)}
 198       resultobj = new_voteobj.result
 199     end
 200
 201     ranked_candidates
 202   end
 203
 204 end
 205
 206 class PureCondorcetResult < CondorcetResult
 207   def initialize(voteobj=nil)
 208     super(voteobj)
 209     self.condorcet()
 210   end
 211
 212   protected
 213
 214   def condorcet
 215     votes = @election.votes
 216     candidates = @election.candidates
 217
 218     unless votes.length > 0 and candidates.length > 0
 219       return @winners=[]
 220     end
 221
 222     victors = Hash.new
 223     candidates.each do |candidate|
 224       victors[candidate] = Array.new
 225     end
 226
 227     self.defeats.each do |pair|
 228       winner, loser = *pair
 229       victors[winner] << loser
 230     end
 231
 232     victory_margin = 1
 233     while true
 234       winners = @election.candidates.find_all do |candidate|
 235         victors[candidate].length == @election.candidates.length - victory_margin
 236       end
 237       if winners.length > 0
 238         @winners = winners
 239         return @winners
 240       else
 241         victory_margin += 1
 242       end
 243     end
 244   end
 245 end
 246
 247 class CloneproofSSDResult < CondorcetResult
 248   def initialize(voteobj=nil)
 249     super(voteobj)
 250     @winners = self.cpssd()
 251   end
 252
 253   protected
 254
 255   def cpssd
 256     votes = @election.votes
 257     candidates = @election.candidates.dup
 258
 259     def in_schwartz_set?(candidate, candidates, transitive_defeats)
 260       candidates.each do |challenger|
 261         next if candidate == challenger
 262
 263         if transitive_defeats.include?( [ challenger, candidate ] ) and
 264             not transitive_defeats.include?( [ candidate, challenger ] )
 265           return false
 266         end
 267       end
 268       return true
 269     end
 270
 271     loop do
 272
 273       # see the array with the standard defeats
 274       transitive_defeats = self.defeats(candidates, votes)
 275       defeats_hash = Hash.new
 276       transitive_defeats.each { |td| defeats_hash[td] = 1 }
 277
 278       candidates = [candidates] unless candidates.class == Array
 279       candidates.each do |cand1|
 280         candidates.each do |cand2|
 281           unless cand1 == cand2
 282             candidates.each do |cand3|
 283               if not cand2 == cand3 and
 284                   not cand1 == cand3 and
 285                   defeats_hash[[cand2, cand1]] and
 286                   defeats_hash[[cand1, cand3]] and
 287                   not defeats_hash[[cand2, cand3]]
 288                 transitive_defeats << [cand2, cand3]
 289                 defeats_hash[[cand2, cand3]] = 1
 290               end
 291             end
 292           end
 293         end
 294       end
 295
 296       schwartz_set = Array.new
 297       candidates.each do |candidate|
 298         if in_schwartz_set?(candidate, candidates, transitive_defeats)
 299           schwartz_set << candidate
 300         end
 301       end
 302
 303       candidates = schwartz_set
 304
 305       # look through the schwartz set now for defeats
 306       defeats = self.defeats(candidates, votes)
 307
 308       # it's a tie or there's only one option
 309       break if defeats.length == 0
 310
 311       def is_weaker_defeat?( pair1, pair2 )
 312         votes = @election.votes
 313         if votes[pair1[0]][pair1[1]] > votes[pair2[0]][pair2[1]]
 314           return true
 315         elsif votes[pair1[0]][pair1[1]] == votes[pair2[0]][pair2[1]] and
 316             votes[pair1[1]][pair1[0]] > votes[pair2[1]][pair2[0]]
 317           return true
 318         else
 319           false
 320         end
 321       end
 322
 323       defeats.sort! do |pair1, pair2|
 324         if is_weaker_defeat?( pair1, pair2 )
 325           +1
 326         elsif is_weaker_defeat?( pair2, pair1 )
 327           -1
 328         else
 329           0
 330         end
 331       end
 332
 333       votes[defeats[0][0]][defeats[0][1]] = 0
 334       votes[defeats[0][1]][defeats[0][0]] = 0
 335
 336     end
 337
 338     return candidates
 339   end
 340
 341 end