1 # election library -- a ruby library for elections
2 # copyright © 2005 MIT Media Lab and Benjamin Mako Hill
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.
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.
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
19 #################################################################
20 ## ==== condorcet.rb ====
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 #################################################################
28 ##################################################################
29 ## CondorcetVote Classes and SubClasses
31 ## The CondorcetVote class is subclassed by the PureCondorcetVote and
32 ## the CloneproofSSDVote classes but should not be used directly.
34 class CondorcetVote < ElectionVote
36 attr_accessor :results
38 def initialize(votes=nil)
39 unless defined?(@candidates)
40 @candidates = Array.new
41 votes.each do |vote_row|
42 vote_row = vote_row.flatten if vote_row.class == Array
43 vote_row.each do |vote|
44 @candidates << vote unless @candidates.include?(vote)
52 def tally_vote(vote=nil)
54 vote.each_with_index do |winners, index|
55 if vote.flatten.length < @candidates.length
56 implied_losers = @candidates.select { |c| not vote.flatten.include?(c) }
57 vote.push(implied_losers)
59 if vote.length - 1 == index
62 losers = vote.flatten.last( vote.flatten.length - index - 1)
65 losers.each do |place|
66 place = [place] unless place.class == Array
69 winners = [winners] unless winners.class == Array
70 next if winners.include?(loser)
71 winners.each do |winner|
72 @votes[winner] = Hash.new unless @votes.has_key?(winner)
73 @votes[loser] = Hash.new unless @votes.has_key?(loser)
75 if @votes[winner].has_key?(loser)
76 @votes[winner][loser] += 1
78 @votes[winner][loser] = 1
81 # make sure we have a comparable object
82 @votes[loser][winner] = 0 unless @votes[loser].has_key?( winner )
90 if @results.size < 2 && (not @candidates.empty?)
97 find_only_winner unless @winner
103 def verify_vote(vote=nil)
104 vote.instance_of?( Array ) and
109 find_only_winner unless @winner
110 until @candidates.empty?
111 aResult = resultFactory( self )
112 @results << aResult.winners
118 @winner = resultFactory( self )
119 @results << @winner.winners
125 class PureCondorcetVote < CondorcetVote
126 def resultFactory(init)
127 PureCondorcetResult.new(init)
131 class CloneproofSSDVote < CondorcetVote
132 def resultFactory(init)
133 CloneproofSSDResult.new(init)
139 ##################################################################
140 ## CondorcetResult Classes and SubClasses
142 ## The CondorcetResult class is subclassed by the PureCondorcetResult
143 ## and the CloneproofSSDResult classes but should not be used
146 class CondorcetResult < ElectionResult
149 def initialize(voteobj=nil)
150 unless voteobj and voteobj.kind_of?( CondorcetVote )
151 raise ArgumentError, "You must pass a CondorcetVote array.", caller
154 @matrix = voteobj.votes
157 def victories_and_ties
160 candidates = @matrix.keys.sort
162 candidates.each do |candidate|
163 candidates.each do |challenger|
164 next if candidate == challenger
165 diff = @matrix[candidate][challenger] - @matrix[challenger][candidate]
167 victors << [candidate, challenger, diff]
168 elsif diff == 0 && ties.include?([challenger, candidate]) == false
169 ties << [candidate, challenger]
174 victories = victors.sort {|a,b| b[2] <=> a[2]}
176 return victories, ties
180 def defeats(candidates=nil, votes=nil)
181 candidates ||= @election.candidates || []
182 # we're assumign that if there are candidates, there must be at
183 # least one vote for them
184 votes ||= @election.votes
187 candidates.each do |candidate|
188 candidates.each do |challenger|
189 next if candidate == challenger
190 if votes[candidate][challenger] > votes[challenger][candidate]
191 defeats << [ candidate, challenger ]
201 class PureCondorcetResult < CondorcetResult
202 def initialize(voteobj=nil)
210 votes = @election.votes
211 candidates = @election.candidates
213 unless votes.length > 0 and candidates.length > 0
218 candidates.each do |candidate|
219 victors[candidate] = Array.new
222 self.defeats.each do |pair|
223 winner, loser = *pair
224 victors[winner] << loser
229 winners = @election.candidates.find_all do |candidate|
230 victors[candidate].length == @election.candidates.length - victory_margin
232 if winners.length > 0
242 class CloneproofSSDResult < CondorcetResult
243 def initialize(voteobj=nil)
245 @winners = self.cpssd()
251 votes = @election.votes
252 candidates = @election.candidates.dup
254 def in_schwartz_set?(candidate, candidates, transitive_defeats)
255 candidates.each do |challenger|
256 next if candidate == challenger
258 if transitive_defeats.include?( [ challenger, candidate ] ) and
259 not transitive_defeats.include?( [ candidate, challenger ] )
268 # see the array with the standard defeats
269 transitive_defeats = self.defeats(candidates, votes)
270 defeats_hash = Hash.new
271 transitive_defeats.each { |td| defeats_hash[td] = 1 }
273 candidates = [candidates] unless candidates.class == Array
274 candidates.each do |cand1|
275 candidates.each do |cand2|
276 unless cand1 == cand2
277 candidates.each do |cand3|
278 if not cand2 == cand3 and
279 not cand1 == cand3 and
280 defeats_hash[[cand2, cand1]] and
281 defeats_hash[[cand1, cand3]] and
282 not defeats_hash[[cand2, cand3]]
283 transitive_defeats << [cand2, cand3]
284 defeats_hash[[cand2, cand3]] = 1
291 schwartz_set = Array.new
292 candidates.each do |candidate|
293 if in_schwartz_set?(candidate, candidates, transitive_defeats)
294 schwartz_set << candidate
298 candidates = schwartz_set
300 # look through the schwartz set now for defeats
301 defeats = self.defeats(candidates, votes)
303 # it's a tie or there's only one option
304 break if defeats.length == 0
306 def is_weaker_defeat?( pair1, pair2 )
307 votes = @election.votes
308 if votes[pair1[0]][pair1[1]] > votes[pair2[0]][pair2[1]]
310 elsif votes[pair1[0]][pair1[1]] == votes[pair2[0]][pair2[1]] and
311 votes[pair1[1]][pair1[0]] > votes[pair2[1]][pair2[0]]
318 defeats.sort! do |pair1, pair2|
319 if is_weaker_defeat?( pair1, pair2 )
321 elsif is_weaker_defeat?( pair2, pair1 )
328 votes[defeats[0][0]][defeats[0][1]] = 0
329 votes[defeats[0][1]][defeats[0][0]] = 0