]> projects.mako.cc - selectricity/blob - lib/rubyvote/condorcet.rb
Add XMLRPC call for getting a list of all QuickVotes
[selectricity] / 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   attr_accessor :results
37
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)
45         end
46       end
47     end
48     super(votes)
49     @results = Array.new
50   end
51
52   def tally_vote(vote=nil)
53
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)
58       end
59       if vote.length - 1 == index
60         losers = []
61       else
62         losers = vote.flatten.last( vote.flatten.length - index - 1)
63       end
64
65       losers.each do |place|
66         place = [place] unless place.class == Array
67         place.each do |loser|
68           
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)
74
75             if @votes[winner].has_key?(loser)
76               @votes[winner][loser] += 1
77             else
78               @votes[winner][loser] = 1
79             end
80
81             # make sure we have a comparable object
82             @votes[loser][winner] = 0 unless @votes[loser].has_key?( winner )
83           end
84         end
85       end
86     end
87   end
88
89   def results
90     if @results.size < 2 && (not @candidates.empty?)
91       tabulate
92     end
93     @results
94   end
95
96   def result
97     find_only_winner unless @winner
98     @winner
99   end
100
101   protected
102
103   def verify_vote(vote=nil)
104     vote.instance_of?( Array ) and
105       vote == vote.uniq
106   end
107
108   def tabulate
109     find_only_winner unless @winner
110     until @candidates.empty? 
111       aResult = resultFactory( self )
112       @results << aResult.winners
113       filter_out(aResult)
114     end
115   end
116
117   def find_only_winner
118     @winner = resultFactory( self )
119     @results << @winner.winners
120     filter_out(@winner)
121   end
122
123 end
124
125 class PureCondorcetVote < CondorcetVote
126   def resultFactory(init)
127     PureCondorcetResult.new(init)
128   end
129 end
130
131 class CloneproofSSDVote < CondorcetVote
132   def resultFactory(init)
133     CloneproofSSDResult.new(init)
134   end
135
136 end
137
138
139 ##################################################################
140 ## CondorcetResult Classes and SubClasses
141 ##
142 ## The CondorcetResult class is subclassed by the PureCondorcetResult
143 ## and the CloneproofSSDResult classes but should not be used
144 ## directly.
145
146 class CondorcetResult < ElectionResult
147   attr_reader :matrix
148   
149   def initialize(voteobj=nil)
150     unless voteobj and voteobj.kind_of?( CondorcetVote )
151       raise ArgumentError, "You must pass a CondorcetVote array.", caller
152     end
153     super(voteobj)
154     @matrix = voteobj.votes
155   end
156   
157   def list_defeats
158     victors = Array.new
159     ties = Array.new
160     candidates = @matrix.keys.sort
161     
162     candidates.each do |candidate|
163       candidates.each do |challenger|
164         next if candidate == challenger
165         diff = @matrix[candidate][challenger] - @matrix[challenger][candidate]
166         if diff > 0 
167           victors << [candidate, challenger, diff]
168         elsif diff == 0 && ties.include?([challenger, candidate]) == false
169           ties << [candidate, challenger] 
170         end
171       end
172     end
173     
174     victories = victors.sort {|a,b| b[2] <=> a[2]}
175     
176     return victories, ties    
177   end
178         
179   protected
180   def defeats(candidates=nil, votes=nil)
181     candidates = @election.candidates unless candidates
182     votes = @election.votes unless votes
183
184     defeats = Array.new
185     candidates = [candidates] unless candidates.class == Array
186     candidates.each do |candidate|
187       candidates.each do |challenger|
188         next if candidate == challenger
189         if votes[candidate][challenger] > votes[challenger][candidate]
190           defeats << [ candidate, challenger ]
191         end
192       end
193     end
194
195     defeats
196   end
197
198 end
199
200 class PureCondorcetResult < CondorcetResult
201   def initialize(voteobj=nil)
202     super(voteobj)
203     self.condorcet()
204   end
205
206   protected
207   
208   def condorcet
209     votes = @election.votes
210     candidates = @election.candidates
211     unless votes.length>0 and candidates.length>0
212       @winners=[]
213       return @winners
214     end
215     victors = Hash.new
216     candidates.each do |candidate|
217       victors[candidate] = Array.new
218     end
219
220     self.defeats.each do |pair|
221       winner, loser = *pair
222       victors[winner] << loser
223     end
224
225     victory_margin = 1
226     while true
227       winners = @election.candidates.find_all do |candidate|
228         victors[candidate].length == @election.candidates.length - victory_margin
229       end
230       if winners.length > 0
231         @winners = winners
232         return @winners
233       else
234         victory_margin += 1
235       end
236     end
237   end
238 end
239
240 class CloneproofSSDResult < CondorcetResult
241   def initialize(voteobj=nil)
242     super(voteobj)
243     @winners = self.cpssd()
244     @winners.delete nil
245   end
246
247   protected
248
249   def cpssd
250     votes = @election.votes
251     candidates = *@election.candidates
252
253     def in_schwartz_set?(candidate, candidates, transitive_defeats)
254       candidates.each do |challenger|
255         next if candidate == challenger
256
257         if transitive_defeats.include?( [ challenger, candidate ] ) and
258             not transitive_defeats.include?( [ candidate, challenger ] )
259           return false
260         end
261       end
262       return true
263     end
264
265     loop do
266
267       # see the array with the standard defeats
268       transitive_defeats = self.defeats(candidates, votes)
269       defeats_hash = Hash.new
270       transitive_defeats.each { |td| defeats_hash[td] = 1 }
271
272       candidates = [candidates] unless candidates.class == Array
273       candidates.each do |cand1|
274         candidates.each do |cand2|
275           unless cand1 == cand2
276             candidates.each do |cand3|
277               if not cand2 == cand3 and 
278                   not cand1 == cand3 and 
279                   defeats_hash[[cand2, cand1]] and
280                   defeats_hash[[cand1, cand3]] and
281                   not defeats_hash[[cand2, cand3]] 
282                 transitive_defeats << [cand2, cand3]
283                 defeats_hash[[cand2, cand3]] = 1
284               end
285             end
286           end
287         end
288       end
289
290       schwartz_set = Array.new
291       candidates.each do |candidate|
292         if in_schwartz_set?(candidate, candidates, transitive_defeats)
293           schwartz_set << candidate
294         end
295       end
296
297       candidates = schwartz_set
298
299       # look through the schwartz set now for defeats
300       defeats = self.defeats(candidates, votes)
301       
302       # it's a tie or there's only one option
303       break if defeats.length == 0
304
305       def is_weaker_defeat?( pair1, pair2 )
306         votes = @election.votes
307         if votes[pair1[0]][pair1[1]] > votes[pair2[0]][pair2[1]]
308           return true
309         elsif votes[pair1[0]][pair1[1]] == votes[pair2[0]][pair2[1]] and
310             votes[pair1[1]][pair1[0]] > votes[pair2[1]][pair2[0]]
311           return true
312         else
313           false
314         end
315       end
316       
317       defeats.sort! do |pair1, pair2|
318         if is_weaker_defeat?( pair1, pair2 ) 
319           +1
320         elsif is_weaker_defeat?( pair2, pair1 ) 
321           -1
322         else
323           0
324         end
325       end
326  
327       votes[defeats[0][0]][defeats[0][1]] = 0
328       votes[defeats[0][1]][defeats[0][0]] = 0
329       
330     end
331
332     return candidates
333   end
334
335 end

Benjamin Mako Hill || Want to submit a patch?