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

Benjamin Mako Hill || Want to submit a patch?