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   def tally_vote(vote=nil)
  37
  38     vote.each_with_index do |winner, index|
  39       # only run through this if this *is* preferred to something
  40       break if vote.length - 1 == index
  41       losers = vote.last( vote.length - index )
  42
  43       losers.each do |loser|
  44         next if winner == loser
  45
  46         @votes[winner] = Hash.new unless @votes.has_key?(winner)
  47         @votes[loser] = Hash.new unless @votes.has_key?(loser)
  48
  49         if @votes[winner].has_key?(loser)
  50           @votes[winner][loser] += 1
  51         else
  52           @votes[winner][loser] = 1
  53         end
  54
  55         # make sure we have a comparable object
  56         @votes[loser][winner] = 0 unless @votes[loser].has_key?( winner )
  57
  58         @candidates << loser unless @candidates.include?( loser )
  59       end
  60
  61       @candidates << winner unless @candidates.include?( winner )
  62     end
  63   end
  64
  65   def result
  66     top_result = resultFactory( self )
  67     until @candidates.empty?
  68       aResult = resultFactory( self )
  69       top_result.full_results << aResult
  70       filter_out(aResult)
  71     end
  72     top_result
  73   end
  74
  75   protected
  76   def verify_vote(vote=nil)
  77     vote.instance_of?( Array ) and
  78       vote == vote.uniq
  79   end
  80
  81 end
  82
  83 class PureCondorcetVote < CondorcetVote
  84   def resultFactory(init)
  85     PureCondorcetResult.new(init)
  86   end
  87 end
  88
  89 class CloneproofSSDVote < CondorcetVote
  90   def resultFactory(init)
  91     CloneproofSSDResult.new(init)
  92   end
  93 end
  94
  95
  96 ##################################################################
  97 ## CondorcetResult Classes and SubClasses
  98 ##
  99 ## The CondorcetResult class is subclassed by the PureCondorcetResult
 100 ## and the CloneproofSSDResult classes but should not be used
 101 ## directly.
 102
 103 class CondorcetResult < ElectionResult
 104   def initialize(voteobj=nil)
 105     unless voteobj and voteobj.kind_of?( CondorcetVote )
 106       raise ArgumentError, "You must pass a CondorcetVote array.", caller
 107     end
 108     super(voteobj)
 109   end
 110
 111   protected
 112   def defeats(candidates=nil, votes=nil)
 113     candidates = @election.candidates unless candidates
 114     votes = @election.votes unless votes
 115
 116     defeats = Array.new
 117     candidates.each do |candidate|
 118       candidates.each do |challenger|
 119         next if candidate == challenger
 120         if votes[candidate][challenger] > votes[challenger][candidate]
 121           defeats << [ candidate, challenger ]
 122         end
 123       end
 124     end
 125
 126     defeats
 127   end
 128
 129 end
 130
 131 class PureCondorcetResult < CondorcetResult
 132   def initialize(voteobj=nil)
 133     super(voteobj)
 134     self.condorcet()
 135   end
 136
 137   protected
 138   def condorcet
 139     votes = @election.votes
 140     candidates = @election.candidates
 141
 142     victors = Hash.new
 143     candidates.each do |candidate|
 144       victors[candidate] = Array.new
 145     end
 146
 147     self.defeats.each do |pair|
 148       winner, loser = *pair
 149       victors[winner] << loser
 150     end
 151
 152     winners = @election.candidates.find_all do |candidate|
 153         victors[candidate].length == @election.candidates.length - 1
 154     end
 155
 156     @winners << winners if winners.length == 1
 157   end
 158 end
 159
 160 class CloneproofSSDResult < CondorcetResult
 161   def initialize(voteobj=nil)
 162     super(voteobj)
 163     @winners = self.cpssd()
 164   end
 165
 166   protected
 167   def cpssd
 168     votes = @election.votes
 169     candidates = *@election.candidates
 170
 171     def in_schwartz_set?(candidate, candidates, transitive_defeats)
 172       candidates.each do |challenger|
 173         next if candidate == challenger
 174
 175         if transitive_defeats.include?( [ challenger, candidate ] ) and
 176             not transitive_defeats.include?( [ candidate, challenger ] )
 177           return false
 178         end
 179       end
 180       return true
 181     end
 182
 183     loop do
 184
 185       # see the array with the standard defeats
 186       transitive_defeats = self.defeats(candidates, votes)
 187
 188       candidates.each do |cand1|
 189         candidates.each do |cand2|
 190           candidates.each do |cand3|
 191             if transitive_defeats.include?( [ cand2, cand1 ] ) and
 192                 transitive_defeats.include?( [ cand1, cand3 ] ) and
 193                 not transitive_defeats.include?( [ cand2, cand3 ] ) and
 194                 not cand2 == cand3
 195               transitive_defeats << [ cand2, cand3 ]
 196             end
 197           end
 198         end
 199       end
 200
 201       schwartz_set = Array.new
 202       candidates.each do |candidate|
 203         if in_schwartz_set?(candidate, candidates, transitive_defeats)
 204           schwartz_set << candidate
 205         end
 206       end
 207
 208       candidates = schwartz_set
 209
 210       # look through the schwartz set now for defeats
 211       defeats = self.defeats(candidates, votes)
 212
 213       # it's a tie or there's only one option
 214       break if defeats.length == 0
 215
 216       def is_weaker_defeat?( pair1, pair2 )
 217         votes = @election.votes
 218         if votes[pair1[0]][pair1[1]] > votes[pair2[0]][pair2[1]]
 219           return true
 220         elsif votes[pair1[0]][pair1[1]] == votes[pair2[0]][pair2[1]] and
 221             votes[pair1[1]][pair1[0]] > votes[pair2[1]][pair2[0]]
 222           return true
 223         else
 224           false
 225         end
 226       end
 227
 228       defeats.sort! do |pair1, pair2|
 229         if is_weaker_defeat?( pair1, pair2 )
 230           +1
 231         elsif is_weaker_defeat?( pair2, pair1 )
 232           -1
 233         else
 234           0
 235         end
 236       end
 237
 238       votes[defeats[0][0]][defeats[0][1]] = 0
 239       votes[defeats[0][1]][defeats[0][0]] = 0
 240
 241     end
 242
 243     return candidates
 244   end
 245
 246 end