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