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     victories_ties = {}
 127     candidates = @matrix.keys.sort
 128
 129     candidates.each do |candidate|
 130       candidates.each do |challenger|
 131         next if candidate == challenger
 132         diff = @matrix[candidate][challenger] - @matrix[challenger][candidate]
 133         victories_ties[candidate] = {} unless victories_ties.key?(candidate)
 134         if diff >= 0
 135           victories_ties[candidate][challenger] = diff
 136         end
 137       end
 138     end
 139
 140     return victories_ties
 141   end
 142
 143   def ranked_candidates
 144     if not defined?(@ranked_candidates)
 145       @ranked_candidates = build_ranked_candidates()
 146     end
 147
 148     @ranked_candidates
 149   end
 150
 151   protected
 152   def defeats(candidates=nil, votes=nil)
 153     candidates ||= @election.candidates || []
 154     # we're assumign that if there are candidates, there must be at
 155     # least one vote for them
 156     votes ||= @election.votes
 157
 158     defeats = Array.new
 159     candidates.each do |candidate|
 160       candidates.each do |challenger|
 161         next if candidate == challenger
 162         if votes[candidate][challenger] > votes[challenger][candidate]
 163           defeats << [ candidate, challenger ]
 164         end
 165       end
 166     end
 167
 168     defeats
 169   end
 170
 171   def build_ranked_candidates
 172     # build a lis of ranked candidates by dropping the winner and
 173     # cursing
 174
 175     ranked_candidates = []
 176
 177     resultobj = self.dup
 178     candidates = self.election.candidates
 179
 180     until candidates.empty?
 181       ranked_candidates << resultobj.winners
 182
 183       new_voteobj = resultobj.election.dup
 184       candidates = new_voteobj.candidates
 185       new_voteobj.candidates.delete_if {|x| resultobj.winners.include?(x)}
 186       resultobj = new_voteobj.result
 187     end
 188
 189     ranked_candidates
 190   end
 191
 192 end
 193
 194 class PureCondorcetResult < CondorcetResult
 195   def initialize(voteobj=nil)
 196     super(voteobj)
 197     self.condorcet()
 198   end
 199
 200   protected
 201
 202   def condorcet
 203     votes = @election.votes
 204     candidates = @election.candidates
 205
 206     unless votes.length > 0 and candidates.length > 0
 207       return @winners=[]
 208     end
 209
 210     victors = Hash.new
 211     candidates.each do |candidate|
 212       victors[candidate] = Array.new
 213     end
 214
 215     self.defeats.each do |pair|
 216       winner, loser = *pair
 217       victors[winner] << loser
 218     end
 219
 220     victory_margin = 1
 221     while true
 222       winners = @election.candidates.find_all do |candidate|
 223         victors[candidate].length == @election.candidates.length - victory_margin
 224       end
 225       if winners.length > 0
 226         @winners = winners
 227         return @winners
 228       else
 229         victory_margin += 1
 230       end
 231     end
 232   end
 233 end
 234
 235 class CloneproofSSDResult < CondorcetResult
 236   def initialize(voteobj=nil)
 237     super(voteobj)
 238     @winners = self.cpssd()
 239   end
 240
 241   protected
 242
 243   def cpssd
 244     votes = @election.votes
 245     candidates = @election.candidates.dup
 246
 247     def in_schwartz_set?(candidate, candidates, transitive_defeats)
 248       candidates.each do |challenger|
 249         next if candidate == challenger
 250
 251         if transitive_defeats.include?( [ challenger, candidate ] ) and
 252             not transitive_defeats.include?( [ candidate, challenger ] )
 253           return false
 254         end
 255       end
 256       return true
 257     end
 258
 259     loop do
 260
 261       # see the array with the standard defeats
 262       transitive_defeats = self.defeats(candidates, votes)
 263       defeats_hash = Hash.new
 264       transitive_defeats.each { |td| defeats_hash[td] = 1 }
 265
 266       candidates = [candidates] unless candidates.class == Array
 267       candidates.each do |cand1|
 268         candidates.each do |cand2|
 269           unless cand1 == cand2
 270             candidates.each do |cand3|
 271               if not cand2 == cand3 and
 272                   not cand1 == cand3 and
 273                   defeats_hash[[cand2, cand1]] and
 274                   defeats_hash[[cand1, cand3]] and
 275                   not defeats_hash[[cand2, cand3]]
 276                 transitive_defeats << [cand2, cand3]
 277                 defeats_hash[[cand2, cand3]] = 1
 278               end
 279             end
 280           end
 281         end
 282       end
 283
 284       schwartz_set = Array.new
 285       candidates.each do |candidate|
 286         if in_schwartz_set?(candidate, candidates, transitive_defeats)
 287           schwartz_set << candidate
 288         end
 289       end
 290
 291       candidates = schwartz_set
 292
 293       # look through the schwartz set now for defeats
 294       defeats = self.defeats(candidates, votes)
 295
 296       # it's a tie or there's only one option
 297       break if defeats.length == 0
 298
 299       def is_weaker_defeat?( pair1, pair2 )
 300         votes = @election.votes
 301         if votes[pair1[0]][pair1[1]] > votes[pair2[0]][pair2[1]]
 302           return true
 303         elsif votes[pair1[0]][pair1[1]] == votes[pair2[0]][pair2[1]] and
 304             votes[pair1[1]][pair1[0]] > votes[pair2[1]][pair2[0]]
 305           return true
 306         else
 307           false
 308         end
 309       end
 310
 311       defeats.sort! do |pair1, pair2|
 312         if is_weaker_defeat?( pair1, pair2 )
 313           +1
 314         elsif is_weaker_defeat?( pair2, pair1 )
 315           -1
 316         else
 317           0
 318         end
 319       end
 320
 321       votes[defeats[0][0]][defeats[0][1]] = 0
 322       votes[defeats[0][1]][defeats[0][0]] = 0
 323
 324     end
 325
 326     return candidates
 327   end
 328
 329 end