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

Benjamin Mako Hill || Want to submit a patch?