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