Fix problem with a [nil] result being taken as having a winner; add testcases
[rubyvote] / 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   def initialize(voteobj=nil)
148     unless voteobj and voteobj.kind_of?( CondorcetVote )
149       raise ArgumentError, "You must pass a CondorcetVote array.", caller
150     end
151     super(voteobj)
152   end
153
154   protected
155
156   def defeats(candidates=nil, votes=nil)
157     candidates = @election.candidates unless candidates
158     votes = @election.votes unless votes
159
160     defeats = Array.new
161     candidates = [candidates] unless candidates.class == Array
162     candidates.each do |candidate|
163       candidates.each do |challenger|
164         next if candidate == challenger
165         if votes[candidate][challenger] > votes[challenger][candidate]
166           defeats << [ candidate, challenger ]
167         end
168       end
169     end
170
171     defeats
172   end
173
174 end
175
176 class PureCondorcetResult < CondorcetResult
177   def initialize(voteobj=nil)
178     super(voteobj)
179     self.condorcet()
180   end
181
182   protected
183
184   def condorcet
185     votes = @election.votes
186     candidates = @election.candidates
187     unless votes.length>0 and candidates.length>0
188       @winners=[]
189       return @winners
190     end
191     victors = Hash.new
192     candidates.each do |candidate|
193       victors[candidate] = Array.new
194     end
195
196     self.defeats.each do |pair|
197       winner, loser = *pair
198       victors[winner] << loser
199     end
200
201     victory_margin = 1
202     while true
203       winners = @election.candidates.find_all do |candidate|
204         victors[candidate].length == @election.candidates.length - victory_margin
205       end
206       if winners.length > 0
207         @winners = winners
208         return @winners
209       else
210         victory_margin += 1
211       end
212     end
213   end
214 end
215
216 class CloneproofSSDResult < CondorcetResult
217   def initialize(voteobj=nil)
218     super(voteobj)
219     @winners = self.cpssd()
220   end
221
222   protected
223
224   def cpssd
225     votes = @election.votes
226     candidates = *@election.candidates
227     
228     def in_schwartz_set?(candidate, candidates, transitive_defeats)
229       candidates.each do |challenger|
230         next if candidate == challenger
231
232         if transitive_defeats.include?( [ challenger, candidate ] ) and
233             not transitive_defeats.include?( [ candidate, challenger ] )
234           return false
235         end
236       end
237       return true
238     end
239
240     loop do
241
242       # see the array with the standard defeats
243       transitive_defeats = self.defeats(candidates, votes)
244       defeats_hash = Hash.new
245       transitive_defeats.each { |td| defeats_hash[td] = 1 }
246
247       candidates = [candidates] unless candidates.class == Array
248       candidates.each do |cand1|
249         candidates.each do |cand2|
250           unless cand1 == cand2
251             candidates.each do |cand3|
252               if not cand2 == cand3 and 
253                   not cand1 == cand3 and 
254                   defeats_hash[[cand2, cand1]] and
255                   defeats_hash[[cand1, cand3]] and
256                   not defeats_hash[[cand2, cand3]] 
257                 transitive_defeats << [cand2, cand3]
258                 defeats_hash[[cand2, cand3]] = 1
259               end
260             end
261           end
262         end
263       end
264
265       schwartz_set = Array.new
266       candidates.each do |candidate|
267         if in_schwartz_set?(candidate, candidates, transitive_defeats)
268           schwartz_set << candidate
269         end
270       end
271
272       candidates = schwartz_set
273
274       # look through the schwartz set now for defeats
275       defeats = self.defeats(candidates, votes)
276       
277       # it's a tie or there's only one option
278       break if defeats.length == 0
279
280       def is_weaker_defeat?( pair1, pair2 )
281         votes = @election.votes
282         if votes[pair1[0]][pair1[1]] > votes[pair2[0]][pair2[1]]
283           return true
284         elsif votes[pair1[0]][pair1[1]] == votes[pair2[0]][pair2[1]] and
285             votes[pair1[1]][pair1[0]] > votes[pair2[1]][pair2[0]]
286           return true
287         else
288           false
289         end
290       end
291       
292       defeats.sort! do |pair1, pair2|
293         if is_weaker_defeat?( pair1, pair2 ) 
294           +1
295         elsif is_weaker_defeat?( pair2, pair1 ) 
296           -1
297         else
298           0
299         end
300       end
301  
302       votes[defeats[0][0]][defeats[0][1]] = 0
303       votes[defeats[0][1]][defeats[0][0]] = 0
304       
305     end
306
307     return candidates
308   end
309
310 end

Benjamin Mako Hill || Want to submit a patch?