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